Graphs and Networks

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

歡迎來到進階數學中最實用且直觀的章節之一！在離散數學的這一部分，我們處理的不是平滑曲線或微積分，而是圖論與網絡（Graphs and Networks）——這是一種數學地圖，用於模擬從社交媒體好友關係、神經網絡路徑，到航空公司航線和互聯網等各種結構。如果這看起來和你以前學過的數學有點「不一樣」，別擔心；重點在於邏輯和連接。讓我們開始吧！

1. 基本構件：術語與標記法

在解決複雜問題之前，我們必須先掌握圖論的語言。你可以將「圖」（Graph）想像成由線連接而成的點的集合。

關鍵術語

• 頂點（Vertex 或 Node）：圖上的點。（複數：Vertices）。
• 弧（Arc 或 Edge）：連接兩個頂點的線。
• 度（Degree 或 Order）：與一個頂點相連的弧的數量。比喻：想像一個火車站，度就是接入該站的鐵軌數量。
• 關聯（Incident）：如果一條弧物理上連接到某個頂點，則稱該弧與該頂點「關聯」。
• 相鄰（Adjacent）：如果兩個頂點之間有弧直接相連，則稱它們「相鄰」。如果兩條弧在同一個頂點相交，則稱它們相鄰。

快速複習：
如果頂點 A 和頂點 B 之間有一條線相連：
1. A 和 B 是相鄰頂點。
2. 該線與 A 和 B 均關聯。
3. A 的度增加 1。

圖的類型

• 簡單圖（Simple Graph）：沒有環（從同一個節點出發又回到該節點的弧）且沒有多重邊（兩個節點之間有多於一條的弧）的圖。
• 連通圖（Connected Graph）：在圖中，你可以通過一系列弧從任何一個頂點到達其他任何頂點。
• 樹（Tree）：一個沒有圈（cycle）的連通圖。它看起來就像樹的分支一樣！
• 單連通（Simply Connected）：就我們目前的教學範圍而言，這指的是那些沒有「洞」或複雜重疊連接的圖，使它們可以被視為一個整體來處理。

常見誤區：學生常誤以為「樹」必須長得像植物。但在數學中，只要是連通且沒有封閉圈的圖，就是樹！

2. 行走：路徑、跡與通路

在圖論中，我們如何從 A 移動到 B 非常重要。根據是否重複經過節點或弧，我們有特定的命名方式。

路徑層級

• 行走（Walk）：最一般的路徑。你可以隨意走，重複經過任何頂點或弧。
• 跡（Trail）：不重複經過任何弧的行走。（你仍然可以多次訪問同一個頂點）。
• 通路（Path）：不重複經過任何頂點的跡。記憶法：Path = People（人）。人們不喜歡被重複提及！
• 圈（Cycle）：一個封閉的通路。你從同一個頂點出發並回到該點，途中不重複經過任何其他節點或弧。
• 路徑（Route）：對行走、跡或通路的統稱，可以是開放的（起點和終點不同）或封閉的（起點和終點相同）。

重點歸納：所有的通路都是跡，所有的跡都是行走，但反過來則不成立！

3. 特殊圖：\(K_n\) 與 \(K_{m,n}\)

有些圖非常常見，以至於它們擁有自己的專屬名稱與公式。

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

完全圖是指圖中每一個頂點都恰好通過一條弧與其他所有頂點相連。我們使用標記 \(K_n\)，其中 \(n\) 是頂點的數量。

神奇公式：具有 \(n\) 個頂點的完全圖擁有 \(\frac{1}{2}n(n-1)\) 條弧。

例子：在 \(K_4\) 中，有 4 個頂點。弧的數量 = \(\frac{1}{2} \times 4 \times 3 = 6\)。

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

二分圖被分成兩組頂點（我們稱之為集合 X 和集合 Y）。弧只連接集合 X 中的頂點與集合 Y 中的頂點。同一集合內的兩個頂點之間沒有連接。
比喻：一種「舞伴」圖，一組是領舞者，另一組是跟隨者。

完全二分圖（\(K_{m,n}\)）在一個集合中有 \(m\) 個頂點，另一個集合中有 \(n\) 個頂點，且兩個集合之間存在所有可能的連接。
弧的數量公式：簡單地等於 \(m \times n\)。

4. 歐拉圖：遍歷的藝術

你知道嗎？這個主題起源於「柯尼斯堡七橋問題」。當時的人們想知道是否能走遍整座城市，穿過每一座橋剛好一次並回到起點。

• 歐拉圖（Eulerian Graph）：每個頂點的度皆為偶數的圖。你可以遍歷每一條邊剛好一次並回到起點。
• 半歐拉圖（Semi-Eulerian Graph）：擁有恰好兩個奇度頂點的圖。你可以遍歷每一條邊剛好一次，但必須從一個奇度頂點開始，並在另一個奇度頂點結束。
• 兩者皆非：如果奇度頂點多於兩個，則你無法在不提筆或重複走過某條邊的情況下畫出該圖！

逐步檢查法：
1. 列出每個頂點的度。
2. 計算有多少個奇數度。
3. 0 個奇數？歐拉圖。2 個奇數？半歐拉圖。多於 2 個？無法遍歷。

5. 同構：數學上的雙胞胎

如果兩個圖在本質上是一樣的，即使它們的畫法不同，我們也稱這兩個圖為同構（Isomorphic）。想像一個由橡皮筋組成的圖；如果你可以拉伸並移動頂點，使一個圖看起來像另一個而不斷開任何連接，那麼它們就是同構的。

如何證明兩個圖是同構的：

• 它們必須擁有相同數量的頂點和弧。
• 它們必須擁有相同的度序列（degree sequence）（按順序排列的頂點度數列表）。
• 警告！擁有相同的度序列是同構的必要條件，但非充分條件。你還必須檢查頂點之間的連接方式是否匹配（例如，如果圖 A 中一個度為 3 的頂點與兩個度為 2 的頂點相連，那麼在圖 B 中也必須滿足此條件）。

6. 有向圖與網絡

有時候，連接只允許單向通行。

有向圖（Digraphs / Directed Graphs）

在有向圖中，弧帶有箭頭以顯示方向。比喻：城市中的單行道。

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

網絡（Networks）

網絡只是一個加權圖。這意味著每一條弧都分配有一個數字（權重），代表距離、時間或成本等資訊。

7. 圖的表示法：矩陣

畫圖固然很好，但計算機更喜歡數字。我們使用兩種類型的矩陣：

• 鄰接矩陣（Adjacency Matrix）：用於圖。第 \(i\) 行第 \(j\) 列的數值告訴你頂點 \(i\) 與頂點 \(j\) 之間有多少條弧連接。（對於簡單圖，通常為 0 或 1）。
• 權重矩陣（Weighted Matrix）：用於網絡。矩陣中的數值為弧的權重。如果沒有連接，我們通常使用無窮大符號（\(\infty\)）或橫線表示。

總結：
圖論與網絡幫助我們將現實世界的關係轉化為數學。無論你是通過觀察頂點度數來檢查圖是否為歐拉圖，還是識別同構的「雙胞胎」，請記住，關鍵在於事物是如何連接的，而不是畫圖看起來有多美觀！如果這讓你覺得像在解謎，別擔心——這本來就是一場謎題挑戰！