歡迎來到決策數學（Decision Mathematics）的世界！
歡迎來到決策數學 1 (試卷 3D) 的領域。如果你曾好奇 GPS 是如何找出最快路線、倉庫如何有效率地堆疊貨物，或是社交網絡如何將朋友連接起來，那麼你來對地方了！這一章節——演算法與圖論 (Algorithms and Graph Theory)，正是這一切的基礎。
如果有些術語起初聽起來有點「科技感」，請不用擔心。你可以把演算法 (algorithm) 想像成一個非常精確的食譜，而圖論 (graph theory) 則是繪製地圖來解開謎題的方法。讓我們馬上開始吧！
1. 演算法：數學食譜
演算法是一系列用於解決特定問題的指令。在考試中，這些指令可能會以流程圖 (flow chart) 或一系列文字指令的形式呈現。
演算法的「階」 (Order)
並非所有演算法都是一樣的！有些很快，但有些會隨著問題規模變大而耗費很長時間。演算法的階（通常稱為複雜度）告訴我們當問題的規模 (\(n\)) 增加時，執行時間是如何增加的。
快速回顧：常見的階
1. 線性 (Linear)： \(O(n)\) — 如果清單長度加倍，執行時間也會加倍。
2. 二次方 (Quadratic)： \(O(n^2)\) — 如果清單長度加倍，執行時間會變為四倍！（在排序中很常見）。
3. 三次方 (Cubic)： \(O(n^3)\) — 如果清單長度加倍，執行時間會增加為 8 倍。
類比：如果你要在電話簿中尋找一個名字，線性搜尋意味著要檢查每一頁。一個更有效率的演算法會快得多！
關鍵重點：
問題的規模通常是指項目的數量或頂點的數量。效率是指操作次數相對於規模的增長方式。
2. 排序：氣泡排序法與快速排序法
為了處理數據，我們經常需要將其排列順序。你需要掌握兩種主要方法。
氣泡排序法 (Bubble Sort)
在氣泡排序法中，你會比較相鄰的項目。如果它們的順序錯誤，就將其交換。你不斷地遍歷清單，直到某一次遍歷中完全沒有發生任何交換為止。
常見錯誤：學生經常忘記最後必須執行一次「檢查遍歷」來證明清單已排好序，即使看起來已經完成了也要做！
快速排序法 (Quick Sort)
這是一種「分治法 (divide and conquer)」演算法。對於大型清單，它通常比氣泡排序法快得多。
步驟指南：
1. 選擇一個樞紐 (pivot)。重要規則：對於 Edexcel，請務必選擇清單的中間項目。（如果清單有 \(n\) 個項目，當 \(n\) 為奇數時，樞紐位於 \([\frac{1}{2}(n+1)]\) 的位置；若 \(n\) 為偶數，則位於 \([\frac{1}{2}(n+2)]\) 的位置）。
2. 建立兩個子清單：比樞紐小的項目和比樞紐大的項目。
3. 對每個子清單重複上述過程，直到每個項目都成為過樞紐為止。
記憶小撇步：Bubble sort (氣泡排序) 是 Basic (基礎) 且緩慢的。Quick sort (快速排序) 當然就是... Quick (快速) 的！
3. 裝箱問題 (Bin Packing)：如何塞進去
我們如何將不同大小的項目放入最少數量的箱子中？
首次適應法 (First-Fit Algorithm)
依照給定的順序拿取每個項目，將其放入第一個有剩餘空間的箱子中。這個方法很簡單，但並不總是最高效率的。
首次適應遞減法 (First-Fit Decreasing Algorithm)
1. 先將項目按降序（從大到小）排列。
2. 應用「首次適應法」。
為什麼要這樣做？ 通常，透過先放入「大」項目，小項目稍後就能更有效地「填補空隙」。
快速回顧：若要找出下界 (lower bound)（即所需的最少箱子數量），請將所有項目大小相加並除以箱子容量。結果務必無條件進位至整數！
4. 圖論基礎 (Graph Theory)
圖 (graph) 只是由頂點 (vertices)（點，也稱為節點）和邊 (edges)（連接它們的線，也稱為弧）組成的集合。
重要術語：
- 權重 (Weight)：與邊相關聯的數值（如距離或成本）。
- 度數 (Degree 或 Valency)：連接到某個頂點的邊的數量。
- 路徑 (Path)：一系列的邊，且路徑中不重複經過同一個頂點。
- 迴路 (Cycle)：起點與終點為同一個頂點的路徑。
- 樹 (Tree)：一個連通且無迴路的圖。
- 生成樹 (Spanning Tree)：包含圖中所有頂點的樹。
你知道嗎？頂點的「度數」就像是那個頂點握了多少隻手！
5. 特殊類型的圖
教學大綱要求你識別一些特定的圖類型：
完全圖 (Complete Graphs, \(K_n\))
一種每個頂點都與其他所有頂點相連的圖。我們使用符號 \(K_n\) 表示，其中 \(n\) 是頂點的數量。
同構圖 (Isomorphic Graphs)
這些圖展示了相同的資訊，但繪製方式不同。即使它們看起來形狀不同，它們仍具有相同數量的頂點和相同的連接關係。
平面圖 (Planar Graphs)
一種可以繪製成沒有任何邊交叉的圖。
平面性演算法：要檢查一個圖是否為平面圖，試著找出一個哈密頓迴路 (Hamiltonian cycle) 並將其畫成一個圓。然後，將剩餘的邊放在圓的內部或外部，看看是否能避免交叉。
6. 歐拉圖與哈密頓圖
這些以兩位著名數學家命名，重點在於圖的「巡迴」。
歐拉圖 (Eulerian Graphs，邊巡迴)
一個歐拉迴路 (Eulerian cycle) 會經過每一條邊恰好一次，並回到起點。
- 歐拉圖：所有頂點的度數均為偶數。
- 半歐拉圖 (Semi-Eulerian)：恰好有兩個頂點的度數為奇數（其餘均為偶數）。你可以從一個奇數度數頂點出發，在另一個結束。
哈密頓迴路 (Hamiltonian Cycles，頂點巡迴)
一個哈密頓迴路會經過每一個頂點恰好一次，並回到起點。與歐拉圖不同，沒有關於度數的簡單規則來尋找它們——你必須親自觀察找出來！
關鍵重點：
Eulerian (歐拉) = Every Edge (每一條邊)。
Hamiltonian (哈密頓) = Every Head (每一個頂點)。
總結檢查清單
- 你能確定演算法的階嗎？(\(n, n^2, n^3\))
- 你能使用中間項目作為樞紐執行快速排序法 (Quick Sort) 嗎？
- 你知道首次適應法 (First-Fit) 和首次適應遞減法 (First-Fit Decreasing) 的區別嗎？
- 你能透過檢查節點的度數來識別圖是否為歐拉圖嗎？
- 你明白同構圖只是繪製方式不同的「孿生圖」嗎？
如果這看起來定義很多，請別擔心！只要你多練習繪製圖形和排序步驟，一切都會變得自然順手。你一定能做到的！