G=(V,E)は、エッジに負の重みを持たない無向グラフです。 TをGとT'のスパニングツリーにすると、G（少なくとも1つではない）なので、Weight(T') > Weight(T)を保持します。証明するのは、T'にある最悪の辺の重みが、最も重い辺の重みよりも小さくないことです。T。最小スパニングツリーのプロパティを証明してください
私たちは(u,u')によって定義されたカットを見れば、我々はその後、e(u,v) - heaviest edge on Tとe'(u',v') - heaviest edge on T'を聞かせている場合、我々はクラスカルのalgorithemを使用することができますし、e'がTかになるように選択されていないことを示してもよい、これをapprochするかどうかはわかりませんこの方向のもの...
ありがとう、
逆の仮定 - Tの最も重いエッジがT 'の最も重いエッジ、すなわち最も重いエッジよりも重くなるように、スパニングツリーTとスパニングツリーT'を持つ重み付け無向グラフが存在すると仮定します。 Tは、よりも重く、すべてエッジがT 'にあります。 Tの最も重いエッジhを削除することによって誘発されるカットを考慮する.T 'が接続されているので、T'のエッジがこのカットを横切る。このエッジをT - hに加えると、最小スパニングツリーであるTよりも軽いスパニングツリーが得られます。矛盾。
私は別の方向に向いています。簡単にするために、MSTが一意であるように、すべてのエッジウェイトを区別します。 MSTの最も重いエッジeと、KruskalアルゴリズムがこのMSTを構成する方法を考えてみましょう。最後に追加されたエッジは、結果として生じるMSTの中で最も重いエッジです。
最後のエッジを追加する直前の状況を確認します。私たちは2本の木からなる森を持っています。 Kruskalアルゴリズムを使っているので、現在のところ、この2つのツリーを接続するには、eよりも安価な方法はありません。したがって、他のスパニングツリーのエッジ間には、少なくともeと同じ大きさの重みがあります。
同じ重量のエッジには、適切に処理するための注意や巧妙な考えが必要です。