Algorithms and graph theory

歡迎來到決策數學（Decision Mathematics）的世界！

歡迎來到決策數學 1 (Decision Mathematics 1) 的世界。這門數學分支並非探討複雜的微積分或抽象的幾何，而是關於效率 (efficiency) 的科學。你可以把它看作是「現實世界的數學」。無論是 GPS 導航規劃最快路徑、倉庫員工整理貨物，還是電腦排列你的播放清單，背後運作的都是演算法 (algorithms)。在這一章中，我們將學習如何逐步執行這些指令，並理解那些被稱為圖 (graphs) 的「地圖式」結構。

如果起初覺得某些術語聽起來有點生澀，別擔心——我們會把所有內容拆解成簡單易懂的小單元！

1. 演算法：數學的「食譜」

演算法 (algorithm) 其實就是一系列用來解決特定問題的精確指令。其實你每天都在使用它們！烘焙蛋糕的食譜或是組裝樂高積木的說明書，都是演算法的一種。

效率與階數 (Efficiency and Order)

在進階數學 (Further Maths) 中，我們不只在意演算法是否有效，更在意它有多快。這就是所謂的效率 (efficiency)。我們透過觀察演算法的階數 (order) 來衡量效率。

問題規模 (\(n\))： 通常指列表中的項目數量或圖中的頂點數量。
階數： 用來衡量「執行時間」（運算次數）隨著問題規模增加而如何增長。如果你將項目數量增加一倍，而執行時間增加為原來的四倍，那麼該演算法很可能是二次階 (quadratic order) \(O(n^2)\)。

快速複習：常見階數
• 線性階 \(O(n)\)： 時間增長速度與列表長度相同。
• 二次階 \(O(n^2)\)： 時間與規模的平方成正比（在排序問題中很常見）。
• 三次階 \(O(n^3)\)： 時間與規模的立方成正比。

重點提示： 對於大規模問題而言，階數越低，演算法就越「有效率」！

2. 排序與裝箱 (Sorting and Packing)

想像你有一堆雜亂的書，你需要按字母順序排列。你會如何系統化地處理？這就是排序演算法 (sorting algorithms) 的用武之地。

氣泡排序法 (Bubble Sort)

氣泡排序法 (Bubble Sort) 是最簡單的排序方式。你比較相鄰的項目，如果順序錯誤就將它們交換。最大的項目會像氣泡一樣「浮」到列表末端。

逐步流程：
1. 從列表開頭開始。
2. 比較前兩個項目。如果第一個比第二個大，就進行交換。
3. 移動到下一對並重複此步驟，直到抵達列表末端（這稱為一輪掃描 (pass)）。
4. 重複掃描，直到某次掃描過程中沒有任何交換發生為止。

快速排序法 (Quick Sort)

對於大型列表，快速排序法 (Quick Sort) 的效率高得多。它利用一個樞紐點 (pivot) 將列表分成兩個較小的列表（一個放較小的項目，一個放較大的項目）。

Edexcel 對於樞紐點的規則： 若要找出 \(N\) 個項目列表中的中間項（樞紐點）：
• 如果 \(N\) 是奇數，使用位置 \( \frac{1}{2}(N+1) \)。
• 如果 \(N\) 是偶數，使用位置 \( \frac{1}{2}(N+2) \)。

例子： 在 6 個項目的列表中，樞紐點是第 4 個；在 9 個項目的列表中，樞紐點是第 5 個。

裝箱問題 (Bin Packing)

我們如何將物品裝入最少數量的「箱子」(bins) 中？
• 首次適應法 (First-Fit)： 將每個物品放入第一個有空間的箱子中。
• 首次適應遞減法 (First-Fit Decreasing)： 先將物品按降序排列，再執行首次適應法。這通常效率更高！
• 全滿裝箱法 (Full-Bin)： 尋找能剛好填滿箱子的物品組合。

常見錯誤： 在使用「首次適應法」時，記得對於每一個物品，都要檢查箱子 1、箱子 2、箱子 3……不要只停留在當前的箱子！

3. 圖論基礎 (Graph Theory)

圖 (graph) 是一組點的集合，稱為頂點 (vertices)（或節點 nodes），並由稱為邊 (edges)（或弧 arcs）的線連接。

關鍵術語：

• 權重 (Weight)： 與邊相關聯的數值（如距離、成本或時間）。帶有權重的圖稱為網絡 (network)。
• 度數 (Degree/Valency)： 在一個頂點處匯集的邊的數量。如果一個頂點連接了 3 條邊，它的度數就是 3（奇數）。
• 路徑 (Path)： 一組邊的序列，且路徑中不會重複訪問同一個頂點。
• 圈 (Cycle)： 起點和終點相同的路徑。
• 連通 (Connected)： 若圖中任意兩點之間皆可互通，則為連通圖。
• 樹 (Tree)： 沒有圈的連通圖。
• 生成樹 (Spanning Tree)： 包含原圖中所有頂點的一棵樹。

你知道嗎？ 握手引理 (Handshaking Lemma) 指出：所有頂點的度數之和等於邊數的兩倍。這意味著度數之和永遠是偶數！

4. 圖的類型

有些圖具有特殊屬性，處理起來會更簡單：

• 完全圖 (Complete Graph, \(K_n\))： 每個頂點都與其他所有頂點恰好有一條邊連接。擁有 5 個頂點的完全圖記為 \(K_5\)。
• 同構圖 (Isomorphic Graphs)： 兩張圖看起來不同，但擁有相同數量的頂點和相同的連接關係。它們在本質上是「偽裝」成不同外表的同一張圖。
• 平面圖 (Planar Graph)： 一種可以畫出來且沒有任何邊交叉（頂點處除外）的圖。
• 子圖 (Subgraph)： 原圖中的一部分。

重點提示： 識別圖的類型能幫助你選擇最正確的演算法來解題！

5. 可遍歷性 (Traversability)：我們能畫出來嗎？

你能在不提筆或不重複畫同一條線的情況下畫出一張圖嗎？這就是歐拉圖 (Eulerian graphs) 的研究範疇。

歐拉圖 (Eulerian Graph)： 每個頂點的度數皆為偶數。你可以從任意點出發，走遍每一條邊後回到起點。
半歐拉圖 (Semi-Eulerian Graph)： 恰好有兩個頂點的度數是奇數。你可以走遍每一條邊，但必須從其中一個奇數度頂點出發，並在另一個奇數度頂點結束。
皆非 (Neither)： 如果圖中有超過兩個頂點的度數為奇數，則該圖無法一次畫完。

記憶小撇步：
偶 (Even) 數度數 = 歐拉 (Eulerian)（起點/終點在同一處）。
有些 (Some/Two) 奇數度數 = 半歐拉 (Semi-Eulerian)（起點/終點在不同處）。

快速複習：
1. 計算每個頂點的度數。
2. 全為偶數 -> 歐拉圖。
3. 恰好兩個奇數 -> 半歐拉圖。
4. 超過兩個奇數 -> 不可遍歷。

總結：成功小撇步

• 仔細讀題： 在快速排序問題中，題目要求的是升序還是降序排列？
• 系統化： 在演算法中不要跳步。考官很喜歡看到完整的「掃描」或「迭代」過程。
• 檢查計算： 在裝箱問題中，將所有物品總和除以箱子容量，即可得出下界 (lower bound)（理論上最少需要的箱子數）。這是檢查答案是否合理的絕佳方法！
• 不要慌張： 本章的核心在於遵循規則。只要嚴格執行演算法步驟，每次都能得到正確答案！