演算法觀點的圖論

序（摘錄）

圖論這門學問有將近三百年的歷史，經由各方學者的研究，已經有很完整的發展，不但有在數學上的深度，在其他領域上也有很多應用。很少有一個數學的分支可以說是哪一年誕生的，而現在大家公認，Euler在1736年解決Königsberg七橋問題的文章是圖論的起源。

從1736年到1936年這整整兩百年，可以說是圖論的春秋戰國時代，不同領域的人們在他們各自的崗位上，用不同的名稱、不同的內容，探索和Euler發現的圖類似的概念。著名的包括四色問題[1852]和Hamilton問題[1856]。也有用圖當作工具去解決其他領域中一些問題的結果，例如，Kirchhoff [1847]用圖的概念來研究電的網路方程組問題，Cayley [1857]用樹的概念研究有機化合物的分子結構問題。進入二十世紀30年代，更出現了許多精彩的結果，例如Menger定理[1927]、Kuratowski定理[1930]和Ramsey定理[1930]等等。到了1936年，Kőnig寫出第一本圖論專著《有限和無限圖的理論》，正式宣告圖論這門學問誕生。

1936年以後，由於生產管理、軍事、交通運輸、電腦和通訊網路等等各方面許多離散數學問題的出現，大大促進了圖論的發展。特別是1970年代以後，大型電腦的出現，使得大規模問題的求解成為可能，圖論和它在許多領域的應用呈現「爆炸性的發展」，各式各樣圖論的書籍以幾何級數的速度產生，本書就是其中之一。在圖的理論方面，膾炙人口的結果包含：Appel、Haken和Koch [1977]藉由電腦的幫助，透過「放電論證法」證明四色問題；Robertson和Seymour從1983年到2004年在Journal of Combinatorial Theory, Series B發表一連串20篇，總共超過500頁的文章，奠定了次圖（graph minor）相關的重要理論；Chudnovsky、Robertson、Seymour和Thomas [2006]在Annals of Mathematics發表了一篇長達179頁的論文，證明了Berge在1960 年代提出的著名的「強完美圖猜測」。

從研究圖論的方法來說，一些數學其他分支的工具，常常被用來解決圖論的問題。一個有名的例子是，Lovász [1978]利用代數拓樸的方法解決了Kneser猜測[1955]，這等同於決定了Kneser圖的著色數。另一個有名的例子是，Erdős開創了機率方法在圖論上的應用，這個方法經由Alon和Spencer的推廣宣傳，現在已經成為圖論（或更一般來說，組合數學）的重要方法。另外，Tutte用代數上的Pfaffian當作工具，給出一個圖有完美匹配的刻畫，雖然現在人們已經可以不用代數方法證明；Tutte原來的證明，對於近代利用平行演算法求最大匹配的數目仍有極大幫助。由於圖的本質上是離散的，所以演算法在圖論的研究上隨處可見。

這本書要特別強調演算法在圖論所扮演的角色。從圖論在其他領域的應用方面來說，把實際問題化成圖論模型，設計出有效的演算法，再經由電腦的快速計算，對實用端有很大的好處。從數學的眼光來看，雖然在演算法理論中有各式各樣好聽的名詞：動態規劃、分治法、修剪和搜尋法、貪求法等等，但是它們的內在本質都是數學歸納法。圖論中的許多定理基本上都可以用數學歸納法證明，所以證明本身也蘊藏著演算法，有時候，利用演算法或是它的精神也可以提供有用的證明。這本書要在各處盡可能地展現數學歸納法和演算法的一體兩面特性。另外，對於各個定理盡量提供目前已知的最簡單、最直接的證明，對於一部分定理也提供多種不同的證明方法和角度，希望能刺激讀者們的思考和回饋。

這本書分成兩部分。第一部分從第1章到第8章，包含圖論的基礎知識，可以當作一個學期的教材；對於進度比較快，而沒有第二學期的課堂，可以適當選擇第二部分的某些章節加入授課；對於進度比較慢的課堂，可以適當捨去各章後面的一兩節，例如打*號的節次。第二部分從第9章到第15章，包含圖論一些常見的專題，可以當作第二學期的教材，必要的時候，可以輔以最新的論文；這部分沒有打*號節次的建議，主要是由授課老師自行斟酌。

本人歷年來在中央大學、交通大學、臺灣大學開授圖論課程，每次挑選教科書都不容易找到符合自己想法的書，因為有些定理明明可以直接由定義不難證明出來，偏偏有些書就要繞一大圈。從正確性來說，倒是沒問題，但是從對一件事情了解的角度來說，似乎沒有看到證明的最主要部分，未達到「洞察本質」的精神，就常在課堂上或一些場合「批判」這些證明方法，心中也偶爾有何不自己寫一本書的念頭。中央大學數學系廖勝強教授有一次就建議，何不寫一本中文的圖論教科書，除了讓大學老師授課使用，也可以給一些聰明的高中生自修使用，並且提供給有興趣的各類讀者參考。

序（摘錄）

圖論這門學問有將近三百年的歷史，經由各方學者的研究，已經有很完整的發展，不但有在數學上的深度，在其他領域上也有很多應用。很少有一個數學的分支可以說是哪一年誕生的，而現在大家公認，Euler在1736年解決Königsberg七橋問題的文章是圖論的起源。

從1736年到1936年這整整兩百年，可以說是圖論的春秋戰國時代，不同領域的人們在他們各自的崗位上，用不同的名稱、不同的內容，探索和Euler發現的圖類似的概念。著名的包括四色問題[1852]和Hamilton問題[1856]。也有用圖當作工具去解決其他領域中一些問題的結果，例如，Kirchhof...

序
目次
圖目次
符號表

第一部　基礎篇
1 通論
1.1 圖論緣起——話說1736年
1.2 圖的定義
1.3 路徑
1.4 Euler圖
1.5 Euler迴路的應用
*1.6 度序列
*1.7 證明Brouwer定點定理
1.8 習題
1.9 參考文獻
2 演算法簡介
2.1 演算法起源
2.2 演算法的複雜度
2.3 資料結構
2.4 表列和圖的表示法
2.5 Euler迴路的案例
*2.6 聯集尋找問題
2.7 習題
2.8 參考文獻
3 樹
3.1 樹是簡單但重要的圖
3.2 樹的基本性質
3.3 樹的中心問題
3.4 樹或圖的遍歷搜尋法
3.5 生成樹計數
*3.6 最小生成樹
3.7 習題
3.8 參考文獻
4 匹配
4.1 婚姻問題面面觀
4.2 匹配和完美匹配
4.3 二分圖匹配
*4.4 加權二分圖匹配
4.5 一般圖匹配
*4.6 Edmonds花被演算法
4.7 穩定婚姻問題
4.8 習題
4.9 參考文獻
5 圖的連通度
5.1 團結在一起
5.2 連通度和邊連通度
5.3 2-連通圖
5.4 k-連通圖和Menger定理
5.5 最小連通圖
*5.6 網路流問題
5.7 習題
5.8 參考文獻
6 平面圖
6.1 老死不相往來的誓言
6.2 平面圖
6.3 Euler多面體公式
6.4 Kuratowski定理
6.5 外圍平面圖
*6.6 平面程度的度量
6.7 習題
6.8 參考文獻
7 圖著色
7.1 地圖著色
7.2 點著色數和它的上界
7.3 點著色數的下界
7.4 平面圖著色
7.5 邊著色
*7.6 列表著色
7.7 習題
7.8 參考文獻
8 Hamilton圈
8.1 環遊世界
8.2 有Hamilton圈的必要條件
8.3 有Hamilton圈的充分條件
8.4 平面圖的Hamilton圈
8.5 有向圖的Hamilton圈
*8.6 推銷員問題
8.7 習題
8.8 參考文獻

第二部　專題篇
9 完美圖
9.1 Shannon零錯容量
9.2 完美圖定義和猜想
9.3 可比圖：第一類傳統完美圖
9.4 弦圖：第二類傳統完美圖
9.5 檢驗弦圖
9.6 完美圖定理
9.7 通往強完美圖定理的道路
9.8 習題
9.9 參考文獻
10 Ramsey理論
10.1 幸福結局問題
10.2 第二層Ramsey數
10.3 Ramsey定理
10.4 圖Ramsey數
10.5 任意長度等差數列
10.6 證明van der Waerden定理
10.7 習題
10.8 參考文獻
11 極值圖論
11.1 令人瘋狂的樂趣
11.2 禁用完全圖
11.3 禁用完全二分圖
11.4 禁用完全多分圖
11.5 禁用路徑圖
11.6 禁用圈圖
11.7 習題
11.8 參考文獻
12 機率方法
12.1 計數的藝術
12.2 機率空間
12.3 期望值
12.4 更動法
12.5 二階矩法和門檻函數
12.6 局部引理
12.7 習題
12.8 參考文獻
13 代數方法
13.1 圖論和代數關係密切
13.2 圖的特徵值
13.3 圖參數和特徵值的關係
13.4 特殊圖的特徵值
13.5 強正則圖
13.6 組合零點定理
13.7 習題
13.8 參考文獻
14 擬陣
14.1 擬陣起源
14.2 繼承系統
14.3 擬陣基本性質
14.4 對偶擬陣
14.5 擬陣和平面圖
14.6 擬陣相交
14.7 擬陣和
14.8 習題
14.9 參考文獻
15 NP-完全問題
15.1 難中之難、無過此難
15.2 Turing機器
15.3 Cook定理
15.4 點覆蓋、獨立集和點團
15.5 路徑和圈
15.6 著色問題
15.7 習題
15.8 參考文獻

索引

序
目次
圖目次
符號表

第一部　基礎篇
1 通論
1.1 圖論緣起——話說1736年
1.2 圖的定義
1.3 路徑
1.4 Euler圖
1.5 Euler迴路的應用
*1.6 度序列
*1.7 證明Brouwer定點定理
1.8 習題
1.9 參考文獻
2 演算法簡介
2.1 演算法起源
2.2 演算法的複雜度
2.3 資料結構
2.4 表列和圖的表示法
2.5 Euler迴路的案例
*2.6 聯集尋找問題
2.7 習題
2.8 參考文獻
3 樹
3.1 樹是簡單但重要的圖
3.2 樹的基本性質
3.3 樹的中心問題
3.4 樹或圖的遍歷搜尋法
3.5 生成樹計數
*3.6 最小生成樹
3.7 習題
3.8 參考文獻
4 ...