Graph Theory, with an Algorithmic Perspective (Revised Edition)
Gerard Jennhwa Chang, Mu-Tsun Tsai
- PublishedAugust, 2020
- Binding平裝 / 23*17 / 476pages / 單色(黑) / 中文
- Publisher國立臺灣大學出版中心
- SeriesEducation－Textbooks
- ISBN978-986-350-406-1
- GPN1010901019
- Price NT$650
- Paper Books San Min Books / wunan / books.com.tw / National Books / iRead / eslite / TAAZE /
- Preview Google Books
修訂版序
初版序
目錄
圖目錄
符號表
第一部 基礎篇
1 圖論緣起
1.1 話說1736年
1.2 圖的定義
1.3 路徑
1.4 Euler圖的存在性與演算法
1.5 Euler迴路的應用
*1.6 度序列
*1.7 證明Brouwer定點定理
習題
參考文獻
2 演算法簡介
2.1 演算法起源
2.2 演算法的複雜度
2.3 資料結構
2.4 表列和圖的表示法
2.5 Euler迴路的案例
*2.6 聯集尋找問題
習題
參考文獻
3 樹
3.1 樹是簡單但重要的圖
3.2 樹的基本性質
3.3 樹的中心問題
3.4 樹或圖的遍歷搜尋法
3.5 生成樹計數
*3.6 最小生成樹
習題
參考文獻
4 匹配
4.1 婚姻問題面面觀
4.2 匹配和完美匹配
4.3 二分圖匹配
*4.4 加權二分圖匹配
4.5 一般圖匹配
*4.6 Edmonds花被演算法
4.7 穩定婚姻問題
習題
參考文獻
5 圖的連通度
5.1 團結在一起
5.2 連通度和邊連通度
5.3 2-連通圖
5.4 k-連通圖和Menger定理
5.5 最小連通圖
*5.6 網路流問題
習題
參考文獻
6 平面圖
6.1 老死不相往來的誓言
6.2 平面圖
6.3 Euler多面體公式
6.4 Kuratowski定理
6.5 外圍平面圖
*6.6 平面程度的度量
習題
參考文獻
7 圖著色
7.1 地圖著色
7.2 點著色數和它的上界
7.3 點著色數的下界
7.4 平面圖著色
7.5 邊著色
*7.6 列表著色
習題
參考文獻
8 Hamilton圈
8.1 環遊世界
8.2 有Hamilton圈的必要條件
8.3 有Hamilton圈的充分條件
8.4 平面圖的Hamilton圈
8.5 有向圖的Hamilton圈
*8.6 推銷員問題
習題
參考文獻
第二部 專題篇
9 完美圖
9.1 Shannon零錯容量
9.2 完美圖定義和猜想
9.3 可比圖：第一類傳統完美圖
9.4 弦圖：第二類傳統完美圖
9.5 檢驗弦圖
9.6 完美圖定理
9.7 通往強完美圖定理的道路
習題
參考文獻
10 Ramsey理論
10.1 幸福結局問題
10.2 第二層Ramsey數
10.3 Ramsey定理
10.4 圖Ramsey數
10.5 任意長度等差數列
10.6 證明van der Waerden定理
習題
參考文獻
11 極值圖論
11.1 令人瘋狂的樂趣
11.2 禁用完全圖
11.3 禁用完全二分圖
11.4 禁用完全多分圖
11.5 禁用路徑圖
11.6 禁用圈圖
習題
參考文獻
12 機率方法
12.1 計數的藝術
12.2 機率空間
12.3 期望值
12.4 更動法
12.5 二階矩法和門檻函數
12.6 局部引理
習題
參考文獻
13 代數方法
13.1 圖論和代數關係密切
13.2 圖的特徵值
13.3 圖參數和特徵值的關係
13.4 特殊圖的特徵值
13.5 強正則圖
13.6 組合零點定理
習題
參考文獻
14 擬陣
14.1 擬陣起源
14.2 繼承系統
14.3 擬陣基本性質
14.4 對偶擬陣
14.5 擬陣和平面圖
14.6 擬陣相交
14.7 擬陣和
習題
參考文獻
15 NP-完全問題
15.1 難中之難、無過此難
15.2 Turing機器
15.3 Cook定理
15.4 點覆蓋、獨立集和點團
15.5 路徑和圈
15.6 著色問題
習題
參考文獻
索引