17

をグラフAの隣接行列としますG = (V,E)。A(i,j) = 1ノードがエッジで接続されている場合、iそうでない場合。jA(i,j) = 0

G私の目的は、非環状かどうかを理解することです。サイクルは次のように定義されます。

  • i接続されてjいます:A(i,j) = 1
  • j接続されてkいます:A(j,k) = 1
  • k接続されてiいます:A(k,i) = 1

次のようにマトリックスをナビゲートするソリューションを実装しました。

  • エッジから開始(i,j)
  • Oから出ているエッジのセットj、つまり のj- 番目の行のすべての 1 を選択します。A
  • ODFS 方式でナビゲートする
  • このナビゲーションから生成されたパスの 1 つがノードiにつながる場合、サイクルが検出されます。

マトリックス内のすべてのパスを評価する必要があるため、明らかにこのソリューションは非常に遅いです。が非常に大きい場合A、必要なオーバーヘッドは非常に大きくなります。DFSなどの高価なアルゴリズムを使用せずにサイクルを見つけるために、隣接行列をナビゲートする方法があるかどうか疑問に思っていました.

MATLAB でソリューションを実装したいと考えています。

前もって感謝します、

エレノア。

4

8 に答える 8

13

このmath.stackexchange の質問に答えるときに、この質問に出くわしました。将来の読者のために、私は (他の人がすでにそうしているように) Danil Asotsky の答えが間違っていることを指摘し、別のアプローチを提供する必要があると感じています。Danil が言及している定理は、A^k の (i,j) エントリがG の i から j までの長さ kのウォークの数をカウントするというものです。ここで重要なことは、ウォークが頂点を繰り返すことができるということです。したがって、A^k の対角エントリが正の場合でも、エントリがカウントする各ウォークには繰り返される頂点が含まれている可能性があるため、サイクルとしてカウントされません。

反例: 長さ 4 のパスには、Danil の回答によると 4 サイクルが含まれます (ハミルトン サイクル問題を解決するため、回答が P=NP を意味することは言うまでもありません)。

とにかく、ここに別のアプローチがあります。グラフが非巡回であるのは、それがフォレストである場合のみです。つまり、c 個のコンポーネントと正確に nc 個のエッジを持ちます。ここで、n は頂点の数です。幸いなことに、ラプラシアン行列Lを使用してコンポーネントの数を計算する方法があります。これは、-A の (i,i) エントリを A の行 i のエントリの合計 (つまり、頂点の次数) に置き換えることによって得られます。ラベル i)。このとき、G の成分数は n-rank(L) (つまり、L の固有値である 0 の多重度) であることがわかります。

したがって、エッジの数が少なくとも n-(n-rank(L))+1 である場合にのみ、G はサイクルを持ちます。一方、ハンドシェークの補題により、エッジの数は正確に trace(L) の半分になります。そう：

0.5*trace(L)=rank(L) の場合に限り、G は非巡回です。同様に、G は 0.5*trace(L) >= rank(L)+1 の場合にのみサイクルを持ちます。

于 2014-08-27T21:13:54.910 に答える
7

Danilの観察に基づいて、を計算する必要があります。A^nこれを行うには、もう少し効率的な方法があります。

n = size(A,1);
An = A; 
for ii = 2:n
     An = An * A; % do not re-compute A^n from skratch
     if trace(An) ~= 0
        fprintf(1, 'got cycles\n');
     end
end
于 2013-05-08T10:32:26.457 に答える
1

このアプローチは DFS を使用しますが、後続の DFS でノードを繰り返さないため、非常に効率的です。

高レベルのアプローチ:

すべてのノードの値を に初期化します-1。

探索されていない各ノードから DFS を実行し、そのノードの値を から始まる自動インクリメント値に設定します0。

これらの DFS については、各ノードの値をprevious node's value + i/n^k、そのノードがi前のノードの th 子であり、k探索された深さである場所で更新し、既に探索されたノードをスキップします (より大きな値のチェックを除く)。

したがって、例n = 10:

   0.1   0.11   0.111
   j   - k    - p
0 /    \ 0.12
i \ 0.2  l
    m

1   1.1
q - o
...

i/branching factor+1各ノードを使用して数値の有効桁数を減らすこともできますが、これを決定するには追加の計算が必要です。

上記で、 から DFS を実行しました。iこれには 2 つの子jとがありmました。m子供がいなかった、子供jが2人いた....そしてi、次の未調査のノードから別のDFSを終了して開始しましたq。

より大きな値に遭遇するたびに、サイクルが発生したことがわかります。

複雑：

すべてのノードを最大で 1 回チェックし、n 個のチェックを行うすべてのノードで、複雑さは ですO(n^2)。これは、マトリックス内のすべてのエントリを 1 回見るのと同じです (これ以上のことはできません)。

ノート：

また、非常に密集したグラフでない限り、隣接リストはおそらく隣接マトリックスよりも高速になることに注意してください。

于 2013-05-08T10:05:57.570 に答える
0

それは私も見つけた問題です。私が考えた説明は次のとおりです
。サイクルについて話すとき、暗黙のうちに有向サイクルを意味します。有向グラフを考慮すると、隣接行列の意味が異なります。これは確かに長さ 2 の有向循環です。したがって、$A^n$ の解は実際には有向グラフ用です。無向グラフの場合、行列の上三角バージョン (残りはゼロで埋められている) を考慮して、手順を繰り返すだけで修正できると思います。これが正しい答えかどうか教えてください。

于 2014-01-08T14:32:28.300 に答える
0

コメントを直接追加することはできませんが、この Casteels (@casteels) によるコメントは正しくありません。

@Pushpendre私のポイントは、Danilの答えが有向グラフに対して正しかった場合、無向グラフに対しても正しかったということです。私の前のコメントの反例には、あなたが書き留めた隣接行列がありません。各エッジを各方向の有向​​エッジに置き換えると言いました。これにより、無向の場合と同じ隣接行列が得られます。>自転車とクローズドウォークを混同していませんか? – Casteels 4 月 24 >'15 で 9:20

有向グラフが両方向に円弧を持つ 2 つの頂点を持つとすぐに、長さ 2 のサイクルと、その隣接行列の 2 乗 (上で提案された「構築」では、実際には基になる無向グラフ) は、0 以外の対角係数を持ちます (エッジは頂点からそれ自体までの長さ 2 の (非基本的な) ウォークをすぐに与えるため、空でない無向グラフのすべての隣接行列の 2 乗も同様です)。 ）。したがって、その場合、ダニルの答えは本質的にサイクルを正しく検出します。上記の推論は正しくありません。

ダニルの答えは、有向グラフについては確かに正しいです。有向グラフでは、単一の弧を両方向にトラバースすることはできないため、すべての閉じた有向ウォークには有向サイクルが含まれている必要があります。これにより、有向グラフの元の隣接行列の累乗の対角線上にゼロ以外の係数が作成されます。したがって、対角係数が非ゼロになるとすぐに停止し、1 から頂点の数まで行列の累乗を計算し続けることができます。

于 2021-03-23T08:29:44.470 に答える
0

行列アプローチに関するその他の考え... 引用されている例は、切断されたグラフの隣接行列です (ノード 1 と 2 は接続され、ノード 3 と 4 は接続されていますが、どちらのペアも他のペアに接続されていません)。A^2 を計算すると、(前述のように) 答えは恒等行列です。ただし、Trace(A^2) = 4 であるため、これは長さ 2 の 2 つのループがあることを示しています (これは正しいです)。これらのループが適切に識別され、行列から削除されるまで、A^3 の計算は許可されません。これはいくつかのステップを必要とする複雑な手順であり、RL Norman の「A Matrix Method for Location of Cycles of a Directed Graph」AIChE J, 11-3 (1965) pp. 450-452 で詳しく説明されています。注意: このアプローチがすべてのサイクル、UNIQUE サイクル、および/または ELEMENTARY サイクルを見つけることが保証されているかどうかは、著者には不明です。

于 2014-10-26T03:20:46.367 に答える