いくつかのエッジが修正されている場合、MSTのKruskalのような標準的なアプローチが使用できますか？

Question

問題：グラフの最小スパニングツリー（すなわち、グラフ内のエッジの集合Sは、それぞれの頂点と一緒にS内のエッジがツリーを形成するようにする必要があります;さらに、そのようなすべての集合から、 Sにおける全てのエッジのコストの最小値は最小でなければならない）。しかし、キャッチがあります。

つまり、固定エッジの開始セットを含むグラフのMSTを見つけます。

私のアプローチ：標準的なKruskalのアルゴリズムですが、何か他のものがすべての頂点を固定エッジの集合で指し示す前に結合する前に。つまり、K = {1,2}, {4,5}私はKruskalのアルゴリズムを適用しますが、最初に独自の個々のノードを設定するのではなく、ノード1とノード2が同じセットにあり、ノード4とノード5が同じセットに含まれています。

質問：これは機能しますか？常に正しい結果が得られるという証拠はありますか？そうでない場合は、誰も反例を提供できますか？

P.S.問題は1つのMSTを見つけることだけを問い合わせる。すべてに興味がありません。

Answer 1

はい、最初のエッジセットがサイクルを形成しない限り機能します。

固定したエッジがグラフ内のMSTの一部ではない可能性があるため、結果のツリーの重みが最小ではないことに注意してください。しかし、それらの固定されたエッジがツリーの一部であるという制約を満たす最も軽いスパニングツリーが得られます。それを実装する方法

：

これを実装するには、単にあなたが修正する必要があるエッジのエッジの重みを変更することができます。グラフの中で一番小さいエッジウェイト、たとえばmin_wを選択して1を引いて、この新しいウェイトを割り当てます。 （min_w-1）を修正する必要があるエッジまで移動します。次に、このグラフでKruskalを実行します。

それが動作する理由：（これらは今最軽量であるため）

明らかにクラスカルは、グラフ内の他のエッジを選ぶ前に、あなたが必要とするすべてのエッジを選択します。 Kruskalが終了すると、得られた辺の集合はG '（重みを変更したグラフ）のMSTになります。固定された辺の値だけを変更したので、アルゴリズムは決して他の辺（固定された集合の一部ではない辺）で異なる選択をしたことはありません。Kruskalがエッジのソートされたリストとして考えるエッジを考えると、修正する必要があるエッジの値を変更すると、これらのエッジがリストの前面に移動しますが、他のエッジの順序は変更されません。リストはお互いに関係しています。

注：ご存知のとおり、エッジに最も軽い重量を与えることは、基本的には提案するものと同じです。しかし、なぜそれが動作するのかを考えるのはちょっと難しいと思います。あなたが好きなものを選んでください。

---

このアルゴリズムは、（1は通常、単一のノードで始まる初めに）現在の連結成分から徐々にスパニングツリーを展開するので、私は、プリムお勧めしません。より大きなコンポーネントに参加する場合（固定されたエッジがすべて単一コンポーネント内にあるわけではない可能性があるため）、個別に処理する必要があります。困難ではないかもしれませんが、処理する必要があります。 OTOH with Kruskalあなたは何も適応させる必要はありませんが、通常のアルゴリズムを実行する前にグラフを少し操作するだけです。

Answer 2

接続されたコンポーネントを結果のスパニングツリー（残りの孤立したノード）で発生する必要があるエッジに正確に初期化することができるので、Prim's algorithmがより適切です。 。所望のエッジにはサイクルを含めることはできません。そうでなければ、それらを含むスパニングツリーはありません。

明らかに、コスト最小の方法で2つのフォレストを接続するエッジを見つけるために使用できることが明示されているように、Kruskal's algorithmも使用できます。

大まかに言って、与えられたグラフのフォレストがMatroidのように、欲張りのアプローチでは、最初にindependent setに関係なく、望ましい結果（つまり重み最小木）が得られます。