點與邊的世界：圖論如何刻劃萬物之間的關係

為什麼七座橋走不完？一個城市難題開啟的數學

想像你站在十八世紀的東普魯士城市哥尼斯堡（Königsberg）。普列戈利亞河（Pregolya River）穿城而過，把陸地分成四塊，七座橋把它們連接起來。市民們週日散步時提出了一個看似無聊卻意外棘手的問題：有沒有辦法走遍全城，每座橋恰好通過一次，最後回到出發點？

無數人試了又試，都失敗了。直到 1736 年，數學家歐拉（Leonhard Euler）證明：這件事根本不可能。他的證明開創了一個全新的數學分支——圖論（Graph Theory）。歐拉的關鍵洞見是：陸地的形狀、橋的長度、走路的快慢，通通不重要。重要的只有一件事——哪塊陸地連到哪塊陸地。

把每塊陸地縮成一個「點」，每座橋畫成一條「邊」，整座城市就變成一張抽象的圖。當我們只保留「連接關係」而丟掉所有幾何細節時，問題的本質才終於浮現。這正是圖論的精神：用點與邊，刻劃萬物之間的關係。

圖是什麼：點、邊與最基本的語言

一張圖（graph）$G = (V, E)$ 由兩個集合構成：

• 頂點集（vertex set） $V$：圖中的「點」，代表物件（陸地、人、城市、網頁）。
• 邊集（edge set） $E$：連接頂點的「邊」，代表關係（橋、友誼、航線、超連結）。

每條邊是一對頂點 $\{u, v\}$。若邊沒有方向，稱為無向圖（undirected graph），如朋友關係（你是我朋友，我也是你朋友）；若邊有方向（用 $(u, v)$ 表示由 $u$ 指向 $v$），稱為有向圖（directed graph / digraph），如「A 追蹤 B」這種單向關係。

一個頂點 $v$ 連接的邊數，稱為它的度數（degree），記作 $\deg(v)$。在哥尼斯堡問題裡，每塊陸地的度數就是它連出去的橋數。

度數有一條極優雅的定律——握手定理（Handshaking Lemma）：

$$\sum_{v \in V} \deg(v) = 2|E|$$

意思是「所有頂點的度數總和，等於邊數的兩倍」。為什麼？因為每條邊都恰好貢獻 $2$ 給度數總和（它的兩個端點各算一次）。一個立即的推論是：度數為奇數的頂點，個數必為偶數。在任何派對裡，握過奇數次手的人，總是偶數個。

歐拉的答案：奇度頂點決定一切

回到那七座橋。歐拉發現，能「一筆畫」走遍每條邊恰好一次的路徑（稱為歐拉路徑，Eulerian path），其存在與否完全由奇度頂點的數量決定：

• 若要回到起點（歐拉迴路，Eulerian circuit）：圖必須連通，且每個頂點的度數都是偶數。
• 若起點與終點可以不同：圖必須連通，且恰好有 0 個或 2 個奇度頂點。

直覺很簡單：每次你「走進」一個頂點，就必須能「走出」去，所以經過的邊要成對出現——除了起點和終點之外。

哥尼斯堡的四塊陸地，度數分別是 $3, 3, 3, 5$，四個全是奇數。$4 > 2$，所以歐拉路徑不存在。市民們的失敗，並非不夠努力，而是數學上的鐵律。

路徑、連通與距離：在圖上移動

圖論的核心活動之一，就是研究「如何在圖上移動」。幾個關鍵概念：

• 路徑（path）：一連串首尾相接的邊，且不重複經過頂點。
• 環（cycle）：起點與終點相同的路徑。
• 連通（connected）：若任意兩頂點之間都存在路徑，則圖是連通的。否則它會分裂成數個連通分量（connected component）。
• 距離（distance） $d(u, v)$：$u$ 到 $v$ 的最短路徑所含的邊數。

「最短路徑」是圖論最具實用價值的問題之一。你每次用導航 App 找路、社群網站推算「朋友的朋友」、網路封包尋找傳輸路徑，背後都是最短路徑演算法在運作。

著名的六度分隔理論（six degrees of separation）就是一個圖論斷言：在全人類的社交圖上，任兩人之間的距離平均不超過 $6$。

樹：最精簡的連通結構

在所有連通圖中，有一類特別純淨——樹（tree）：連通且不含任何環的圖。

樹有一個漂亮的性質：一棵有 $n$ 個頂點的樹，恰好有 $n - 1$ 條邊。多一條邊就會產生環，少一條邊就會斷裂。樹是「剛好把所有點連起來、一條不多一條不少」的最精簡結構。

樹無所不在：家族族譜、檔案系統的目錄結構、生物的演化樹、決策樹、HTML 的 DOM 結構。當我們需要「無冗餘的層級連接」時，樹就是答案。

看一個例子：用相鄰矩陣計算路徑數

圖可以用相鄰矩陣（adjacency matrix）表示。設圖有 $n$ 個頂點，矩陣 $A$ 是 $n \times n$ 的方陣，其中

$$A_{ij} = \begin{cases} 1 & \text{若頂點 } i \text{ 與 } j \text{ 之間有邊} \\ 0 & \text{否則} \end{cases}$$

考慮一個四頂點的圖，頂點為 $\{1, 2, 3, 4\}$，邊為 $\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}$（一個正方形環）。它的相鄰矩陣為：

$$A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$$

這裡藏著一個令人驚喜的定理：$A^k$ 的第 $(i,j)$ 項，等於從頂點 $i$ 走 $k$ 步抵達 $j$ 的「不同路徑數」（允許重複經過頂點的走法，稱為 walk）。

我們來計算 $A^2$：

$$A^2 = \begin{pmatrix} 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2 \\ 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2 \end{pmatrix}$$

讀一下對角線：$(A^2)_{11} = 2$，意思是從頂點 $1$ 走兩步回到 $1$ 的走法有 $2$ 種——確實如此，你可以走 $1 \to 2 \to 1$，也可以走 $1 \to 4 \to 1$。再看 $(A^2)_{13} = 2$：從 $1$ 走兩步到 $3$，可以走 $1 \to 2 \to 3$ 或 $1 \to 4 \to 3$，恰好兩種。

矩陣冪運算，竟然就能數出圖上的路徑——這是「線性代數」與「圖論」交會的第一個火花，後面在頻譜圖論還會大放異彩。

動手試試：判斷你的人際網路能否「一筆畫」

拿一張紙，畫出你和五個朋友之間的「認識關係」（互相認識就連一條線）。現在用歐拉的判準檢查：

1. 算出每個人的度數（連幾條線）。
2. 數一數奇度頂點有幾個。
3. 若是 $0$ 個 → 存在歐拉迴路（可從任一點出發、走遍每條關係線、回到原點）；若是 $2$ 個 → 存在歐拉路徑（必須從某個奇度點出發，到另一個奇度點結束）；其餘情況 → 不可能一筆畫完。

你會發現，這個判準快到不可思議——不必真的去試走任何路徑，只要數一數度數的奇偶性就夠了。這正是好的數學定理的威力：把「指數級的嘗試」化約為「線性的計算」。

著色與規劃：把抽象變應用

圖論還有一個極富應用價值的方向——圖著色（graph coloring）。我們想為每個頂點塗上顏色，使相鄰的頂點顏色不同，並問：最少需要幾種顏色？這個最小數稱為色數（chromatic number） $\chi(G)$。

這聽起來抽象，卻直接對應現實中的「衝突排程」：

• 考試排程：頂點是課程，若兩門課有共同學生則連邊（衝突）。同色 = 同一時段考試。色數 = 至少需要幾個考試時段。
• 頻率分配：頂點是基地台，距離太近會干擾的連邊。同色 = 同頻率。
• 地圖著色：相鄰國家不同色——著名的四色定理（Four Color Theorem） 斷言：任何平面地圖只需 $4$ 種顏色。這是史上第一個借助電腦完成的重大數學證明（1976 年）。

重點回顧

• 圖 $G = (V, E)$ 用頂點與邊刻劃物件之間的關係；圖論的精髓是「只保留連接，丟棄幾何」。
• 握手定理 $\sum_v \deg(v) = 2|E|$ 告訴我們度數總和必為偶數，奇度頂點必成對出現。
• 歐拉路徑/迴路的存在與否，只由連通性與奇度頂點數量決定：$0$ 個奇度點 → 有迴路；恰 $2$ 個 → 有路徑；其餘 → 無解。
• 樹是連通且無環的圖，$n$ 個頂點恰有 $n-1$ 條邊，是最精簡的連接結構。
• 相鄰矩陣的冪 $A^k$ 可直接數出長度為 $k$ 的走法數，連結了線性代數與圖論。

深入探討（研究所視角）

當我們把圖論推向研究前沿，幾條主線值得學習者繼續探索。

頻譜圖論（spectral graph theory） 將圖的結構編碼進矩陣的特徵值（eigenvalue）。核心物件是圖拉普拉斯矩陣（graph Laplacian） $L = D - A$，其中 $D$ 是度數對角矩陣、$A$ 是相鄰矩陣。$L$ 是半正定的，其特徵值排序為 $0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_n$。特徵值 $0$ 的重數恰等於連通分量的數目；而第二小特徵值 $\lambda_2$（稱為代數連通度，algebraic connectivity 或 Fiedler value）刻劃了圖「有多難被切斷」。對應的 Fiedler 特徵向量，是頻譜分群（spectral clustering） 與社群偵測（community detection）的理論基石——這也是現代機器學習中圖嵌入（graph embedding）的源頭之一。

隨機圖（random graph） 由 Erdős 與 Rényi 在 1959 年開創。在 $G(n, p)$ 模型中，$n$ 個頂點之間每對以機率 $p$ 獨立連邊。一個驚人的發現是相變（phase transition）現象：當 $p$ 跨過臨界閾值 $\frac{1}{n}$ 時，圖會「突然」從碎片化變為出現一個橫跨大部分頂點的巨大連通分量（giant component）；而連通性的閾值則在 $p = \frac{\ln n}{n}$ 附近。這類臨界現象與物理學中的滲流理論（percolation theory）深刻呼應。

複雜網路（complex networks） 則把圖論帶進真實世界。現實中的社交網、網際網路、蛋白質交互網，大多呈現無尺度（scale-free） 特性：度數分佈服從幂律（power law） $P(k) \sim k^{-\gamma}$，其中指數 $\gamma$ 通常落在 $2$ 到 $3$ 之間。這意味著存在極少數高度連接的樞紐節點（hub）。Barabási–Albert 模型用「優先連接（preferential attachment）」機制——新節點傾向連向已經很熱門的節點——成功重現了這種分佈。這解釋了為何 Google 的 PageRank 演算法（本質是相鄰矩陣的主特徵向量問題，即一個馬可夫鏈的穩態分佈）能有效衡量網頁重要性。

計算複雜度（computational complexity） 是圖論與理論計算機科學的交界。某些圖問題有高效解（如最短路徑的 Dijkstra 演算法、最小生成樹的 Kruskal 演算法，皆為多項式時間），但另一些卻是NP 完備（NP-complete）——如判斷圖是否存在漢米爾頓迴路（Hamiltonian circuit，恰好經過每個頂點一次）、求解最小頂點著色數、尋找最大團（maximum clique）。有趣的對比：歐拉迴路（走遍每條邊）有簡單的多項式判準，而表面上極相似的漢米爾頓迴路（走遍每個頂點）卻是 NP 完備。這道「容易與困難之間的鴻溝」，至今仍是 $\text{P} \overset{?}{=} \text{NP}$ 千禧問題的一部分。

對教育與學習科學而言，圖論提供了刻劃「關係資料」的天然語言：學習者之間的協作網、知識點之間的先備依賴圖、討論區的互動結構，都可以建模為圖，再用頻譜方法或網路指標分析學習社群的凝聚與資訊流動。從十八世紀的七座橋，到今日的學習分析（learning analytics），圖論始終在問同一個問題——當我們只看「誰連著誰」，世界會顯露出什麼樣的秩序？