歡迎來到網絡世界！
歡迎來到進階數學（Further Mathematics）中最實用的章節之一！在這一節中，我們將探索網絡（Networks）。如果你曾經使用 GPS 尋找回家的最快路線，好奇過像 Amazon 這樣的物流公司是如何規劃配送路線，又或者想了解互聯網是如何保持連接的，那麼你其實已經接觸過網絡的強大之處了。
學完這些筆記後，你將能掌握網絡的「語言」，找出連接各個地點最高效的方法，並解決關於在不同點之間行進的複雜難題。別擔心一開始會看到很多術語——我們會一步步拆解，讓你輕鬆上手！
1. 網絡的語言
在解決問題之前，我們需要先了解所面對的對象。網絡（有時被稱為權重圖，weighted graph）其實就是一系列由線條連接的點，而這些線條上標有數值。
必須掌握的關鍵術語：
- 節點 (Nodes 或 Vertices)： 這是網絡中的「點」。你可以把它們想像成地圖上的城市或房間裡的電腦。
- 弧 (Arcs 或 Edges)： 這是連接節點的「線」。你可以把它們想像成道路或電纜。
- 權重 (Weight)： 這是分配給每條弧的數值，代表現實世界中的具體度量，例如距離、時間或成本。
現實生活中的類比： 想像一下你所在區域的地圖。節點是商店，弧是連接它們的路徑，而權重則是走過每條路徑所需的時間（分鐘）。
快速複習：
- 節點 (Node)： 一個點。
- 弧 (Arc)： 一條線。
- 權重 (Weight)： 這條線的「代價」。
2. 生成樹與優化
有時候，我們想要用最小的總權重連接網絡中的每一個節點。這被稱為最小生成樹 (Minimum Spanning Tree, MST)。
什麼是生成樹？
樹 (Tree) 是一種沒有「環」（cycles）且所有部分都連通的圖。而生成樹 (Spanning Tree) 則是包含網絡中每一個節點的樹。我們在「優化」過程中的目標，通常就是找到達成此目的最「省錢」（即權重最小）的方法。
為什麼這很有用？
想像你是一家電纜公司，想要為村裡的 10 戶人家提供光纖寬頻。你希望在確保每戶人家都連入網絡的前提下，使用最少量的電纜。這就是典型的 MST 問題！
重點總結：
生成樹連接所有節點且沒有環。為了進行優化，我們要尋找總權重最小的弧集合。
3. 路徑檢查問題 (Route Inspection Problems)
你有沒有看過郵差走遍社區的每一條街道？他們解決的其實就是路徑檢查問題（也被稱為中國郵差問題，Chinese Postman Problem）。
目標：
找出最短路徑，該路徑必須經過每一條弧至少一次，並最終回到起點。
解題步驟：
- 檢查度數 (Degrees)： 查看每個節點並計算連接到它的弧的數量，這就是度數。
- 找出奇數節點： 如果所有節點的度數都是偶數，則該網絡是歐拉圖 (Eulerian)。你可以不重複地走過每一條弧！
- 配對奇數節點： 如果存在度數為奇數的節點（奇數節點的總數一定是偶數！），你必須重複連接它們之間的最短路徑，使它們變為「偶數」。
- 計算總權重： 總權重 = (所有弧的總和) + (重複的最短路徑權重)。
常見錯誤： 同學們經常忘記尋找奇數節點之間最短的路徑。如果你有兩個奇數節點 A 和 B，最短路徑可能並非直接連接它們的弧，而是經過節點 C 的路徑！
4. 旅行推銷員問題 (The Travelling Salesperson Problem, TSP)
這是一個經典問題！推銷員需要造訪網絡中的每一個節點並回到起點，但同時希望總距離越短越好。
上限與下限
TSP 對於大型網絡來說，要找到完美解非常困難。因此，我們通常會找出一個數值範圍，讓答案落於其中。
1. 上限 (尋找「足夠好」的路線)
我們使用最近鄰算法 (Nearest Neighbour Algorithm)：
步驟 1： 從任意節點開始。
步驟 2： 前往最近且尚未造訪過的節點。
步驟 3： 重複上述步驟直到造訪所有節點，最後回到起點。
注意： 這給出了最佳路線的一個最大可能值。真正的最佳路線長度將等於或小於此值。
2. 下限 (尋找「底線」)
為了找到下限，我們使用刪除節點法 (Deleted Node Method)：
步驟 1： 刪除一個節點及所有連接到它的弧。
步驟 2： 為剩餘的節點找出最小生成樹 (MST)。
步驟 3： 加上剛剛被刪除的節點所連接的兩條最短弧的權重。
注意： 真正的最佳路線長度將等於或大於此數值。
記憶小撇步：
- 上限 (Upper Bound)： 把它看作「天花板」。我們知道答案不會比這更糟。
- 下限 (Lower Bound)： 把它看作「地板」。我們知道答案不可能比這更好。
5. 評估與完善模型
在進階數學中，我們不只是「做算術」，更要思考這些數學模型在現實世界中是否合理。
修改模型：
別擔心這看起來很複雜；這主要取決於常識！ 當我們用網絡來代表現實時，可能需要進行調整，因為：
- 單行道： 弧可能只能單向通行（有向弧）。
- 交通/施工： 權重（時間）可能會根據一天中的不同時段而改變。
- 實用性： 數學上的最短路徑可能會包含大型貨車無法轉彎的路口。
你知道嗎？ 完善模型是一個循環。你建立模型、檢驗它是否有效、找出缺陷，然後更新權重或弧以使其更準確。
章節總結：
DB1： 節點是點，弧是線，權重是數值。
DB2： 生成樹在沒有環的情況下連接所有點。
DB3： 路徑檢查覆蓋每一條弧（郵差問題）。
DB4： TSP 覆蓋每一個節點（推銷員問題）。使用最近鄰法求上限，刪除節點法求下限。
DB5： 務必檢查你的網絡模型是否符合現實生活中的限制條件。