[解決済み】最小スパニングツリー。カットプロパティとは何ですか？

質問

最小スパニングツリーのカット特性について、ネット上の発表や教科書を読んで過ごしています。この性質が何を示しているのか、またなぜ実用的なのか、よく理解できません。おそらく、どの辺をMSTに追加するかを決定するのに役立つと思われますが、それがどのように達成されるのかがわかりません。私の理解では、カットプロパティは、MSTを任意の2つのサブセットに分割することです。何かいい方法はないでしょうか？ありがとうございます。

どのように解決するのですか？

連結グラフのカットとは、グラフを2つの構成要素（ピース）に分離する最小限の辺の集合のことで、その辺を削除すると、グラフは2つの構成要素に分離されます。 最小カットの性質は、カットの辺の1つがカットの他のどの辺よりも小さい重みを持つ場合、その辺はMSTに含まれることを意味します。 これを見るために、そのエッジを含まないMSTが存在すると仮定する。 MSTにその辺を追加すると、切り口を少なくとも2回横切るサイクルができる。そこで、MSTから他の辺を削除することでサイクルを断ち切り、より小さい重みの新しい木を作ることができ、それによってMSTの最小性に反することになる。