graph - グラフの周囲を見つける

Question

隣接行列として表される特定のグラフの胴回りを出力する必要があります。隣接行列または隣接リストを使用してグラフの胴回りを取得する方法を教えてください。

例：

graph one:
0 1 0 0
1 0 0 1
0 0 0 0
0 1 0 0 

graph two:
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0

The result:
Girth of graph 1: infinity
Girth of graph 2: 5

Answer 1

http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdfに、複雑さ O(VE) の BFS に基づくアルゴリズムがあります。これは無向グラフ用です (たとえば、隣接行列の例は対称です)。https://github.com/jaspervdj/Genus/blob/master/src/genus/FindGirth.javaも参照してください。

Answer 2

このアルゴリズムは、最短サイクルの長さを見つけます。

- set `girth` to infinity
- for each edge
-- remove the edge from the graph
-- measure the distance between the edge endpoints
-- if `girth` is longer than distance+1
--- set `girth` to distance+1
-- return the edge to the graph.

ダイクストラ アルゴリズムの時間計算量はです。O(v^2)したがって、このアルゴリズムはですO(v^4)。

グラフがまばらな場合は、隣接リスト表現に変換してから、前のアルゴリズムをO(v^2+e*(e+v*log(v)))=で実行できます。O(v^2+e^2+v*e*log(v))

Answer 3

セージで

sage: G1 = Matrix([[0,1,0,0],[1,0,0,1],[0,0,0,0],[0,1,0,0]])
sage: G2 = Matrix([[0,1,0,0,1],[1,0,1,0,0],[0,1,0,1,0],[0,0,1,0,1],[1,0,0,1,0]])
sage: G1 = Graph(G1)
sage: G2 = Graph(G2)
sage: G1.girth()
+Infinity
sage: G2.girth()
5

Answer 4

グラフのガースは、グラフに含まれる最短のサイクルの長さです。つまり、合計が最小になるサイクルです (グラフに負のサイクルがある場合は、負になる可能性があります)。胴回りを見つける最も簡単な方法は、与えられたグラフ (V<= 400 を持つ) に対してフロイド ウォーシャル アルゴリズム (O(V^3) 時間) を実行し、すべてのペア間の距離を 2 次元配列に格納することです。その後、可能なすべての頂点 (O(V) 時間) に対して dist[i][i] を繰り返し、頂点 i で始まり頂点 i で終わるサイクルが存在するかどうかを確認し、すべての最小値を取ります。 dist[i][i] から得られる可能な値。

Answer 5

すべてのポイントからダイクストラを実行し、その特定のソースからの最大距離を各ラウンドで取得すると、(O(v^3)) 安くなります。次に、これらの要素の最大値を取り、それが胴回りです.