六、若 G =（V,E）是一加權無向連接圖（undirected weighed connected graph） ， 且各邊的權重均不相等，則其最小生成樹（minimum spanning tree）是否唯一？如不是請舉一反例，如是請說明原因。（10 分）

詳解 (共 1 筆)

詳解 提供者：hchungw

是的，如果 G=(V,E)G = (V, E)G=(V,E) 是一個加權無向連接圖，且各邊的權重均不相等，那麼其最小生成樹（Minimum Spanning Tree, MST）是唯一的。

原因：

當所有邊的權重都不相等時，最小生成樹的邊選擇是唯一的。這是因為在每一步選擇邊時，總是有一條唯一的最小邊，沒有兩條邊具有相同的權重。因此，無論使用 Kruskal 算法還是 Prim 算法，都會產生同樣的一組邊，從而形成唯一的最小生成樹。

詳細說明：

  1. Kruskal 算法：

    • Kruskal 算法按照邊的權重從小到大排序，然後逐一選擇邊，確保不形成環。
    • 由於所有邊的權重都不相等，每次選擇的邊都是唯一的最小邊，因此最小生成樹是唯一的。

  2. Prim 算法：

    • Prim 算法從某個起點開始，逐步選擇連接當前樹的最小權重邊，直到所有節點都被包括在內。
    • 由於邊的權重不相等，每次選擇的邊都是唯一的最小邊，因此最小生成樹也是唯一的。

總結：

在權重不相等的加權無向連接圖中，由於每條邊的權重都是唯一的，因此每次選擇邊時不會有權重相同的選擇，從而確保最小生成樹是唯一的。

如果邊權重不唯一：

如果邊的權重不唯一，那麼最小生成樹可能不唯一。例如，考慮以下圖形：

V={A,B,C,D}V = \{A, B, C, D\}V={A,B,C,D} E={(A−B,1),(A−C,1),(B−C,2),(B−D,3),(C−D,3)}E = \{(A-B, 1), (A-C, 1), (B-C, 2), (B-D, 3), (C-D, 3)\}E={(A−B,1),(A−C,1),(B−C,2),(B−D,3),(C−D,3)}

這個圖的最小生成樹可以有不同的組合。例如：

  • A−BA-BA−B, A−CA-CA−C, B−DB-DB−D
  • A−BA-BA−B, A−CA-CA−C, C−DC-DC−D

兩者都是最小生成樹，因為它們的總權重相同，都是 1+1+3=51 + 1 + 3 = 51+1+3=5。

但在給定條件下（即所有邊的權重都不相等），最小生成樹是唯一的。