? asked in 教育與參考考試 · 1 decade ago

演算法Minimum-Cost Spanning Tree

題目是Minimum-Cost Spanning Tree,weighted graphs uniqe?why?

請幫忙...

1 Answer

Rating
  • Leslie
    Lv 7
    1 decade ago
    Favorite Answer

    (1)

    若是原來的圖的 edges 的 weights 是唯一的 (即, 沒有兩個是相等的),

    則其 Minimum-Cost Spanning Tree (MST, 最小生成樹, 展延樹, 骨架樹) 是唯一的.

    證明如下:

    因為 Prim's 或 Kruskal's 的方法是正確的, 若按照該方法去造 MST,

    當 edges 的 weights 是唯一的時後, 造出的 MST 只有一個, 設為 S.

    假設另一個 spanning tree T 也和它一樣的輕, 則會發現, 存在 S 中一個 edge e

    和 T 中一個不同的 edge f 重量一樣. 這和已知的 "weights 是唯一的" 矛盾.

    (詳細證明見: http://en.wikipedia.org/wiki/Minimum_spanning_tree...

    (2)

    若原來的圖的 edges 的 weights 不是唯一的 (即, 至少有兩個是相等的),

    則其 Minimum-Cost Spanning Tree 不是唯一的.

    譬如, 一個三角形, 三邊等重, 其 MST 就有 三個.

    Source(s): Algorithm textbooks
Still have questions? Get your answers by asking now.