申論題

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

原因：

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

詳細說明：

1. Kruskal 算法：

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

2. Prim 算法：

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

總結：

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

如果邊權重不唯一：

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

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

• 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。

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