歡迎來到圖論演算法 II！

在上一章中，我們學習了如何找出兩個特定點之間的最短路徑（Dijkstra 演算法）。在本章中，我們的角色將從想要從 A 到 B 的「遊客」，轉變為「送貨司機」或「郵差」。

我們要學習的是路徑檢查演算法（Route Inspection Algorithm），它還有一個著名的名稱，叫作中國郵差問題（Chinese Postman Problem）。這裡的目標不僅僅是到達目的地，而是要走遍網絡中每一條邊（edge）至少一次，並回到起點，同時確保總行駛距離最短。

先修知識重溫：節點基礎

在深入研究之前，我們先快速重溫課程早前介紹過的兩個關鍵術語：

  • 度數（Degree 或 Valency）：連接到該節點（node）的邊的數量。
  • 奇數節點與偶數節點：如果一個節點連接的邊數為偶數，它就是偶數節點。如果邊數為奇數，它就是奇數節點。

小貼士：在任何圖（graph）中，奇數節點的數量永遠是偶數（例如：你可以有 0、2 或 4 個奇數節點，但絕對不會有 3 個）。

核心概念：歐拉圖（Eulerian Graphs）

對於郵差來說，「完美」的情況是歐拉圖。這是一個網絡中每一個節點都是偶數節點的情況。

如果所有節點都是偶數，你就可以從任何一個頂點（vertex）出發，剛好走過每一條邊一次，並在不重複走過任何一條路的情況下回到起點。這種情況下，你的總距離就是網絡中所有邊的權重總和。

類比：這就像畫一個圖形，過程中筆不能離開紙面，也不能重複描繪同一條線。

如果圖形不是「完美」的怎麼辦？

在現實世界中，大多數網絡都有奇數節點。如果圖中有奇數節點，你就必須重複經過某些邊才能回到起點。路徑檢查演算法可以幫助我們決定重複哪些邊，以使額外增加的距離降到最低。

情況 1：兩個奇數節點

如果有恰好兩個奇數節點，該圖稱為「半歐拉圖（Semi-Eulerian）」。要完成路線並回到起點，你必須重複這兩個奇數節點之間的最短路徑。

2 個奇數節點的操作步驟：
1. 找出兩個度數為奇數的節點。
2. 找出它們之間的最短路徑（通常可以通過「觀察法」得出——直接看圖即可）。
3. 將這條最短路徑的權重加到網絡中所有邊的權重總和中。

情況 2：四個奇數節點

這是你在 8FM0 課程中會遇到的最複雜版本。如果有四個奇數節點，你必須將它們兩兩配對，並重複這些配對之間的最短路徑。總共有三種可能的配對方式。

4 個奇數節點的操作步驟：
假設你的奇數節點是 \(A, B, C,\) 和 \(D\)。
1. 列出三種可能的配對方式：
   • 配對 1：\((AB)\) 和 \((CD)\)
   • 配對 2：\((AC)\) 和 \((BD)\)
   • 配對 3：\((AD)\) 和 \((BC)\)
2. 將每種配對的兩條路徑權重相加，計算出每種配對的總最短距離。
3. 選擇總和最小的那一組配對。
4. 將這個「額外」距離加到網絡中所有邊的權重總和中。

你知道嗎？ 這個演算法之所以被稱為「中國郵差問題」，是因為它是由中國數學家管梅谷（Mei-Ko Kwan）於 1960 年首次研究提出的！

範例詳解

想像一個邊權重總和為 150km 的小型網絡。你發現了四個奇數節點：A, B, C 和 D。

它們之間的最短距離分別為：\(AB = 10, AC = 12, AD = 15, BC = 14, BD = 11, CD = 13\)。

讓我們檢查一下配對：
1. \((AB + CD) = 10 + 13 = 23\)
2. \((AC + BD) = 12 + 11 = 23\)
3. \((AD + BC) = 15 + 14 = 29\)

配對 1 和配對 2 都給出了最小的額外距離 23。
最終答案： 總路線長度 = \(150 + 23 = 173\text{km}\)。

常見錯誤提示

  • 忘記加上「權重總和」： 學生經常計算出額外距離（例如 23），卻忘記把它加到圖中所有原始邊的總和上。
  • 遺漏奇數節點： 請務必仔細檢查每個節點的度數。如果你漏掉了一個，你的配對就會全錯！
  • 沒有檢查所有 3 種配對： 不要只隨手挑選前兩個看到的奇數節點。對於 4 個節點，你必須檢查所有 3 種組合。

如果剛開始覺得很難，不用擔心！ 記住，奇數節點就是「問題區域」。我們只是在試圖找出最便宜的方法來「修復」這些問題，方法就是重複走過連接它們的道路。

總結：關鍵要點

目標：走遍每一條邊至少一次並回到起點。

快速檢視表：
• 0 個奇數節點： 總距離 = 所有邊的總和。
• 2 個奇數節點： 總距離 = 所有邊的總和 + 這 2 個奇數節點間的最短路徑。
• 4 個奇數節點： 總距離 = 所有邊的總和 + 4 個奇數節點的 3 種可能配對中最小的總和。

接下來是什麼？

既然你已經能算出路線長度了，接下來請練習列出實際的路線（節點序列）。記住，如果你「重複」了一條邊（例如 \(AB\)），你的最終路徑必須真的經過 \(A\) 和 \(B\) 兩次！