一意の最小スパニングツリー十分かつ必要な条件

Question

十分な必要条件であるグラフGが与えられているので、このグラフに固有の最小スパニングツリーがありますか？また、これらの条件をどのようにプロービングできますか？これまでのところ、私はそれらの条件であること

を発見した：

1）2つのサブセットにV（G）のすべてのパーティションについて、各サブセット内の1つのエンドポイントと最小重量エッジが独特です。

2）Gの任意のサイクルでの最大ウェイトエッジは一意です。

しかし、これが正しいかどうかはわかりません。これが正しい場合でも、その正しさを証明することはできません。

Answer 1

少なくとも最初の条件は不要なので、これは誤りです。証明は反例である（source）。

は、すべてのエッジの重みが1でありそしてGは 一意MST（自体）を有し、それに交差する複数のエッジ 有する任意のパーティションが複数の最小重量エッジを有する任意の木であることGを取ります。

---

EDIT：

変更した質問に対して

...

MSTの一意性のためのよく知られた十分な（必ずしも必要ではない）条件があります：

接続されたグラフの各エッジの重みが異なる場合、グラフには正確に1つの（一意の）最小スパニングツリーが含まれます。

次のように証明は（source）である：

矛盾のために、 Gの二つの異なるMSTSがあると仮定し、T1とT2を言います。 e = v-wをGの最小重みエッジとする。これは、T1またはT2のいずれか一方である であるが、両方ではない。 eがT1にあるとしましょう。 にeを追加すると、T2にサイクルCが作成されます。Cに少なくとも1つのエッジ、たとえばfがあり、T1にない です（それ以外の場合、T1はサイクリックになります）。 eの選択により、w（e）≦ w（f）。すべてのエッジ重みが異なるため、w（e）< w（f）。今度は T2をfでeに置き換えると、T2の最小値に反して、 よりも少ない重みで新しいスパニングツリーが生成されます。

しかし、MSTの一意性のための「十分なと必要な」条件については、私はいずれかが存在することが知られているとは思いません。