試題詳解

49 擴展樹（Spanning Tree）是圖形理論（Graph Theory）中的一種運用。擴展樹是以最少的邊數來連接圖形中所有的頂點，若圖形中的每一個邊加上一些數值當作權重（Weight），這樣的權重可以是成本（Cost）或距離（Distance）。雖然一個圖形可能會有許多的擴張樹，但若考慮每個邊上的權重（或成本），我們可以找到一個最小成本的擴張樹（Minimum Cost Spanning Tree）。以下的圖形，G=(V, E)，V 是頂點，V={1, 2, 3, ..., n}，E 是連接兩個頂點的邊，邊上的數值代表權重（或成本）。請問下圖中，關於這個圖形的最小成本擴張樹（從頂點 1 開始出發），下列何者正確？

(A)頂點 4 跟頂點 7 的邊包含在這個最小成本擴張樹中
(B)最小成本擴張樹所有權重總和為 50
(C)頂點 5 跟頂點 7 的邊包含在這個最小成本擴張樹中
(D)最小成本擴張樹所有權重總和為 48