異なる重みを持つ接続グラフのMSTを見つける

Question

接続されたグラフのMST（最小スパニングツリー）を見つけるためのkruskalとprimのMSTアルゴリズムなどのアルゴリズムが存在することは、皆知っています。

私が知っているもう一つの方法は、サイクルがなくなるまで、グラフの各サイクルから最大値のエッジを削除することです。結果のグラフはMSTになります。グラフの各MSTにグラフの各サイクルの最小エッジが含まれるかどうかは、私が確信している質問です。私たちはこれを証明することができますか？

Answer 1

私はMSTのためのウィキペディアのページでこれに対する答えを見つけることができた：

最小コストのエッジ

グラフの最小コスト辺eが 一意である場合には、このエッジは任意のMSTに含まれます。

証明：eが（大きく コスト）のいずれかを除去し、MSTに含まれていなかった場合には、MSTに電子を追加した後に形成された周期でエッジ小さい重量の スパニングツリーを生じます。