グラフを切断せずに削除できるエッジはありますか？

Question

私が始める前に、はい、これは宿題です。 私はこの14時間のうちにこの問題を解決できるほどの努力を尽くさず、どこにもいないと私はここに投稿しませんでした。

問題は次のとおりです：接続されている無向グラフからエッジを切断することなくO（V）時間でエッジを削除できるかどうかチェックしたいと思います。

サイクルエッジは、グラフを切断することなく除去することができるので、グラフがサイクルを持っている場合、私は単純にチェックしてください。私はこれまで達している何

私は、使用できる2つの方法があります.1つはDFSです。もう1つは、VsとEsを数え、| E | = | V | - 1、それが本当であれば、グラフはツリーであり、切断することなく削除できるノードはありません。

どちらの方法も問題を解決していますが、両方ともO（| E | + | V |）が必要であり、より速い方法があると言われています（おそらく貪欲な方法です）。

ヒントはありますか？

編集： 具体的には、これは私の質問です。与えられたグラフG =（V、E）が与えられていれば、Eの中のいくつかのエッジeを取り除いて、結果のグラフをまだ接続してもよいですか？

Answer 1

グラフの再帰的なトラバーサルは、ノードがマークされているとマークし、既にマークされているノードを実行した場合にショートを返して真を返すようになります。これは、除去可能なエッジがない場合はグラフ全体を横切るためにはO（| V |）をとり、早期に真を返す場合は時間を短縮します。 （| V | + | E |）編集

はい

、グラフ全体のrecusiveトラバーサルがO要求する時間は、ないサイクルが存在しない場合、我々は唯一のグラフ全体をトラバース - その場合、 | E | = | V | -1そして、それはO（| V |）時間だけかかる。サイクルがある場合は、せいぜい| V | （そして| V | +1個のノードを訪問する）、これは同様にO（| V |）時間を要する。

また、（最初のノード以外の）ノードからトラバースする場合、ノードに到達するために使用したエッジは考慮されていないため、既に訪問済みのノードがすぐに表示される可能性があります。

Answer 2

私が読んでいるところでは、繰り返しのないDFSはO（| V |）と見なされますので、エッジeを取って接続する2つの頂点をuとvとします。 eが、vが発見された場合、eがブリッジではないと推測できます。繰り返しなしのDFSがO（| V |）ならば、これはO（| V |）と見なされます。

Answer 3

すべてのエッジEをリストし、エッジを取得し、訪問された2つの終了頂点を1つずつマークします。横断中に、2つの頂点が以前にいくつかの辺によって訪問されており、その辺を削除できることが分かりました。

ほとんどの場合、エッジ| V |この条件が満足するかどうかを見る時間。

最悪の場合はこのようになるかもしれません。私たちがエッジを取るたびに、少なくとも新しい頂点を訪問します。そして、| V |頂点と| V |特定のエッジのエッジを見つけることができます。

ベストケースは、| V |/2 + 1 e