有關圖（Graph）的敘述，下列何者錯誤？

題目

有關圖（Graph）的敘述，下列何者錯誤？ A. 擴張樹（Spanning Tree）的總邊數比總節點（Node）數少1 B. 任何圖的最小成本擴張樹（Minimum Cost Spanning Tree）只有一個 C. 一個圖的最小成本擴張樹（Minimum Cost Spanning Tree）不一定是單源頭、多目的的最短路徑圖 D. 在一圖有n 個節點（Nnode），計算單源頭、多目的的最短路徑需O(n2)時間

官方答案

• 答案：B. 任何圖的最小成本擴張樹（Minimum Cost Spanning Tree）只有一個

解析

最小成本擴張樹（MST）不一定唯一，例如三節點構成正三角形、三邊等長時，任取兩邊都是 MST，故 B 錯誤。擴張樹含 n 個節點時邊數為 n-1；MST 只保證總成本最小，不保證是單源頭多目的的最短路徑樹；以 Dijkstra 求單源最短路徑需 O(n²) 時間。A、C、D 敘述正確。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。