トーナメントグラフ

Question

トーナメントは、無向の完全なグラフの各エッジに方向を割り当てることによって得られる有向グラフ（有向グラフ）です。つまり、頂点のすべてのペアが単一の有向エッジによって接続されている有向グラフです。

データ構造は隣接行列です。

グラフがトーナメントグラフであるかどうかを調べるアルゴリズムは何ですか？

Answer 1

隣接行列にはn ^ 2個のエントリがあり、問題を解決するにはすべてのエントリにある情報が必要です。 （適切なエッジが存在することを確認するには1が必要であり、バックエッジが存在しないことを確認するには0が必要です。）したがって、マトリックスから少なくともN ^ 2エントリを読み取る必要があるため、全体的な問題は少なくともO（N ^ 2）時間。

BFS検索の試行について：トラバーサルがO（n ^ 2）をとる場合-隣接行列でエッジを検索する必要があるため-これは、バックエッジチェックが一定であるかどうかは関係ありません時間、全体的なアルゴリズムはまだO（n ^ 2）です。

この問題を見る別の方法：エッジの数は頂点の可能なペアの数に等しいため、n *（n-1）/ 2のエッジがあり、これはO（n ^ 2）です。トラバーサルはO（V + E）、つまりO（n + n ^ 2）であり、したがってO（n ^ 2）です。

このアルゴリズムのベストケースタイムはO（n ^ 2）であるため、マトリックスの右上半分（対角線上）を単純にループし、それらのエントリごとに、 ）1、またはb）転置等価物は1です。

Answer 2

編集：グラフが完成した部分を見逃しました。

M が隣接行列の場合、 Mt は転置行列、〜M はすべての「ビット」を含む行列です。 A ^ B は2つのマトリックス間のビットごとのxorです。

その後、マトリックスはトーナメントの場合です：

〜（M ^ Mt）= I

Answer 3

tonfaのコメントに追加するには：

概要：各iのアルゴリズム＆quot;＆＃8800; j、（i、j）と（j、i）のどちらかがグラフにあることを確認してください。漸近的に最適です。

詳細： 隣接行列を読み取るには、＆＃937;（n ² ）時間かかります。したがって、o（n ² ）時間でこの問題を解決する方法はありません。しかし、入力を無視しましょう。

マトリックスが既にメモリにあるとします。グラフの無向バージョンが完全であることを確認するには、それぞれのi＆＃8800; j、エッジ（i、j）および（j、i）の少なくとも1つがグラフにあります。隣接グラフしかないので、これは、ある時点で、各iについて（i、j）または（j、i）の少なくとも1つを訪問する必要があることを意味します。 j。完全性を保証する他の方法はありません。これを確認するには、n（n + 1）/ 2 = O（n ² ）ステップかかります。