建立 2026-11-12 更新 2026-11-12

圖論

圖論（graph theory）用「點」與「連線」描述網路關係，例如城市之間的道路、電腦網路、社群好友關係。IB Math AI HL 的圖論重點是三類最佳化問題：用最小生成樹以最低成本連接所有地點、用中國郵差問題找走遍每條路的最短路線、用旅行推銷員問題找拜訪每個地點的最短路線。本頁是 HL 限定內容（課綱 AHL 3.14～3.16）。

圖的基本名詞

握手定理：所有頂點的度數總和 \(= 2 \times\) 邊數，所以奇數度頂點的個數一定是偶數。

走法、路徑與迴路

• 走法（walk）：沿著邊依序經過頂點，可重複。
• 路徑（path）：不重複頂點的走法；迴路（cycle）：回到起點的路徑。
• Euler 路線：每條邊恰好走一次。所有頂點都是偶數度時，存在回到起點的 Euler 迴路；恰有兩個奇數度頂點時，存在 Euler 路徑（從一個奇點走到另一個）。
• Hamilton 迴路：每個頂點恰好經過一次並回到起點。

鄰接矩陣

鄰接矩陣（adjacency matrix）\(A\) 的第 \(i\) 列第 \(j\) 行，記錄頂點 \(i\) 到頂點 \(j\) 的邊數。

• \(A^k\) 的第 \(i\) 列第 \(j\) 行 \(=\) 從 \(i\) 到 \(j\)、長度為 \(k\) 的走法數目。
• 把鄰接矩陣每一行除以該行總和，得到轉移矩陣，可用來模擬在圖上隨機走動（與 Markov 鏈 相同概念）。

最小生成樹

最小生成樹（minimum spanning tree, MST）是連接所有頂點、總權重最小的樹。適用情境：以最低成本鋪設連接所有建築的電纜。

Kruskal 演算法：

1. 把所有邊依權重由小到大排序。
2. 依序選邊，若加入後不會形成迴路就保留，否則跳過。
3. 選到 \(n - 1\) 條邊時停止。

Prim 演算法：從任一頂點出發，每次加入「連接已選頂點與未選頂點」的最小邊，直到所有頂點都被納入。Prim 可直接在權重表格上操作，適合題目給距離表時使用。

中國郵差問題

中國郵差問題（Chinese postman problem，也叫 route inspection problem）：找一條走遍每一條邊、回到起點的最短路線。適用情境：郵差送信、掃街車、道路巡檢。

1. 找出所有奇數度頂點。
2. 若沒有奇點：答案就是所有邊的權重總和。
3. 若有兩個奇點：找它們之間的最短路徑，這段路要重複走。答案 = 總權重 + 該最短路徑長。
4. 若有四個奇點：列出三種兩兩配對方式，各自計算重複距離，取最小的一種。

旅行推銷員問題

旅行推銷員問題（travelling salesman problem, TSP）：找一條拜訪每個頂點恰好一次並回到起點的最短迴路。這個問題沒有快速的精確解法，IB 只要求求出上下界。

• 上界（upper bound）——最近鄰演算法（nearest neighbour）：從起點出發，每次走向最近的未拜訪頂點，最後回到起點。這條迴路的長度是一個上界。
• 下界（lower bound）——刪點演算法（deleted vertex）：刪掉一個頂點，求剩下頂點的最小生成樹權重，再加上被刪頂點最短的兩條邊。

最佳解 \(L\) 滿足：下界 \(\le L \le\) 上界。若上下界相等，就找到了最佳解。

推薦影音

圖論完整講解

簡述：Revision Village 介紹圖論名詞、鄰接矩陣、最小生成樹、中國郵差與旅行推銷員問題，涵蓋本頁全部主題。

中國郵差問題考題解析

簡述：Maths with Lemon 用一道 IB 考題示範找奇點、配對與計算重複路線，對應本頁「中國郵差問題」。

練習題

練習 1～3 使用以下加權圖 \(G\)（權重單位為 km）：

練習 1

(a) 寫出 \(G\) 每個頂點的度數，並驗證握手定理。 (b) 寫出 \(G\) 的鄰接矩陣（不計權重），並求從 A 到 D、長度為 2 的走法數目。

練習 2

用 Kruskal 演算法求 \(G\) 的最小生成樹與總權重。

練習 3

一位巡檢員要從 A 出發，走遍 \(G\) 的每一條路再回到 A。求最短總距離，並說明哪一段要重複走。

練習 4

五個城市之間的距離（km）如下表：

(a) 從 P 出發，用最近鄰演算法求旅行推銷員問題的上界。 (b) 刪除 P，用刪點演算法求下界。 (c) 你能對最佳路線下什麼結論？