次のことを証明してください。
G=(V,E) エッジに負でない重みを持つ無向連結グラフです。 みましょう T のMSTになる G そして T" の木になる G （最低限ではない） Weight(T") > Weight(T)。で最も重いエッジの重みが T" 最も重いエッジの重みよりも小さい T.
どうすればいいかわかりませんが、 e(u,v) - heaviest edge on T そして e"(u",v") - heaviest edge on T" そしてで定義されたカットを見ると (u,u") Kruskal algorithemを使ってそれを示すことができる e" であることが選択されていません T またはこの方向の何か...
ありがとうございました、
回答：
回答№1は4反対を仮定してください - 加重が存在します最小全域木Ｔおよび全域木Ｔを有する無向グラフであり、「Ｔの最も重い辺がＴの最も重い辺より重い」、すなわちＴの最も重い辺がより重い。 すべて T "の辺"＃：。 Ｔ”の最も重いエッジｈを削除することによって引き起こされるカットを考える。Ｔ”が接続されているので、Ｔ”のあるエッジはこのカットを横切る。この辺をT - hに加えると、Tよりも明るいスパニングツリーが得られます。これは最小スパニングツリーです。矛盾。
回答№2の場合は1
簡単にするために、すべてのエッジの重みを明確にし、MSTが一意になるようにします。最も重いエッジを考えます。 e MSTで、そしてクラスカルアルゴリズムがこのMSTを構築する方法。最後に追加されたエッジは、結果として得られるMSTの中で最も重いエッジです。
最後の辺を追加する直前の状況を見てください。 2本の木からなる森があります。 Kruskalアルゴリズムを使っているので、現在のところ、より安い方法はありません。 e これら二つの木を結ぶために。したがって、他のすべてのスパニングツリーでそれらの間のエッジには、少なくとも次のサイズの重みがあります。 e 持っている。
同じ重みのエッジを適切に処理するには、ある程度の注意、またはおそらく巧妙なアイデアが必要です。