歡迎來到圖論的世界！
在你大部分的數學課中，「圖形」（Graphs）通常指 \(y = x^2\) 或直線。但在離散數學中，圖形更像是地圖或社交網絡，它們僅僅是由「點」通過「線」連接而成的集合。
讀完這些筆記後，你將能像專家一樣描述這些圖表，理解如何穿梭其中，甚至解決困擾數學家數百年的難題！如果一開始接觸到很多新詞彙，請別擔心——我們會循序漸進地學習。
1. 圖的構造
在開始任何高深的運算前，我們必須先認識各部分的名稱。可以把一個圖想像成城市與連接城市的道路集合。
關鍵詞彙（課程大綱 DA1 及 DA6）
頂點 (Vertex，複數：Vertices)： 即「點」。在現實世界的例子中，這些點可以是社交網絡中的用戶，或是地鐵路線中的車站。
邊 (Edge)： 連接頂點的「線」。它們代表兩點之間的關係或路徑。
度 (Degree 或 Valency)： 連接到特定頂點的邊數。貼士：如果頂點上有環（Loop），該環在計算度數時計作 2！
環 (Loop)： 起點和終點都在同一個頂點的邊。
多重邊 (Multiple Edges)： 連接相同兩個頂點的多於一條邊。
簡單圖 (Simple Graph)： 一個沒有環且沒有多重邊的圖。這是圖最「純淨」的形式。
構建圖形
子圖 (Subgraph)： 大型圖的一部分。想像一下拿著英國地圖，但只關注倫敦市內的道路——這就是一個子圖。
細分 (Subdivision)： 當你對一條邊進行「放大」，並在其中間放置一個新頂點，從而將一條邊變為兩條時，這就稱為細分。
連通圖 (Connected Graph)： 在這個圖中，你可以通過邊從任何頂點到達其他任何頂點。它不一定是直接路徑，但不能有任何「孤島」。
重點速覽：
- 頂點 (Vertices) = 點
- 邊 (Edges) = 線
- 度 (Degree) = 在一個點上匯集的線條數量
- 簡單圖 (Simple) = 沒有環或雙重線
2. 穿梭圖中：軌跡與迴路
現在我們有了「地圖」，該如何移動呢？（課程大綱 DA1）
軌跡 (Trail)： 一系列邊的序列，其中沒有邊被重複使用。你可以重複訪問同一個頂點，但不能兩次走過同一座橋！
迴路 (Cycle)： 一個閉合的軌跡。這意味著你從同一個頂點出發，最後回到該頂點，過程中沒有重複使用任何邊。
類比：將「軌跡」想像成在公園散步，你想走遍所有路徑，但絕不走回頭路。而「迴路」就像是在賽車場跑了一圈。
3. 歐拉圖與哈密頓圖
接下來我們要探討圖的一些特殊性質。這些性質以兩位著名的數學家 Leonhard Euler（歐拉）和 William Rowan Hamilton（哈密頓）命名。（課程大綱 DA2）
歐拉圖 (Eulerian Graphs)
歐拉圖是指你能找到一條軌跡，恰好使用每一條邊一次，並回到起點。
秘訣： 一個連通圖是歐拉圖的充要條件是，每一個頂點的度數都是偶數。
半歐拉圖 (Semi-Eulerian)： 你可以使用每一條邊一次，但起點和終點在不同位置。這發生在圖中剛好有兩個奇數度頂點時（這兩個點分別是起點和終點）。
哈密頓圖 (Hamiltonian Graphs)
哈密頓圖關注的是頂點，而不是邊。它是一個包含一個能恰好訪問每個頂點一次（並回到起點）的迴路的圖。
記憶法：Eulerian = Edges（邊）。Hamiltonian = Homes（頂點/家）。
核心重點：
- 歐拉圖 (Eulerian)：「我不提起筆或重疊線條，能畫完這個圖嗎？」
- 哈密頓圖 (Hamiltonian)：「我能每個城市只去一次並回到家嗎？」
4. 特殊類型的圖
有些圖擁有特定的結構，使它們在模擬不同情況時非常有用。（課程大綱 DA5 及 DA6）
完備圖 (\(K_n\))
在完備圖中，每個頂點都與其他所有頂點通過一條邊相連。我們用 \(K_n\) 表示，其中 \(n\) 是頂點的數量。
例子：在 \(K_4\) 中，有 4 個頂點，每個頂點的度數均為 3。
二分圖 (Bipartite Graphs)
在二分圖中，頂點被分成兩個獨立的集合（我們稱為集合 A 和集合 B）。邊只存在於兩個集合之間，而永遠不會存在於集合內部。
現實例子：一個展示「學生」與「課程」的圖。邊連接學生和他所選修的課程。學生與學生之間不會相連，課程與課程之間也不會相連。
樹 (Trees)
樹是一種非常簡單的連通圖，且沒有迴路。
你知道嗎？ 一個有 \(n\) 個頂點的樹，必定剛好有 \(n - 1\) 條邊。如果你多加任何一條邊，就會產生一個迴路！
5. 鄰接矩陣與補圖
有時候，手繪圖表會顯得很混亂，這時我們可以使用表格（矩陣）來代替。（課程大綱 DA5）
鄰接矩陣 (Adjacency Matrix)： 一個網格，行和列分別代表頂點。格內的數字告訴你那兩個頂點之間連接了多少條邊。
補圖 (Complement of a Graph)： 想像一個圖 \(G\)。補圖（記作 \(G'\)）是一個擁有相同頂點，但包含所有在原圖中不存在的邊的圖。
類比：如果 \(G\) 代表「互為朋友的人」，那麼補圖 \(G'\) 就代表「互為陌生人的人」。
6. 平面圖與歐拉公式
你能畫出一個沒有邊交叉的圖嗎？（課程大綱 DA3）
平面圖 (Planar Graph)： 一個可以被畫成沒有邊交叉的圖。即使目前繪製的方式有交叉，只要你能通過調整將其「理順」，它就是平面圖。
歐拉公式 (Euler’s Formula)
對於任何連通平面圖，頂點數 (\(V\))、邊數 (\(E\)) 和面數 (\(F\)) 之間存在一個神奇的關係：
\(V + F = E + 2\)
什麼是「面」？
面是由邊所圍成的區域。
常見錯誤： 永遠記得要把圖形外面那個「無限大」的區域也算作一個面！如果你畫一個正方形，它共有 2 個面：正方形內部，以及它外面的廣闊區域。
簡單例子：
一個簡單的三角形：
- \(V = 3\)
- \(E = 3\)
- \(F = 2\)（內部和外部）
驗證：\(3 + 2 = 3 + 2\)。成立！
總結表：關鍵性質
樹 (Tree)： 連通、無迴路、\(E = V - 1\)。
完備圖 (Complete - \(K_n\))： 每個頂點均與其他所有頂點相連。
平面圖 (Planar)： 沒有邊需要交叉，遵循 \(V + F = E + 2\)。
歐拉圖 (Eulerian)： 所有頂點的度數均為偶數。
二分圖 (Bipartite)： 頂點分為兩組；連接僅存在於組與組之間。
如果一開始覺得困難，別擔心！離散數學的核心在於視覺化這些連接。試著親自畫出這些不同類型的圖——這是讓定義深入腦海最好的方法！