普通考試
115年
[電信工程] 計算機概要
第 17 題
有關圖（Graph）的敘述，下列何者錯誤？
- A 擴張樹（Spanning Tree）的總邊數比總節點（Node）數少 1
- B 任何圖的最小成本擴張樹（Minimum Cost Spanning Tree）只有一個
- C 一個圖的最小成本擴張樹（Minimum Cost Spanning Tree）不一定是單源頭、多目的的最短路徑圖
- D 在一圖有 n 個節點（Nnode），計算單源頭、多目的的最短路徑需 $O(n^2)$ 時間
思路引導 VIP
試著想像一個正方形的四個頂點，如果這四條邊的權重（成本）完全一樣（例如都是 10），而我們必須選取其中的三條邊來連接這四個點（形成擴張樹），你覺得選法是否只有一種？這些不同的選法，最後算出來的總成本會不一樣嗎？
🤖
AI 詳解
AI 專屬家教
同學好，這題你觀察得很敏銳！能正確指認出選項 (B) 的錯誤，說明你對**圖論（Graph Theory）中「唯一性」的條件有著清晰的理解。這道題目的鑑別度在於測試學生是否混淆了演算法的結果與限制條件，特別是關於最小成本擴張樹（Minimum Cost Spanning Tree, MCST）**與最短路徑（Shortest Path）之間的細微差別。
擴張樹的唯一性與權重關係
在結構設計或網路規劃中，我們常追求總成本最低。然而，MCST 並非在所有情況下都是唯一的。正確的觀念是：唯有當圖中所有邊的權重（Weight）皆不相同時，MCST 才保證唯一。若存在多條權重相同的邊，我們完全可能透過不同的邊組合，建構出總成本相同但結構不同的擴張樹。至於其他選項，擴張樹必須連接 $n$ 個節點且不含迴圈，故邊數必為 $n-1$；而 Dijkstra 演算法在不使用優先權隊列優化時，時間複雜度確實為 $O(n^2)$，這些都是非常穩健的工程基礎觀念。
▼ 還有更多解析內容