第 一 題

「最小擴充樹問題（Minimum Spanning Tree Problem）」是指在一個給定的連通且具權重（如長度、成本）的無向圖中，尋找一個滿足特定條件的子圖，其特徵包含： (1) 擴充性（Spanning）：所選取的子圖必須連結並包含圖中的「所有節點」。 (2) 樹狀結構（Tree）：為連通圖且「無任何迴圈（Cycle）」產生。若原圖有 $n$ 個節點，則該擴充樹必定恰好由 $n-1$ 條節線所組成。

【破題】 最小擴充樹問題旨在於一個無向連通圖中，找出連結所有節點且總長度（權重）最小的樹結構（不含迴路）。常見的求解演算法有普林演算法（Prim's Algorithm）與克魯斯克爾演算法（Kruskal's Algorithm），以下以「普林演算法」為例說明其標準步驟。 【論述】

【解題思路】利用 Kruskal 演算法（克魯斯克爾演算法）求解，將所有節線依長度由小到大排序，依序加入不形成迴路的節線，直到選取 n-1 條節線為止。 【詳解】 已知：本題網路圖共有 n = 5 個節點，故最小擴充樹（MST）應恰好包含 n - 1 = 4 條節線。