圖論

第一章 圖
1.1 從哥尼斯堡七橋問題談起
1.2 圖的基本概念
1.3 軌道和圈
1.4 Brouwer不動點定理
1.5 求最短軌長度的算法
1.6 圖上博弈
習(xí)題
第二章 樹
2.1 樹的定義與性質(zhì)
2.2 生成樹的個數(shù)
2.3 求生成樹的算法
2.4 求最優(yōu)樹的算法
2.5 有序二元樹
2.6 n頂有序編碼二元樹的數(shù)目
2.7 最佳追捕問題
習(xí)題
第三章 平面圖
3.1 平面圖及其平面嵌入
3.2 平面圖Euler公式
3.3 極大平面圖
3.4 平面圖的充要條件
3.5 平面嵌入的灌木生長算法
習(xí)題
第四章 匹配理論及其應(yīng)用
4.1 匹配與許配
4.2 匹配定理
4.3 匹配的應(yīng)用
4.4 圖的因子分解
習(xí)題
第五章 著色理論
5.1 圖的邊著色
5.2 圖的頂著色
5.3 四色猜想為真的機器證明
5.4 顏色多項式
5.5 獨立集
5.6 Ramsey數(shù)
習(xí)題
第六章 Euler圖和Hamilton圖
6.1 Euler圖
6.2 中國郵遞員問題
6.3 Hamilton圖
習(xí)題
第七章 有向圖
7.1 弱連通、單連通與強連通
7.2 循環(huán)賽圖、有向軌和王
7.3 有向Hamilton圖
習(xí)題
第八章 最大流的算法
8.1 2F算法
8.2 Dinic分層算法
8.3 有上下界網(wǎng)絡(luò)最大流的算法
8.4 有供需要求的網(wǎng)絡(luò)流算法
習(xí)題
第九章 連通度
9.1 頂連通度
9.2 邊連通度
9.3 一種邊數(shù)最少的k連通圖
習(xí)題
第十章 圖的線性空間與矩陣
10.1 圖的線性空間
1O.2 圖矩陣
習(xí)題
第十一章 圖論中的NPC問題
11.1 問題、實例和算法的時間復(fù)雜度
11.2 Turing機和NPC
11.3 滿足問題和Cook定理
11.4 圖論中的一些NPC問題
習(xí)題
習(xí)題解答與提示
參考文獻(xiàn)