Networks

歡迎來到網絡的世界！

你好！歡迎來到進階數學（Further Mathematics）中最實用且與「現實世界」最貼近的章節之一。你有沒有想過 Google Maps 是如何找到前往朋友家最快的路線，或是像 Amazon 這樣的物流公司如何決定送貨司機該走哪條路才能節省燃油？這正是網絡（Networks）這門學問的精髓所在！

在本章中，我們將學習如何將現實生活中的地圖與連接轉化為數學圖表。如果一開始看起來像是密密麻麻的線條和圓圈，請別擔心——我們會逐步拆解，讓你徹底掌握其中的邏輯。

1. 網絡的語言 (DB1)

在解決複雜問題之前，我們需要先學會它的語言。一個網絡（Network）（也稱為加權圖，Weighted Graph）只是一組由線條連接起來的點。

你需要知道的關鍵術語：
• 節點 (Nodes) 或 頂點 (Vertices)： 這些就是網絡中的「點」。你可以把它們想像成城市、住家或電腦伺服器。
• 弧 (Arcs) 或 邊 (Edges)： 這些是連接節點的「線」。把它們想像成道路、電纜或飛行航線。
• 權重 (Weight)： 這是附在弧上的數字。它代表了一種「成本」，例如距離（公里）、時間（分鐘）或金錢（英鎊）。如果節點 A 和節點 B 之間的弧權重為 5，這可能意味著往返它們之間需要 5 分鐘。

快速回顧：
一個網絡就是一個線條上帶有數字（權重）的圖（Graph）。如果你看到一個包含圓圈和線條的圖表，你看到的其實就是一個網絡！

2. 網絡優化：生成樹 (Spanning Trees) (DB2)

想像你是電纜公司的工程師，你需要連接 5 戶人家，確保它們都有網絡。你不需要在每戶人家之間都鋪設道路，只需要足夠的電纜，讓每戶都能連接到主中心即可。這就是生成樹（Spanning Trees）發揮作用的地方。

什麼是生成樹？
一個樹（Tree）是指沒有循環（沒有迴路！）的圖。一個生成樹則是連接網絡中所有節點的樹。我們的目標通常是找出最小生成樹（Minimum Spanning Tree, MST）——即所有弧的權重總和為最小的那個樹。

如何尋找 MST：
你會用到兩種主要的「食譜」（演算法）：
1. 克魯斯克爾演算法 (Kruskal’s Algorithm)： 觀察整個網絡中的所有弧，始終挑選權重最小的一條，只要它不會形成封閉迴路即可。
2. 普林演算法 (Prim’s Algorithm)： 從一個節點開始，藉由挑選連接「已訪問節點」與「未訪問節點」之間最短的弧，不斷「擴張」你的樹。

比喻：
克魯斯克爾演算法就像一個精打細算的購物狂，查看整個目錄並優先挑選最便宜的路線。普林演算法則像是一個探險家，從家出發，永遠選擇通往一個全新未知領域的最短路徑。

關鍵總結：
要找到最小生成樹，你的最終答案必須使用 \(n - 1\) 條弧連接所有節點（其中 \(n\) 為節點數量），且過程中絕不能形成迴路。

3. 路線檢查：郵差問題 (Route Inspection) (DB3)

現在，想像你是一名郵差。你必須走遍鄰里內的每一條街道去派遞郵件，然後返回分揀辦公室。你希望在走最短距離的情況下完成任務。

目標：
經過每一條弧至少一次，並回到起點。

邏輯：
如果每個節點都有偶數度數（Even Degree）（即從該點發出的線條數量為偶數），你就可以輕鬆做到而不必重複走任何路！這稱為歐拉電路（Eulerian circuit）。
如果有奇數節點（Odd nodes）（線條數量為奇數的節點），你必須重複走某些路。在 AQA 教學大綱中，你通常會處理擁有兩個或四個奇數節點的網絡。

2 個奇數節點的步驟：
1. 找出兩個度數為奇數的節點。
2. 找出這兩個節點之間的最短路徑。
3. 總距離將等於網絡中所有權重的總和 + 這兩個奇數節點之間的最短路徑。

常見錯誤：
學生常忘記將「重複」的路徑加到網絡的總權重中。請務必先計算「所有弧的總權重」！

4. 旅行推銷員問題 (TSP) (DB4)

這聽起來像郵差問題，但其實不同！推銷員不需要走過每一條道路；他們只需要拜訪每一個城市（節點）一次，然後回到起點。

對於電腦來說，要找到 TSP 的絕對完美路線非常困難。因此，我們利用上限 (Upper Bounds) 和 下限 (Lower Bounds) 來縮小答案範圍。

上限 (Upper Bounds)（「足夠好」的路線）

上限是一個我們已知可以實現的距離。找到它的一種常見方法是最近鄰演算法 (Nearest Neighbour Algorithm)：
1. 從一個節點開始。
2. 前往最近且未訪問過的節點。
3. 重複此步驟，直到所有節點都被訪問過。
4. 別忘了：你必須加上返回起點的距離！

下限 (Lower Bounds)（「完美世界」的最小值）

下限是最佳路線不可能短於的數值。我們使用刪除節點法 (Deleted Node Method) 來找到它：
1. 選定一個節點並將其「刪除」（忽略它以及與其連接的所有弧）。
2. 為剩餘的節點找出最小生成樹 (MST)。
3. 找出與被刪除節點相連的兩條最短弧。
4. 下限 = MST 的權重 + 兩條最短弧的權重。

你知道嗎？
最佳解 (Optimal Solution)（即可能的最短路線）永遠會落在你的下限與上限之間。\(Lower Bound \le Optimal \le Upper Bound\)。

5. 評估與優化模型 (DB5)

數學並不總是完美的。在現實世界中，如果發生交通堵塞，10 分鐘的「權重」可能會變動。優化模型 (Refining a model) 意味著調整你的網絡，使其更符合現實。

什麼可能會改變？
• 單行道： 弧可能只能單向通行（有向弧，Directed Arcs）。
• 道路封閉： 如果道路封鎖，弧的權重可能會變成「無限大」。
• 可變成本： 燃料價格或過路費可能會將「權重」從距離轉變為成本。

快速回顧框：
• 生成樹： 以最小成本連接所有節點（無迴路）。
• 路線檢查： 涵蓋所有弧（郵差問題）。
• TSP： 拜訪所有節點並回到起點（推銷員問題）。
• 上限： 我們找到的一條路線（通常使用最近鄰演算法）。
• 下限： 理論上的最小值（使用刪除節點法 + MST）。

如果這些演算法起初讓你覺得枯燥，別擔心。練習在圖表上多描幾次，它們就會變得自然而然！你一定可以做到的！