G = (V, E) を重み付き連結無向グラフとします。Kruskal のアルゴリズムで成長し、k 回の反復後に停止するエッジ セットを T とします (したがって、T には |E|-1 未満のエッジが含まれる可能性があります)。W(T) をこのセットの加重和とします。T' を |T| となるアシル エッジ セットとする。= |T'|。W(T) <= W(T') であることを証明する
私はアルゴリズムの元の証明を理解しており、これに取り組むためにいくつかのアプローチを試みましたが、どちらもうまくいきませんでした。
例: |T| に関する帰納法を考えました。動作する可能性があります。|T| の場合 = 1 明らかです。
|T|=k の正しさを仮定し、k+1 の正しさを証明します (または…)。矛盾により、|T'|=k+1 かつ W(T') < W(T) となる辺集合 T' が存在するとします。
Kruskal アルゴリズムによって追加された最後のエッジを e とします。したがって、T' の任意のエッジ f について、W(f) < W(e) (そうでない場合、2 つのセットからエッジを削除し、矛盾が発生します)。
これは、T' のすべてのエッジが既に T にあるか、T – {e} でサイクルを形成している場合にのみ発生します。
…</p>
注: クラスカルのアルゴリズムと同じ証明ではありません。T' が接続されているかどうかさえわかりません。
次に何をすべきかわかりません。助けていただければ幸いです、事前に感謝します