0

G = (V, E) を重み付き連結無向グラフとします。G に 2 つの異なる MST があるかどうかを判定する効率の良いアルゴリズムを説明してください。

私がすでに解決した前の問題は、はるかに簡単でした: G に MST が 1 つだけ存在するかどうかを決定する効率的なアルゴリズムを説明してください。

これが私が後者の質問を解決した方法です：

Kruskal アルゴリズムを実行し、新しい MST のエッジを青で、残りのエッジを赤で色付けします。

次に、これまでに見た (Kruskal を使用する) 別の単純なアルゴリズムを使用しました。このアルゴリズムは、最大数の赤いエッジを含むグラフ内の MST を見つけます。つまり、エッジの色に関係なく、グラフ G 内の MST であり、他のすべての MST には、アルゴリズムが検出した MST よりも多くの赤いエッジを含めることはできません。

これで、アルゴリズムが同じ MST (すべての青いエッジを含む) を見つけた場合、MST は 1 つだけになります。

ここでのもう 1 つの質問は、もっと複雑に思えます。上記のアルゴリズムを使用してみましたが、他のさまざまなトリックも使用しようとしましたが、どちらも機能しませんでした。

ところで、グラフ内の異なる MST の数をカウントするアルゴリズムがあると聞いたことがありますが、それは実際にはやり過ぎであり、単純なアルゴリズムを提供するよう求められました。

助けていただければ幸いです、ありがとう

4

1 に答える 1

0

私はそれを過小評価しているかもしれませんが、あなたのアプローチは不必要に複雑に思えます。2 つの異なる MST があるかどうかを判断するには、まず Kruskal を実行して最初の MST を取得します。次に、もう一度実行して、最初の MST から優位に立つことを回避できるかどうかを確認します。

Kruskal の各ステップで、以前は接続されていなかった 2 つのコンポーネントを接続する最も安価なエッジを追加します。したがって、エッジを重みで並べ替えて実行し、2 つの接続されていないコンポーネントを接続する場合は MST に追加する必要があります。複数の MST がある場合、同じコンポーネントを接続する同じウェイトの 2 つのエッジから選択するポイントに到達します。

Kruskal を 1 回実行すると、MST にどのエッジがあるかがわかります。2 回目に実行すると、エッジを重みで再度ソートし、最も安価なエッジ (2 つの接続されていないコンポーネントを接続するエッジ) をグラフに追加します。ただし、同じコンポーネントを接続する 2 つのエッジを追加する選択肢が得られた場合は、最初に取らなかったエッジを取ることができます。最終結果は、異なる MST (1 つのエッジを含まない) になりますが、完全にクルスカルのルールに従って操作したため、有効な MST になります。

基本的にクルスカルを行うだけですが、同じウェイトのエッジのタイ ブレーカーを変更します。この手順を繰り返して、さらに異なる MST を見つけます。MST が 2 つしかないかどうかを知りたい場合は、3 つ目の MST を探してみてください。

于 2013-03-11T12:44:42.143 に答える