# 基礎圖論 (三) : 有趣的圖論 Topics
在前面的篇章，我們粗略地介紹了各種圖論的名詞還有常見的圖。對打競程的來說這樣就很夠了，**但如果你對圖論的理解只有這樣的話，那你的人生應該很無趣**。每次看到網路上那些只介紹資工關心的圖論，而沒去對整個圖論做 overview，我都覺得有點膩，想說他們的人生是不是也那麼無趣。因此這篇來聊聊圖論究竟有什麼好玩的主題，你可以看完後去查一些這些主題的 open problems，每天睡前想一下，說不定哪天上帝託夢你就想出來了也說不定(?

PS : 這篇就只是閒聊，用字遣詞可能非常不精確，也懶得給證明，有可能還會有些怪怪的自言自語

## 古典的圖論主題 Classical Graph Topics
### 連通/不連通 Connectivity
研究歐拉道路/迴路是圖論領域的第一篇論文，也是開啟這領域的濫觴，古典的圖論是從對於生活中空間的觀察開始。當我們看地圖，我們會在意的無非就是能否從一個地方到達另一個地方。之後可能也會有人想搞破壞，看要破壞哪條路或是城鎮才有辦法使兩地無法溝通。這些連通與不連通的討論應用最多的應該就是經濟學或軍事吧!

### 圖形結構 Structure of Graphs
不知道從什麼時候開始，某些無聊的人類開始幫不同長相的圖取名字，什麼 clique、tree 或是 hamiltonian cycle 之類的，然後就開始研究起他們的性質。這些討論無非就是在什麼情況下會產生什麼樣的結構，可能是節點數量、邊的數量或是最大/最小的度數會造就產生某些結構的 bound。像是如果要產生歐拉迴路的話，那節點度數就必須是偶數才有可能。

然而，在這個主題也產生了不少 open problem。像是找出圖中長度為 $k$ 的環，或是找 hamiltonian cycle。Somehow 我們都不知道產生這些結構的條件是什麼，只能說他們的共通點都是，當我們證完他們之後，就被丟到 [NP-complete 垃圾桶](https://youtu.be/HVbOHvChOQ8?si=Q77181Y_XZ57Aoq8&t=2265)，然後再也不理他們(?

備註 : hamiltonian cycle 可以是小寫，因為他太有名了

### 組合最佳化 Combinatorial Optimization
圖論的東西很適合拿來優化一些做事情的流程，所以被廣泛的應用。比如說用二分圖匹配來[誰要跟誰配對 (stable matching)](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm)，又像是最短路徑問題可以抽象化變成怪怪的東西之類的

所謂組合最佳化就是一個有限的集合中找出最佳解的一些問題。雖然集合是有限的，但是窮舉肯定不是最省事的辦法，因此我們需要想出演算法去解這些問題提升效率。如果是很難找到演算法的問題，我們就把這種問題跟其他已經知道演算法的問題搭「橋梁」，使得他們都可以用同一套算法解出來。像是 [Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)、[Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem)或[最大流量-最小割定理](https://hackmd.io/@ShanC/maxflow-mincut-theorem)都屬於這類「橋梁」

有意思的事，不只我們電腦科學跟數學會去討論這個主題，有修作業研究 (operations research) 的或許也會學到這些東西，因為真的很實用

## 圖論演算法 Graph Algorithms
基本上就是資工愛玩的東西，不論是演算法或是資料結構都有它的身影。會有這樣的現象，我認為是因為 :
- 圖論這個數學物件用於描述電腦裡儲存的資料非常方便，其中又以樹狀結構最為常用
- 在儲存資料之外，圖論某些良好的性質也很適合找資料
- 圖論的節點太多了，若是在電腦中算會快很多，或許可以拿來證明一些東西(? 嗯，我就是在說[四色定理](https://en.wikipedia.org/wiki/Four_color_theorem)

說白了其實就是上面古典的圖論在研究的東西，只是切換到計算的視角。這方面由於大多數人接觸圖論都是在演算法，基本上[我的筆記](https://hackmd.io/@ShanC/B1ouGxqcC#%E5%9C%96%E8%AB%96-Graph-Theory)已經囊括了一堆東西，所以就不細講。競程原則上會有這些主題 :

- 圖的 operation : DFS、BFS...
- 找東西 : 找環、找漢米爾頓路徑、找 SCC、找 BCC...
- 樹 : 生成樹、數一些東西、找祖先、找後代、壓平
- 最短路徑 : 單源最短路徑、全源最短路徑
- 怪東西 : 拓樸排序 (感覺就 [partial ordering](https://en.wikipedia.org/wiki/Partially_ordered_set))
- 計數 : 計算一些怪東西的數量
- 一些可以互相轉換的東西 : 流量網路、割、二分圖匹配...

大多數學的東西都有分「分析」跟「計算」兩個層面。分析是數學系在玩的事，計算就是我們電腦科學 (資工) 在玩的事情。同樣地，在找這些圖的性質在數學的工作，在計算上就是看如何實作然後去分析複雜度。兩者相輔相成，沒有計算這些東西就不知道在研究什麼鬼，沒有分析有些複雜度就降不下來，所以沒事不要搞歧視

## 圖著色 Graph Coloring
### 著色問題
這領域是在說，在圖上我們可以給一些東西著色，可能是節點、可能是邊，也有可能是平面圖的 region，我們希望使相鄰的兩者可以塗上不同顏色，那最少會是幾種顏色呢? Somehow 我們可以將平面圖的 region reduce 成節點著色的問題 ([用 dual graph](https://en.wikipedia.org/wiki/Dual_graph))，所以其實問題只有兩種而已 :
- 給一個 simple graph 來說，最少可以用幾種顏色，使相鄰兩節點圖上不同顏色?
- 給一個 simple graph 來說，最少可以用幾種顏色，使相鄰兩邊圖上不同顏色?

### Chromatic Number
關於這些問題，他們的上界還蠻明顯的嘛，無非就是和節點數、邊數或度數有關，但是下界呢? 組合學家們為此定義了兩個名詞 (不知道中文翻譯是什麼) :
- chromatic number : 寫作 $\chi(G)$，最少的顏色數使相鄰兩節點圖上不同顏色
- edge-chromatic number (chromatic index) : 寫作 $\chi'(G)$，最少的顏色數使相鄰兩邊圖上不同顏色

關於找出 $\chi(G)$ 與 $\chi'(G)$ 至今都還是很難的問題，所以從 De Morgan 那個時代至今，有很多人投入這領域的研究，但只能找到一些上界或是下界來估算。既然沒辦法直接算出來，那就換種圖的結構來玩玩，因此有人試圖去研究著色與結構 (像是 clique) 的關係，其中最著名的莫過於用於平面圖的[四色定理](https://en.wikipedia.org/wiki/Four_color_theorem)

### 四色定理 Four Color Theorem
四色定理是在說「若在平面上劃出一些相鄰的有限區域，那麼可以用四種顏色來給這些區域著色，使每兩個鄰接區域染的顏色都不同」這問題在很早以前就被提出來，因為畫地圖常需要用不同顏色來分辨不同國家，但是卻一直很難被證出來。有一個比較弱的定理叫[五色定理](https://en.wikipedia.org/wiki/Five_color_theorem)，這個比較好證。但是四色定理卻是麻煩許多，歷年來一直有人把問題 reduce 到一些 cases (最後總共是 1936 個)，到近代 (1976 年)才被電腦跑完所有 cases，被證明是正確的。但爭議點就在於，這並不是一個數學邏輯上的證明，比較像是做實驗所得到的成果，因此到現在都還有人在找證明去證四色定理

### 在電腦科學的視角
在煮飯先生 (Stephen Cook) 證明[第一個 NP-complete 問題](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem)後，隔年 (1972 年) Karp 就發表了[二十一個 NP-complete 問題](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems)，論文的產出速度真的是非常快。其中就包括找出 chromatic number ，因此這也是個 NP-complete 問題

## 拓樸圖論 Topological Graph Theory
### 把圖畫在其他平面!?
基本的東西在[上一篇](https://hackmd.io/@ShanC/basic-graph-theory-1#%E5%B9%B3%E9%9D%A2%E5%9C%96-Planar-Graph)就講過了，看過之後應該就有點感覺了吧! 基本上就是在玩平面圖與拓樸學之間的關係，是個有趣的東西。如下圖就是一個平面圖畫在甜甜圈上的例子

<center>
<img src="https://hackmd.io/_uploads/B1tMuy4Ulx.png" style="margin: 0 auto; display: block; width: 300px">
</center>

### 一些歷史
要說起拓樸與圖論的淵源，早期數學家們覺得只要不是跟幾何 (距離、角度等) 有關的空間問題都屬於拓樸，因此以前的圖論自然也被劃在拓樸學的範疇，直到 1936 年匈牙利人 [Dénes Kőnig](https://en.wikipedia.org/wiki/D%C3%A9nes_K%C5%91nig) 寫了第一本圖論的書，大家才開始對圖論生興趣。再加上 20 世紀初的那些拓樸學家們開始定義一些拓樸學的東西，兩邊才開始分家。如今兩者已經是不同領域，這在你分開圖論與拓樸學的書 (或是 baby Rudin 第二章) 的第一頁時就會發現

有意思的是那位寫過 [Topology](https://www.amazon.com/Topology-2nd-James-Munkres/dp/0131816292) 的 Munkres，剛好也是 [KM 演算法 (匈牙利演算法)](https://hackmd.io/@ShanC/Hungarian-Algorithm#%E5%82%99%E8%A8%BB) 的發明者之一 (就是代表字母 M)

還有就是匈牙利真的是一堆圖論學家，在學圖論的時候不遇到匈牙利人名都很難，根本可以自成一個匈牙利學派了吧

## 極圖論 Extremal Graph Theory

### 簡介 Introduction
極圖論是在說，給局部的圖一些條件，會造成整個圖有哪些影響。這些條件可能是如果沒有 $K_3$、或是沒有二分圖等。給個例子或許比較具體，像是 Mantel's theorem 說「大小為 $n$ 的圖若沒有 $K_3$ 作為子圖，則最多的邊數為 $\lfloor \frac{n^2}{4} \rfloor$」

受 Mantel's theorem 啟發，有人可能會猜測，一個不含 $K_{r+1}$ 的圖的最大邊數將是一個均衡完全 $r$-partite graph。所以就有了下面這位數學家 Turán (對，又是匈牙利人) 證出的定理

### Turán's Graph
Turán's graph $T_{n, r}$ 是一張 $K_{s_1, s_2, \dots, s_r}$，且 $s_1+s_2+\dots+s_r=n$，每個 $s_i$ 不是 $\lceil \frac{n}{r}\rceil$ 就是 $\lfloor \frac{n}{r}\rfloor$。如下圖就是一個 $T_{9, 4}$

<center>
<img src="https://hackmd.io/_uploads/BkE7YJAwgg.png" style="margin: 0 auto; display: block; width: 300px">
</center>

### Turán's Theorem
任何 $n$ 節點且不包含 $K_{r+1}$ 的圖有最多 $(1 - \frac{1}{r} )\frac{n^2}{2}$ 條邊

### $H$-free 的圖
其實就是在研究這圖沒有什麼東西時，圖會長什麼樣子。給一個圖 $H$ 我們說一張圖沒有 $H$ 作為子圖叫做 $H$-free 的圖 (跟我們點一杯 "sugar-free" 的飲料是一樣的邏輯)。顯然當我們從 $0$ 條邊開始加邊到圖裡面，總會到一個上限使得一定會出現某些圖。這領域常常跟著色或是古典的圖論問題弄在一起，有時候在隨機圖也會看到類似的東西，說實話其實很難分辨，但並不妨礙我們討論這門學問

### Extremal Number
給一個有 $n$ 節點的圖與另一個圖 $H$，$ex(n, H)$ 代表 $H$-free 圖的最大邊數

### 與加法組合學的關係
我還沒有時間去研究這塊，但是感覺還蠻有趣的。有興趣者可以看底下參考資料的推薦影片

## 隨機圖論 Random Graph
這領域研究的邊是隨機的。具體來說，通常會給一個圖 $G(n,p)$，代表給 $n$ 個點，每條邊都有 $p$ 的機率會出現，那圖會長什麼樣子呢?

這領域我也沒有深入研究過，大概知道而已。聽說在社群網路有很多研究，有興趣可以自己去玩玩看

## 代數圖論 Algebratic Graph Theory
這領域主要是用群論或是線性代數的方法來討論圖論，但因為我不會群論所以就點到為止

### 譜圖論 Spectral Graph Theory
有學過線性代數的人應該知道 "spectral" 是在做什麼吧! 沒錯，就是跟特徵值 (eigenvalue) 有關。具體來說是研究兩種矩陣的特徵值 : 鄰接矩陣與拉普拉斯矩陣。你可能會覺得矩陣特徵值跟圖本身有什麼關係呢? 我也不知道具體而言怎麼說，這我看很多資料還是覺得很玄，但我大概可以說一種感覺

#### 鄰接矩陣 Adjacency Matrix
矩陣的每個元素 $A_{i, j}$ 代表點對 $(i, j)$ 之間有連邊。假設你用一個向量去提取簡單圖的鄰接矩陣的話，那就相當於把人擺在你向量分量所對應到的節點上，然後看他們走長度為 $1$ 的 walk 後他們到其他點的可能數。如果我們把這套流程重複 $k$ 遍，那就相當於矩陣的 $k$ 次冪。所以你大概會發現鄰接矩陣就好像在描述每個節點往外擴散的狀況

#### 拉普拉斯矩陣 Laplacian Matrix
拉普拉斯矩陣就是 $L=D-A$，其中 $D_{i, i}$ 就是節點 $i$ 的度數。說起來我也還是不知道這樣定義到底是在做啥，感覺有點像是每個節點到另一個節點的「阻力」。這個東西最著名的是可以去做[圖的 cluster](https://www.youtube.com/watch?v=cxTmmasBiC8)，在機器學習上會用到。除此之外還有找圖的連通塊個數、找某些圖的結構或是[計算生成樹的個數 (矩陣樹)](https://hackmd.io/@ShanC/Cayleys-Formula-Prufer-Code#%E5%85%8B%E5%B8%8C%E8%8D%B7%E5%A4%AB%E7%9F%A9%E9%99%A3%E6%A8%B9%E5%AE%9A%E7%90%86-Kirchhoffs-Matrix-Tree-Theorem) 。在這些例子上都可能會用到拉普拉斯矩陣與它的特徵值

## Ramsey Theory
這東西有夠複雜，它原本不是長圖論的樣子，當初 [Ramsey](https://en.wikipedia.org/wiki/Frank_Ramsey_(mathematician)) 在 26 歲臨終前應該也沒想過會跟圖論扯上關係，但是這在圖論中也有許多討論。至於為什麼不是 theorem 而是 theory，我猜是因為真的太厲害了

簡單來說，這是在討論一個東西叫 Ramsey number，寫作 $R(s, t)$。它的定義如下 :

$R(s, t)=min\{n:|G|=n, ~K_s\subseteq G ~\text{or}~K_t\subseteq \overline{G}\}$

我們可以代一些數字進去看看。比如說 $R(3, 3)=6$，代表給 $6$ 個節點畫成一張圖的話，這張圖會出現 $K_3$ 或這圖的補圖會出現 $K_3$。想當然，$n=6$ 都可以達成這條件了，那 $n=7$ 個點或更多點一定也會符合條件。反著說就是若 $n=5$，那可能就沒辦法達成這條件

用邊著色的角度換句話說就是，「若將足夠大的完全圖各邊染紅藍兩色，則必定有紅色的 $s$-clique 或藍色的 $t$-clique」，那個完全圖的節點數就是 $R(s, t)$

老樣子，Ramsey 當初也只是說「存在」這樣子的數字而已。由於求 $R(s, t)$ 太難了，所以很多時候我們頂多只能求出一個 bound 而不能直接找出一個確切的數字

----

## 參考資料 / 推薦讀物 / 推薦影片
有興趣的可以去看看下面參考的連結還有書籍，有些我覺得講的還蠻有趣
- D.B.West Introduction to Graph Theory 2/e
- Reinhard Diestel Graph Theory
- [維基百科 - Graph theory](https://en.wikipedia.org/wiki/Graph_theory)
- [維基百科 - Graph coloring](https://en.wikipedia.org/wiki/Graph_coloring)
- [維基百科 - Four color theorem](https://en.wikipedia.org/wiki/Four_color_theorem)
- [維基百科 - Extremal graph theory](https://en.wikipedia.org/wiki/Extremal_graph_theory)
- [台師大演算法筆記 - complete graph](https://web.ntnu.edu.tw/~algo/CompleteGraph.html)
- [台師大演算法筆記 - graph](https://web.ntnu.edu.tw/~algo/Graph2.html)
- [線代啟示錄 - 線性代數在圖論的應用(一)：鄰接矩陣](https://ccjou.wordpress.com/2010/01/18/%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8%E5%9C%A8%E5%9C%96%E8%AB%96%E7%9A%84%E6%87%89%E7%94%A8-%E4%B8%80%EF%BC%9A%E9%84%B0%E6%8E%A5%E7%9F%A9%E9%99%A3/)
- [線代啟示錄 - 線性代數在圖論的應用 (三)：拉普拉斯矩陣](https://ccjou.wordpress.com/2014/12/04/%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8%E5%9C%A8%E5%9C%96%E8%AB%96%E7%9A%84%E6%87%89%E7%94%A8-%E4%B8%89%EF%BC%9A%E6%8B%89%E6%99%AE%E6%8B%89%E6%96%AF%E7%9F%A9%E9%99%A3/)
- [NYCU OCW - Lec09 組合學導論 拉姆齊定理 1 Ramsey Theory 1](https://www.youtube.com/watch?v=NVsjhoQ3FSw)
- [MIT 18.217 Graph Theory and Additive Combinatorics, Fall 2019](https://youtube.com/playlist?list=PLUl4u3cNGP62qauV_CpT1zKaGG_Vj5igX&si=WGXAzlljPJehbgab)

----

>上一篇: [基礎圖論 (二)](https://hackmd.io/@ShanC/basic-graph-theory-2)
>下一篇: [基礎圖論 (四)](https://hackmd.io/@ShanC/basic-graph-theory-4)

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/7/21