Graphs and Networks

歡迎來到圖論與網絡的世界！

在本章中，我們將暫時放下大家從中學（GCSE）以來熟悉的 \(y = f(x)\) 函數圖表。取而代之的是，我們將以圖（Graphs）作為模擬現實世界的工具。試想一下地鐵路線圖、社交媒體上的好友圈，或是手機內部的電路板——這些全都是網絡！我們利用離散數學（Discrete Mathematics）來研究事物之間如何連接、如何尋找最佳路徑，以及如何將複雜的系統簡單化。如果起初覺得有很多新術語，別擔心；一旦你掌握了當中的規律，你會發現這其實是進階數學（Further Maths）中最具視覺感且邏輯分明的一部分。

1. 基礎積木：術語與符號

在解決複雜問題之前，我們需要一套共同語言。一個「圖」本質上就是由「點」與「線」組成的集合。

關鍵術語：

• 頂點（Vertex 或 Node）：圖中的「點」。它們代表實體（如城市、人或電腦）。複數形式為 vertices。
• 弧（Arc 或 Edge）：連接頂點的「線」。它們代表實體之間的關係或路線。
• 頂點的度數（Degree 或 Valency）：連接在該頂點上的弧的數量。你可以把它想像成這個頂點有多少個「朋友」。
• 關聯（Incident）：如果一條弧物理上連接到一個頂點，我們稱這條弧與該頂點「關聯」。
• 鄰接（Adjacent）：如果兩個頂點之間有弧直接相連，則稱這兩個頂點「鄰接」。同樣地，如果兩條弧共用一個頂點，則稱它們「鄰接」。

小貼士：在任何圖中，所有頂點的度數之和永遠等於弧數量的兩倍。這是因為每一條弧都有兩個端點！這通常被稱為握手引理（Handshaking Lemma）。

重點總結：頂點是「位置」，而弧是「連接方式」。

2. 描述圖的特性

並非所有的圖都長得一樣。我們使用特定的名稱來描述它們的「連接程度」或「複雜性」。

圖的種類：

• 簡單圖（Simple Graph）：沒有自環（loop）（即起點和終點在同一個頂點的弧）且沒有多重弧（multiple arcs）（即兩個頂點之間有多於一條弧）的圖。
• 連通圖（Connected Graph）：你可以通過路徑從任何一個頂點到達其他任何一個頂點。圖中沒有「與世隔絕」的孤島。
• 簡單連通（Simply Connected）：在離散數學中，這通常指一個連通且沒有圈（cycle）的圖（例如樹狀圖）。
• 樹（Tree）：一個連通且沒有圈的圖。類比：就像家譜一樣，沒有任何「環」讓你繞回起點。

你知道嗎？一個有 \(n\) 個頂點的樹，必定剛好有 \(n - 1\) 條弧。如果你再加一條弧，就會構成一個圈！

3. 路徑、軌跡與圈

我們如何在圖中移動？課程大綱區分了幾種不同的「旅程」。如果覺得容易混淆也不用擔心，只要記住移動的「層次」即可：

• 行走（Walk）：最基礎的移動方式。你可以重複經過任何頂點或弧。
• 軌跡（Trail）：一種不會重複使用弧的行走。（但你可以多次經過同一個頂點！）
• 路徑（Path）：最「嚴格」的路線。一種不會重複經過頂點的軌跡。
• 圈（Cycle）：一個「封閉的路徑」。從某個頂點出發，最後回到該頂點，過程中不重複經過任何其他頂點或弧。
• 路線（Route）：一個通用術語，可以指上述任何一種情況。

常見錯誤：學生經常混淆路徑（Path）與軌跡（Trail）。請記住：Path（路徑）= 不重複 People（頂點/人）；Trail（軌跡）= 不重複 Tracks（弧/軌跡）。

4. 特殊圖族

有些圖具有非常具體的結構，我們將其作為離散數學中的基準。

完全圖（Complete Graphs，\(K_n\)）

這是一種每一個頂點都與其他所有頂點相連的圖。我們用 \(K_n\) 來表示，其中 \(n\) 為頂點數量。

重要公式：完全圖 \(K_n\) 中的弧數量為： \( \frac{1}{2}n(n-1) \)。

二分圖（Bipartite Graphs，\(K_{m,n}\)）

在二分圖中，頂點被分成兩個獨立的集合。弧只連接一個集合中的頂點與另一個集合中的頂點，同一集合內的頂點之間沒有連接。

• 完全二分圖（Complete Bipartite Graph，\(K_{m,n}\)）：第一個集合（大小為 \(m\)）中的每個頂點都與第二個集合（大小為 \(n\)）中的每個頂點相連。
• 弧的數量：對於 \(K_{m,n}\)，弧的數量簡單地等於 \( m \times n \)。

快速檢視：如何證明一個圖是二分圖？試試染色法（Colouring Argument）。如果你能將每個頂點塗上紅色或藍色，使得沒有兩個相同顏色的頂點相連，那麼這個圖就是二分圖！

5. 可遍歷性：歐拉圖與哈密頓圖

這是考試中的經典考點，主要問的是：「我們可以一次過走完所有東西嗎？」

歐拉圖（側重於「弧」）

歐拉圖（Eulerian graph）是指能夠找到一條路徑，能夠遍歷每一條弧且僅限一次，並回到起點的圖。

• 歐拉圖：所有頂點的度數均為偶數。
• 半歐拉圖（Semi-Eulerian）：恰好有兩個頂點的度數為奇數。你可以遍歷所有弧，但必須從其中一個奇數度頂點出發，並在另一個奇數度頂點結束。

哈密頓圖（側重於「頂點」）

哈密頓圈（Hamiltonian Cycle）是一個能夠恰好經過每個頂點一次（並回到起點）的圈。

• 奧爾定理（Ore's Theorem）：對於一個有 \(n \ge 3\) 個頂點的簡單圖，如果對於每一對不鄰接的頂點 \(v\) 和 \(w\)，都有 \( \text{deg } v + \text{deg } w \ge n \)，則該圖是哈密頓圖。
• 注意：奧爾定理是哈密頓圖的充分條件，但不是必要條件。如果條件不滿足，該圖仍然可能是哈密頓圖！

重點總結：歐拉圖看「弧」。哈密頓圖看「頂點」。

6. 有向圖與同構

有向圖（Digraphs）

在有向圖中，弧是有箭頭的！它們是單行道。我們不再只用「度」，而是使用：

• 入度（Indegree）：指向該頂點的弧的數量。
• 出度（Outdegree）：從該頂點向外指出的弧的數量。

同構（Isomorphism）

如果兩個圖在結構上本質相同，即使畫法不同，我們也稱它們為同構。它們必須擁有相同數量的頂點、相同數量的弧，以及相同的度數序列（按順序排列的度數列表）。

警告：擁有相同的度數序列是同構的必要條件，但不是充分條件。你必須檢查實際的連接方式是否完全相同！

7. 平面圖：保持平面

如果一個圖可以畫出來而沒有任何弧交叉，則該圖是平面圖（planar）。

關鍵概念：

• 細分（Subdivision）：在現有的弧上增加一個度數為 2 的新頂點（就像在繩子上加一顆珠子）。
• 收縮（Contraction）：將一條弧縮短，直到兩端的頂點合併為一個。
• 歐拉公式（Euler’s Formula）：對於任何連通平面圖： \( V + R = E + 2 \)，其中 \(V\) 是頂點，\(R\) 是區域（包括圖外無限大的區域），\(E\) 是邊（弧）。
• 庫拉托夫斯基定理（Kuratowski's Theorem）：一個圖是平面圖的充要條件是它不包含任何 \(K_5\) 或 \(K_{3,3}\) 的細分圖。（這兩個就是「禁忌」的非平面圖形！）
• 厚度（Thickness）：「覆蓋」一個非平面圖的所有邊所需的最少平面圖數量。（在你的課程中，我們主要探討厚度為 1 或 2 的情況）。

8. 網絡與矩陣

網絡其實就是弧具有權重（weights）（代表距離、成本或時間的數值）的圖。

以數值表示圖：

• 鄰接矩陣（Adjacency Matrix）：一個表，行和列代表頂點。數字 '1' 表示它們相連；'0' 表示不相連。對於有向圖，這還能顯示方向。
• 權重矩陣（Weighted Matrix）：類似於鄰接矩陣，但我們不寫 '1'，而是寫出弧的權重。如果沒有連接，我們通常用短橫線（\(-\)）或無窮大符號（\(\infty\)）表示。

快速複習箱：
- 頂點：點。
- 弧：線。
- 樹：沒有圈。
- 歐拉圖：每條邊只走一次（度數皆為偶數）。
- 哈密頓圖：每個頂點只走一次。
- 歐拉公式： \( V + R = E + 2 \)。

最後的鼓勵

離散數學往往需要你多與圖表「互動」。如果某個概念感覺很抽象，試著把它畫出來！在二分圖上使用不同顏色，或者用手指在歐拉軌跡上比劃。你一定可以做到的！