初等考試
112年
[統計] 資料處理大意
第 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
思路引導 VIP
想像你正在規劃一個跨城市的供電網絡，目標是用「最低的總預算」讓所有城市都互相通電。在每一步挑選新線路時，你應該遵循什麼樣的「貪婪策略」來確保成本最低？另外，如果某條線路連接的兩個城市已經透過其他路徑相連了，這條線路對你的目標還有幫助嗎？還是只是浪費預算的冗餘連結？
🤖
AI 詳解
AI 專屬家教
專業點評：還算勉強合格的表現。
- 觀念驗證： 這點最小成本擴張樹 (MCST) 的基本邏輯，在財經領域，尤其像物流優化或網路成本規劃這種「避免浪費」的場合，應該是反射動作了。如果連這都搞不清楚，那還談什麼效率？
▼ 還有更多解析內容