algorithm - 最小全域木に線形時間のエッジが含まれているかどうかを調べますか？

Question

宿題に次の問題があります。

O（n + m）アルゴリズムを与えて、エッジeがグラフのMSTの一部であるかどうかを確認します

（この割り当てについて他の人から助けを得ることが許可されているので、これは不正行為ではありません。）

BFSを実行して、このエッジが2つのレイヤー間のエッジであるかどうか、もしそうであれば、このエッジがこれらのレイヤー全体で最小であるかどうかを確認できると思います。しかし、このエッジがBFSツリーのツリーエッジではない場合、私は何を言うことができますか？

Answer 1

ヒントとして、エッジがそれを含むサイクルの中で最も重いエッジでない場合、そのエッジを含むMSTがいくつかあります。これを確認するには、MSTを検討してください。MSTにすでにエッジが含まれている場合は、すばらしいです。終わったね。そうでない場合は、エッジをMSTに追加します。これにより、グラフにサイクルが作成されます。次に、そのサイクルで最も重いエッジを見つけて、グラフから削除します。これですべてが接続されたままになります（2つのノードがそのエッジを通過するパスで接続されていた場合、サイクルを逆に回るだけで接続できるようになりました）。さらに、削除されたエッジのコストは問題のエッジのコストよりも小さくなかったため（エッジはサイクル内で最も重いエッジではないため）、このツリーのコストはこれより大きくすることはできません。前。MSTで開始したため、MSTで終了する必要があります。

このプロパティを使用して、線形時間の任意のサイクルでエッジが最も重いエッジであるかどうかを確認できます。

Answer 2

これは、 MSTサイクルプロパティを使用して解決します。「グラフ内のどのサイクルCでも、Cのエッジeの重みがCの他のすべてのエッジの重みよりも大きい場合、このエッジはMST。」

次に、次のアルゴリズムを実行して、O(E+V)頂点uとvを接続するエッジEがMSTの一部になるかどうかをテストします。

ステップ1

エッジEのエンドポイントの1つ（uまたはv）からdfsを実行します。これは、Eよりも重みが小さいエッジのみを考慮したものです。

ステップ2

ケース1 このdfsの最後で、頂点uとvが接続されている場合、エッジEを一部のMSTの一部にすることはできません。これは、この場合、エッジEが最大の重みを持つサイクルがグラフに確実に存在し、MSTの一部になることができないためです（サイクルプロパティから）。

ケース2 ただし、dfs uとvの終了時に切断されたままの場合、エッジEはMSTの一部である必要があります。この場合、Eは、その一部であるサイクルの最大ウェイトエッジではありません。

Answer 3

uとvへのサイクルを作成する現在のパス（u、v）よりも安価なパスがあるかどうかを調べます。ある場合は、（u、v）はmstにありません。そうでなければそうです。これは、カットプロパティとサイクルプロパティによって証明できます。