目錄
第一章 圖 1
1.1 從哥尼斯堡七橋問題談起 1
1.2 圖的基本概念 4
1.3 軌道和圈 10
*1.4 Brouwer不動(dòng)點(diǎn)定理 15
1.5 求最短軌長度的算法 17
*1.6 圖上博弈 19
習(xí)題 23
第二章 樹 28
2.1 樹的定義與性質(zhì) 28
2.2 生成樹的個(gè)數(shù) 31
2.3 求生成樹的算法 32
2.4 求最優(yōu)樹的算法 36
2.5 有序二元樹 37
2.6 n頂有序編碼二元樹的數(shù)目 42
*2.7 最佳追捕問題 45
習(xí)題 48
第三章 平面圖 50
3.1 平面圖及其平面嵌入 50
3.2 平面圖Euler公式 52
3.3 極大平面圖 53
3.4 平面圖的充要條件 56
*3.5 平面嵌入的灌木生長算法 59
習(xí)題 65
第四章 匹配理論及其應(yīng)用 67
4.1 匹配與許配 67
4.2 匹配定理 69
4.3 匹配的應(yīng)用 76
4.4 圖的因子分解 80
習(xí)題 82
第五章 著色理論 84
5.1 圖的邊著色 84
5.2 圖的頂著色 91
*5.3 四色猜想為真的機(jī)器證明 95
5.4 顏色多項(xiàng)式 101
5.5 獨(dú)立集 105
5.6 Ramsey數(shù) 111
習(xí)題 119
第六章 Euler圖和Hamilton圖 122
6.1 Euler圖 122
6.2 中國郵遞員問題 126
6.3 Hamilton圖 130
習(xí)題 136
第七章 有向圖 138
7.1 弱連通、單連通與強(qiáng)連通 138
7.2 循環(huán)賽圖、有向軌和王 141
7.3 有向Hamilton圖 144
習(xí)題 149
第八章 最大流的算法 150
8.12 F算法 150
*8.2 Dinic分層算法 153
8.3 有上下界網(wǎng)絡(luò)最大流的算法 157
8.4 有供需要求的網(wǎng)絡(luò)流算法 160
8.5 關(guān)于PERT的兩個(gè)問題 161
習(xí)題 164
第九章 連通度 167
9.1 頂連通度 167
9.2 邊連通度 171
*9.3 一種邊數(shù)最少的k連通圖 174
習(xí)題 175
第十章 圖的線性空間與矩陣 177
10.1 圖的線性空間 177
10.2 圖矩陣 183
10.3 開關(guān)網(wǎng)絡(luò) 194
習(xí)題 201
第十一章 圖論中的NPC問題 204
11.1 問題、實(shí)例和算法的時(shí)間復(fù)雜度 204
11.2 Turing機(jī)和NPC 206
11.3 滿足問題和Cook定理 209
11.4 圖論中的一些NPC問題 212
習(xí)題 221
習(xí)題解答與提示 223
參考文獻(xiàn) 239