グラフ内の非循環の切り捨て

Question

グラフのG =（V、E）とVのみの部分集合Fを与えられたとき、Fの各連結成分Sに対して、カット（S、 V \ S）をFに代入します。

なぜ最小ウェイトエッジがFに追加されるたびに、Fは非循環になりますか？

Answer 1

サイクルを作成するには、既に接続されている頂点を接続するエッジを作成する必要があります。

接続されていない頂点間にエッジを追加すると、新しいサイクルは作成されません。接続されていない2つのコンポーネントを接続します。しかし、グラフは非周期的なままです。

どのように動作するかを理解するために、グラフの接続されたコンポーネントを単一の頂点として表現することができます。そして、接続されていないコンポーネント間でエッジを追加すると、頂点だけがマージされます。

ところで、この質問は重み（およびMSTアルゴリズム）とは関係ありません。それはまだ重みなしで有効です。