阿摩線上測驗
17 有關圖（Graph）的敘述，下列何者錯誤？
(A)擴張樹（Spanning Tree）的總邊數比總節點（Node）數少 1
(B)任何圖的最小成本擴張樹（Minimum Cost Spanning Tree）只有一個
(C)一個圖的最小成本擴張樹（Minimum Cost Spanning Tree）不一定是單源頭、多目的的最短路徑圖
(D)在一圖有 n 個節點（Nnode），計算單源頭、多目的的最短路徑需 O(n2)時間
答案：登入後查看
統計： A(4), B(16), C(4), D(3), E(0) #3966681
統計： A(4), B(16), C(4), D(3), E(0) #3966681
詳解 (共 1 筆)
mk010226
#7448879
我們來檢視各選項：
-
(A) 擴張樹（Spanning Tree）的總邊數比總節點數少 1 → ✔ 正確。樹的基本性質：若有 n 個節點，邊數必為 n−1。
-
(B) 任何圖的最小成本擴張樹（Minimum Cost Spanning Tree）只有一個 → ✘ 錯誤。若邊權重有相同值，可能存在多個不同的最小成本擴張樹。並非唯一。
-
(C) 一個圖的最小成本擴張樹不一定是單源頭、多目的的最短路徑圖 → ✔ 正確。MST 與最短路徑樹是不同概念，MST 追求總邊權最小，而最短路徑樹追求從源點到各節點的最短路徑。
-
(D) 在一圖有 n 個節點，計算單源頭、多目的的最短路徑需 O(n²) 時間 → ✔ 正確。以 Dijkstra 演算法（使用鄰接矩陣）為例，時間複雜度為 O(n²)。
ㅤㅤ
✅
0
0
