1

次のような接続された頂点の大きな任意のグラフがあるとします。これらがネットワーク接続であると仮定します。一部の接続 (赤色で表示) は、他の接続よりもはるかにダメージを与えます。2 つの赤い接続が失敗した場合、多くのポイントが残りの島のメンバーに接続できなくなります。

これらの神経学的接続をどのように見つけることができますか?

そのための既存のアルゴリズムはありますか？

グラフのサンプル

4

2 に答える 2

1

あなたはEdge Connectivityについて疑問に思っています。あなたの場合、グラフが2エッジ接続されていることだけを気にしているようです。この場合には特定のアルゴリズムがあるかもしれませんが、わかりません。これは、私がうまくいくと思う単純なアルゴリズムです。

For all edges, E, in your graph, G:
  Remove E from G.
  Find any path, P, from src(E) to dst(E).
  Remove all edges in P from G.
  Find a path from src(E) to dst(E),
    if none exists then E is one of your important edges.

これは高速ではありませんが、O(E*(E+V)) かかります。グラフが平面である場合、O(E) == O(V) であるため、それほど悪くはありません。時間 O(V^2)。グラフがより多く接続されている場合、これは O(V^4) と同じくらい悪い可能性があり、法外な可能性があります。

于 2012-07-25T18:45:11.010 に答える
0

頭のてっぺんから、フローネットワークを見る必要があると思います: http://en.wikipedia.org/wiki/Flow_network。

于 2012-07-25T16:18:43.650 に答える