特定のエッジがすべての可能なmstの1つに含まれているかどうかを確認するアルゴリズムに取り組んでいます。
この質問では、不明瞭な値を検討しており、エッジeは頂点AとBを接続します。
これまでのところ、次のようになっています。エッジeの重み以下の重みを持つエッジで構成されるパスをAからBに作成できる場合、エッジeはMSTの一部ではないと言えます。
私はここで何か/より良いアルゴリズムに関するアイデアを見逃していますか？
編集：
サイクル特性を含むソリューションについての考えは何ですか？したがって、検討しているエッジよりも重みが小さいすべてのエッジを検討します。これらのエッジを使用してA->Bからパスを作成できる場合、それはMSTの一部ではないと言えますか？
これをMST サイクル プロパティを使用して解決します。これは、「グラフ内の任意のサイクル C について、C のエッジ e の重みが C の他のすべてのエッジの重みよりも大きい場合、このエッジはに属することはできません。 MST.」
次に、次のアルゴリズムを実行して、O(E+V)頂点 u と v を接続するエッジ E が MST の一部になるかどうかをテストします。
ステップ1
E よりも重みが小さいエッジのみを考慮して、エッジ E の端点 (u または v) のいずれかから dfs を実行します。
ステップ2
ケース 1 この dfs の最後で頂点 u と v が接続される場合、エッジ E は MST の一部になることはできません。これは、この場合、エッジ E が最大の重みを持つサイクルがグラフに確実に存在し、(サイクル プロパティから) MST の一部になることができないためです。
ケース 2 ただし、dfs の最後で u と v が切断されたままの場合、エッジ E は一部の MST の一部である必要があります。この場合、E は、それが属するすべてのサイクルで常に最大重みエッジではないためです。
この問題についての私の考えを書きます。
ここでは、サイクル プロパティが非常に重要です。任意のサイクルの最大エッジは、最小スパニング ツリー内にあることはできません。
サイクル プロパティを証明するために、サイクルで最大のコスト エッジであるエッジ e を含む最小全域木 T があるとします。次に、ツリー T のエッジ e を削除すると、2 つのセット S と T が得られます。次に、サイクルには、セット S と T を接続する e 以外のエッジが含まれている必要があります。最小スパニング ツリーで。
サイクル プロパティを取得したら、いくつかのエッジ e が最小全域木にあるかどうかを主張します
。エッジ e(v,w) は最小全域木に属していませんこのパス上のすべてのエッジが e より小さい v と w からのパス。
上記の主張を使用すると、アルゴリズムは次のようになります
。e より大きいすべてのエッジを削除すると、グラフ G' が得られます。DFS を実行して、v と w が G' で接続されているかどうかを確認します。v と w がまだ接続されている場合、エッジ e はどの最小全域木にも属していません。v と w が接続されていない場合、エッジ e は最小スパニング ツリー内にあります。
1つのエッジがMSTにあるかどうかを確認するには、代わりに、このエッジをグラフに追加することでサイクルが作成されるかどうかを確認することから始める必要があります。MSTにはサイクルがないことは誰もが知っています。
もしそうなら、少なくとも2つのルートのどちらのルートがより重みが少ないかを把握するだけです。エッジeの重みが最小の場合、それはMSTに含まれている必要があります。そうでない場合、サイクルを形成する可能性のあるエッジであり、グラフに含めるのに最適なエッジではありません。
そうでない場合は、後のエッジが機能して既存のエッジを打ち負かさない限り、MSTに含まれている必要があります。
そうすることで、エッジがMSTにあるかどうかをチェックするO（n）時間を達成できます。
AB がグラフで、e が唯一のエッジであるとします。次に、e は MST の一部ですが、条件に十分なパス AB があります。
e がそのようなパスの一部ではないことを要求したとしても、それは間違っています。A と B の間に同じ重みを持つ 2 つのエッジ e1 と e2 を持つグラフを作成します。
また、すべての辺の重みが 1 である AC からの追加の辺を持つグラフ ABC も考慮する必要があります。どのエッジを削除しても、最小限のスパニング ツリーを取得できます。したがって、任意のエッジを MST の一部にすることができます。