G =（V、E）を重み付きの接続された無向グラフとし、Tを最小全域木とします。eをEにない（そして重みW（e）を持つ）任意のエッジとします。証明または反証：TU {e}は、G'=（V、EU {e}）の最小全域木を含むエッジセットです。
まあ、それは私には真実に聞こえるので、私はそれを証明することに決めましたが、私は毎回立ち往生しています...
たとえば、eが最小の重みを持つ新しいエッジである場合、Tのエッジが、Eの他のエッジの「ヘルプ」なしで新しい最小の重みを取得するのを妨げるような悪い方法で選択されていないことを約束できます。 -T？
助けていただければ幸いです。よろしくお願いします。
[ a (1), a(2), ..., a(n-1)]をEから選択されたエッジのシーケンスとし、クルスカルのアルゴリズムによってGのMST を構築します (選択された順序で -重み (a (i)) <= 重み(a(i + 1)) )。
入力E' = EU {e}として与えられたときにクルスカルのアルゴリズムがどのように動作するかを考えてみましょう。i = min { i: weight(e) < weight(a(i))} とします。最初に、アルゴリズムはエッジ[a(1), ..., a(i - 1)]を選択することを決定します( eはまだ処理されていないため、同じように動作します)。次に、 eを決定する必要があります- eが削除された場合、 E' のソリューションはEの場合と同じになります。したがって、アルゴリズムによって選択された最初のi個のエッジが[a(1), ..., a(i - 1), e] であると仮定しましょう。この新しいシーケンスを a'と呼びます。アルゴリズムは継続 - 次の選択 (j > i の場合) が満たされる限りa'(j) = a(j - 1)私たちはクールです。このような素晴らしいストリークを破る 2 つのシナリオがあります (ストリークがインデックスk + 1で破るとしましょう):
1) アルゴリズムは、 Tにないエッジ e'とweight(e') < weight(a(k+1))を選択します。今までのシーケンスは次のとおりです。
[a(1), ..., a(i-1), e, a(i), a(i+1), ..., a(k-1), a(k), e']
しかし、このリストにe'を追加できる場合は、 [a(1), ..., a(k-1), a(k)]に追加することもできます。しかし、クラスカルのアルゴリズムは、 Gの MST を探すときにそれを行いませんでした。それは矛盾につながります。
2) 慎重に選択されたアルゴリズム:
[a(1), ..., a(i-1), e, a(i), a(i+1), ..., a(k-1), a(k)]
しかし、エッジa(k+1)をドロップすることにしました。しかし、eがリストに存在しない場合、アルゴリズムはa(k+1)を追加することを決定します。つまり、グラフ(V, {a(1), ..., a(k)}) では、エッジa(k+1)はエッジeと同じコンポーネントを接続します。つまり、 GとG'の両方の場合にアルゴリズム エッジa(k + 1)を考慮した後、接続されたコンポーネント (選択されたエッジのセットによって決定される) への分割は同じになります。したがって、(k+1)アルゴリズムの処理後は、どちらの場合も同じように処理されます。
ノードを追加せずにエッジがグラフに追加されると、そのエッジはグラフの最小スパニング ツリーにサイクルを作成します。サイクルの長さは 2 から n まで変化する場合があります。ここで、n はグラフ内のノードの数です。T = G の最小スパニング ツリー (T + 追加されたエッジ) の MST を見つけるには、そのサイクルから 1 つのエッジを削除するだけで済みます。最大の重みを持つエッジを削除します。
したがって、T' は常に TU {e} から来ます。
そして、これが新しい MST が TU {e} のエッジ セットになることを証明しないと考えている場合は、新しいグラフのクラスカル アルゴリズムを分析してください。つまり、e が最小の重みの場合、MST acc to Kruskal アルゴリズムに選択されている必要があり、最小の場合はサイクルから削除できません。