歡迎來到圖論（Graphs）的世界！
在進階數學（Further Mathematics）中，當我們談論「圖」（Graphs）時，指的並非你在 GCSE 階段所學的 \(x\) 和 \(y\) 軸圖表。這裡我們要探討的是離散數學（Discrete Mathematics）。試想一下倫敦地鐵的路線圖，或是社交媒體上人與人之間的關係網，這些都是由點和連接點的線所構成的網絡，這就是我們這裡所說的「圖」！
在本章中，我們將學習描述這些連結的專業術語，並探索隱藏在背後的運作規律。如果剛開始接觸到許多新詞彙，請別擔心——一旦你看出了當中的規律，就會發現這部分數學其實非常有邏輯且直觀。
1. 圖的詞彙表
要像一位離散數學家那樣溝通，你需要了解圖的「解剖結構」。讓我們拆解最關鍵的術語。
基礎知識
- 頂點（Vertex，複數：Vertices）： 圖中的「點」。你可以把它們想像成地圖上的城市。
- 邊（Edge）： 連接點與點的「線」。你可以把它們想像成城市之間的道路。
- 度數（Degree 或 Valency）： 與一個頂點相連的邊的數量。如果一個城市有三條路通往外面，它的度數就是 3。
路徑與連接
- 跡（Trail）： 一個邊的序列，其中沒有任何邊被重複使用。
- 環（Cycle）： 一個封閉的跡。你從某個頂點出發，沿著路徑走，在不重複任何邊的情況下回到起點。
- 連通圖（Connected Graph）： 一個圖，你可以在其中透過邊從任何一個頂點到達另一個頂點。圖中沒有「孤島」。
- 子圖（Subgraph）： 大圖中的一小部分。就像集合論中的子集一樣，它是從原圖中選取部分頂點和邊所組成的。
特殊屬性
- 迴路（Loop）： 一個起點和終點都在同一個頂點上的邊。
- 多重邊（Multiple Edges）： 當兩個頂點之間有多於一條邊連接時。
- 簡單圖（Simple Graph）： 沒有迴路且沒有多重邊的圖。這是圖中最「乾淨」的形式。
- 細分（Subdivision）： 將一條邊替換為兩條邊，並在中間加入一個新頂點。想像一下在路的中間新增一個巴士站。
快速複習：
頂點（Vertex）是點。邊（Edge）是線。度數（Degree）是連接到該點的線的數量。環（Cycle）是一趟繞圈的旅程。
2. 樹與完全圖
有些圖擁有非常特殊的結構，這讓它們在解決問題時非常實用。
什麼是樹（Tree）？
在數學中，樹是一種連通且沒有環的圖。
類比： 想像家譜。它會不斷分支出去，但永遠不會繞回來形成一個圓圈。
完全圖（Complete Graphs, \(K_n\)）
完全圖是指每一個頂點都恰好與其他所有頂點透過一條邊相連的圖。我們使用符號 \(K_n\) 來表示，其中 \(n\) 是頂點的數量。
例子： 在 \(K_4\) 中，共有 4 個頂點，每個頂點的度數都是 3。
二分圖（Bipartite Graphs）
在二分圖中，頂點被分為兩個獨立的集合。邊只能連接來自第一個集合的頂點與第二個集合的頂點。你永遠不可能有一條邊連接同一個集合內的兩個頂點。
現實生活例子： 想像一組「工作」和一組「工人」。你將工人與他們有資格擔任的工作連接起來，你絕不會把工作與工作連接在一起！
重點總結：
樹沒有環。完全圖（\(K_n\)）是完全連接的。二分圖則像是在「配對」兩個不同的群體。
3. 鄰接矩陣（Adjacency Matrices）
有時候，畫圖會顯得很混亂。我們可以用一個數字表格來表示同樣的資訊，這稱為鄰接矩陣。
在鄰接矩陣中：
1. 行和列代表各個頂點。
2. 格子內的數字告訴你那兩個頂點之間連接了多少條邊。
常見錯誤：
對於簡單圖而言，主對角線（從左上到右下）永遠會是零，因為簡單圖沒有迴路（頂點不會與自身連接）。
4. 歐拉圖與哈密頓圖
本節的主題是「可遍歷性」——我們能否遵循特定的規則走遍整個圖？
歐拉圖（Eulerian Graphs）
如果一個圖可以讓你從某個頂點出發，走過每一條邊恰好一次，並回到起點，那麼它就是歐拉圖。
訣竅： 一個連通圖是歐拉圖的充要條件是每個頂點的度數都是偶數。
半歐拉圖（Semi-Eulerian Graphs）
如果你可以走過每一條邊恰好一次，但最終停在與起點不同的頂點上，它就是半歐拉圖。
訣竅： 這發生在恰好有兩個頂點具有奇數度數的情況下（分別作為起點和終點）。
哈密頓圖（Hamiltonian Graphs）
哈密頓圖的情況略有不同。這裡我們關注的是頂點，而不是邊。如果一個圖存在一個能訪問每個頂點恰好一次的環，那麼該圖就是哈密頓圖。
記憶小撇步： Eulerian = Edges（邊）。Hamiltonian = Homes（頂點/家）。
你知道嗎？
歐拉問題起源於「柯尼斯堡七橋問題」，當時人們試圖在不重複經過同一座橋的情況下走遍七座橋。李昂哈德·歐拉正是利用上述這些度數規則，證明了這是不可能的任務！
5. 平面性與歐拉公式
平面圖（Planar Graph）是指可以被畫出來且沒有任何邊互相交叉的圖。即使看起來很亂，只要你能重新安排點的位置讓線不交叉，它就是平面圖。
歐拉公式
對於任何連通平面圖，頂點數（\(V\)）、邊數（\(E\)）和面數（\(F\)）之間存在一個神奇的關係：
\(V + F - E = 2\)
注意： 面是指由邊圍成的封閉區域，加上包圍整個圖的無限大外部區域（「外部」面）。
庫拉托夫斯基定理（Kuratowski’s Theorem）
我們如何確定一個圖無法在不交叉的情況下畫出呢？庫拉托夫斯基發現了兩個特定的圖是「非平面」的：
1. \(K_5\)（有 5 個頂點的完全圖）。
2. \(K_{3,3}\)（一個二分圖，兩個集合各 3 個頂點，每個頂點都與另一方的所有頂點相連）。
庫拉托夫斯基定理指出，如果一個圖包含 \(K_5\) 或 \(K_{3,3}\) 的細分，則該圖就是非平面的。
6. 同構（Isomorphism）
如果兩個圖實際上是同一個圖，只是畫法不同，我們稱它們為同構圖。它們擁有相同數量的頂點，以相同的方式連接，且每個頂點的度數都相同。
如何檢查兩個圖是否「不同構」：
如果你被要求證明兩個圖不相同，請尋找「不匹配」之處：
- 它們的頂點數或邊數是否不同？
- 它們的度數序列是否不同？（例如：一個圖有度數為 4 的頂點，另一個則沒有）。
- 其中一個是否有長度為 3 的環（三角形），而另一個沒有？
鼓勵一下：
尋找同構就像是在玩「找不同」遊戲。保持耐心，逐個頂點核對連接情況，你一定沒問題的！
摘要清單
- 我能定義度數、跡和環這些基本術語嗎？
- 我知道歐拉圖意味著所有頂點的度數都必須是偶數嗎？
- 我會對平面圖使用 \(V + F - E = 2\) 嗎？
- 我認得 \(K_5\) 和 \(K_{3,3}\) 是「被禁止」的非平面圖嗎？
- 我能解釋為什麼樹沒有環嗎？