algorithm - MSTのカットの最小重量

Question

Gを、明確なエッジの重みを持つ無向グラフとします。TをGのMSTとします。（u、v）をTの任意のエッジとします。（u; v）がこのカットの最小重みエッジであるようなカット（S; VS）があることを示します。

Answer 1

シュートを与えます。e=（u、v）がTに属する唯一のエッジであるようなカットを考えてみましょう。w（e'）<w（eのカットに別のエッジe'があるとします。 ）、次に、e'とドロップeを含む別のSTを形成することができます。これは、より小さな重みを持ち、ばかげています。

Answer 2

|V|から始めます カット。すべてのループで2つのカットをマージします。最終的に1カットになります。MSTは、このカットのエッジのサブセットです。したがって、すべてのマージについて、そのカットのライトエッジ（u、v）（の1つ）を選択しました。最後に、| V|-1のエッジがあります。逆に、ツリーのすべてのエッジには、「ブリッジ」されたカットがあります。したがって、エッジ（u、v）がMSTにある場合、それがライトエッジであったことに対応するカット（S、VS）があります。