data-structures - 最小スパニング ツリー: Cut プロパティとは正確には何ですか?

Question

私は、最小全域木の切断特性に関するオンライン プレゼンテーションや教科書を読むことに多くの時間を費やしてきました。何を説明しようとしているのか、あるいはなぜそれが実用的なのかさえ、私にはよくわかりません。おそらく、MST に追加するエッジを決定するのに役立つと思われますが、それがどのように達成されるかはわかりません。これまでのところ、カット プロパティについての私の理解では、MST を 2 つの任意のサブセットに分割するということです。ここで何か助けはありますか？ありがとう！

Answer 1

連結グラフのカットは、エッジの最小セットであり、そのエッジを削除すると、グラフが 2 つのコンポーネント (ピース) に分離されます。最小カット プロパティは、カットのエッジの 1 つがカット内の他のどのエッジよりも重みが小さい場合、それは MST にあることを示します。これを確認するには、エッジを含まない MST があると仮定します。エッジを MST に追加すると、カットを少なくとも 2 回交差するサイクルが得られるため、MST からもう一方のエッジを削除することでサイクルを破ることができます。 MST。