26

これは、アルゴリズム設計マニュアルの演習です。

与えられた無向グラフ G = (V, E) に長さ 3 の三角形または閉路が含まれているかどうかを判断する問題を考えてみましょう。

(a) O(|V |^3) を与えて、三角形が存在する場合にそれを見つけます。

(b) 時間 O(|V |·|E|) で実行されるようにアルゴリズムを改善します。|V | と仮定することができます。≤ |E|。

これらの境界により、G の隣接行列と隣接リスト表現の間で変換する時間が得られることに注意してください。

ここに私の考えがあります：

(a) グラフが隣接リストとして与えられている場合、O(|V|^2) でリストを行列に変換できます。それから私は：

for (int i = 0;i < n;i++) 
   for (int j = i+1;j < n;j++) 
   if (matrix[i][j] == 1) 
      for (int k = j+1;k < n;k++) 
         if (matrix[i][k] == 1 && matrix[j][k] == 1)
             return true;

これにより、三角形をテストするための O(|V|^3) が得られるはずです。

(b) 私の最初の直感は、グラフが隣接リストとして与えられた場合、bfs を実行するということです。クロス エッジが見つかった場合はいつでも、たとえば 、if y-x is a cross edge次に を実行しcheck whether parent[y] == parent[x], if true, then a triangle is foundます。

私の考えが正しいかどうか誰か教えてくれませんか?

この（b）についても、その複雑さはわかりません。O(|V| + |E|) でいいじゃないですか。

O(|V|*|E|) でどうすればいいですか?

4

4 に答える 4

38

考えられるO(|V||E|)解決策は、(a) のブルート フォースと同じ考え方です。

for each edge (u, v):
  for each vertex w:
     if (v, w) is an edge and (w, u) is an edge:
          return true
return false

すべての頂点のペアではなく、すべてのエッジをチェックします(三角形を形成する別の頂点を使用)。これは、エッジと頂点が実行可能な解を形成するかどうかを判断するのに十分な情報です。

BFS ソリューションの反例:

       A
     / | \
    /  |  \
   B   C   D
   |   |   |
   |   |   |
   F---G---H
   |       |
   ---------
    (F, H) is also an edge

father[F] != father[G] != father[H]したがって、アルゴリズムは false を返すことに注意してください。ただし、(F, G, H) は実現可能なソリューションです!

于 2012-04-17T14:38:44.517 に答える
8

隣接行列がある場合は、行列を二乗し、元の行列と正方行列の同じ場所にゼロ以外のエントリがあるかどうかを確認することで、三角形を見つけることができます。

単純な行列乗算には時間O(n^3)がかかりますが、より優れた高速な行列乗算アルゴリズムがあります。最もよく知られているアルゴリズムの 1 つは、時間内に実行されるCoppersmith-WinogradアルゴリズムO(n^2.4)です。つまり、アルゴリズムは次のようになります。

  • 時間を使用O(V^2)して隣接行列に変換します。
  • 時間を使用O(V^2.4)して、隣接行列の 2 乗を計算します。
  • 時間をかけて行列をチェックし、一致するO(V^2)ゼロ以外のエントリを探します。
  • ゼロ以外のエントリが一致している行と列のインデックス (存在する場合) は、関連する 2 つのノードを示します。
  • 時間をO(V)かけて、両方の既知のノードに共通する 3 番目のノードを絞り込みます。

したがって、全体としてこれには時間がかかりO(V^2.4)ます。より正確には、時間がかかりますが、行列の乗算には時間がかかります。このアルゴリズムと、 amit が回答で説明している if-any-edge-end-points-have-a-common-neighbor アルゴリズムを動的に切り替えて、それを改善することができO(V min(V^1.4, E))ます。

これは、問題をより深く掘り下げた論文です。

この問題がいかに理論上の発見に依存しているかがよくわかります。行列の乗算が実際に二次であるという推測が真実であることが判明した場合、O(V^2)またはO(V^2 log(V))またはそのようなものの非常に優れた時間境界が得られます。しかし、量子コンピューターがうまくいけば、それよりもさらに優れたことができるようになります( O(V^1.3).

于 2015-01-07T03:01:06.823 に答える
1

これが私の考えです：

上で指摘したように、元の BFS ソリューションは正しくありません。ただし、DFS を変更することはできます。DFS の各頂点にアクセスするときに、アクセスしたノードに番号を割り当てます。ここで、頂点に到達した場合 (クロス エッジを見た質問では、無向グラフには何もありません)、その隣接リストを確認し、1 つの頂点が検出されたと仮定します (ただし、処理されていないため、発生することはありません)。次に、その数を確認します。 . 差が 2 の場合、長さ 3 のサイクルがあります。

于 2013-11-10T18:18:49.890 に答える
0

このブログ投稿で説明されている行列乗算ソリューションが本当に気に入っています。

a = 隣接行列とする

  • a*a (a2) 行列の隣接関係は、2 つの長さのパスの数です。
  • a2*a 行列の隣接関係は、3 つの長さのパスの数です。

問題は、行列の乗算が遅いことです...ただし、GPGPU を使用して行列の乗算を実行でき、GPU を含む最新のアーキテクチャでパフォーマンスの高いソリューションを実現できます。

于 2014-06-12T23:49:35.810 に答える