無向グラフに奇数長のサイクルがあるかどうかをチェックする方法

Question

接続された グラフが奇数の周期を持つかどうかを調べるために、O（| V | + | E |）時間アルゴリズムを探しています。

私は、グラフ上で幅優先検索を行い、同じ色でラベル付けされた2つの頂点が隣接しないように頂点を白黒にラベル付けしようと考えています。

線形時間でこの問題を解決する既知のアルゴリズムはありますか？

Answer 1

あなたのアプローチは正しいです。それ以上はできません。

BFSを実行中に頂点に深さを付けてラベル付けすると、すべての辺が同じラベルまたはラベルが1つずつ接続されるためです。同じラベルを接続するエッジがある場合、奇数サイクルが存在することは明らかです。そうでなければ、すべての奇妙なラベルを白く、すべての偶数のラベルを黒色にすることができます。

Answer 2

また、DFSを使用して頂点に番号を付けることもできます。

1. 頂点 'S' とクロック= 1
2. スタート、 "訪問" と（S）探検呼び出しとしてマーク

（U）を探検

1. uがすでに訪問されている場合、（clock-Num [u]）が奇数の場合、奇数サイクルである

   「訪問した」と「u」をマーク

2. Num [u] = clock ++;

   i) Explore(v) 
       ii) clock=Num[u] 
   

   初期において

Answer 3

Uのすべての隣接ノードvについて

、あなたはまた、[S] = 0民を設定する必要があります。