免費開始練習
地特三等申論題 111年 [工業工程] 作業研究

第 一 題

📖 題組：
請回答下列有關最小擴充樹問題（minimum spanning tree problem）： 圖中共有 5 個節點（node），編號 1 至 5。各節線（arc）一側之數字即為節線之長度，例如節線（1,2）之長度為 3。
題組圖片
📝 此題為申論題，共 3 小題

小題 (一)

請說明最小擴充樹問題之定義。（5 分）

思路引導 VIP

看到定義題，應直接從圖論的構成要素切入。拆解『最小』、『擴充（生成）』、『樹』三個關鍵字的數學意義，並補充如『n個節點需選用n-1條邊』的重要特性來爭取滿分。

🤖
AI 詳解
AI 專屬家教

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

小題 (二)

試說明任一種最小擴充樹問題之求解演算法。請明確列出其步驟。（10分）

思路引導 VIP

看到最小擴充樹（MST）問題，應立刻聯想到兩種經典的貪婪演算法：普林演算法（Prim's Algorithm）與克魯斯克爾演算法（Kruskal's Algorithm）。作答時擇一即可，重點在於使用標準的集合符號（如已連通集合與未連通集合）嚴謹定義，並清晰條列每一操作步驟與終止條件。

🤖
AI 詳解
AI 專屬家教

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

小題 (三)

試求解下圖網路之最小擴充樹，請寫出完整的演算步驟。圖中共有 5 個節點（node），編號 1 至 5。各節線（arc）一側之數字即為節線之長度，例如節線（1,2）之長度為 3。（10 分）

思路引導 VIP

看到最小擴充樹（Minimum Spanning Tree）問題，應立刻聯想到克魯斯克爾（Kruskal's）或普林（Prim's）演算法。解題關鍵在於完整展示「邊長排序」與「依序挑選且不形成迴路」的過程，直到選滿 n-1 條邊為止。

🤖
AI 詳解
AI 專屬家教

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

📝 同份考卷的其他題目

查看 111年[工業工程] 作業研究 全題

升級 VIP 解鎖