目錄
目錄
前言
第1章 圖的基本概念 1
1 1 圖論發展歷史與特點 1
1 1 1 圖論起源 1
1 1 2 圖論發展 2
1 1 3 圖論現狀與特點 3
1 2 圖的定義 5
1 2 1 定義 5
1 2 2 度 7
1 2 3 同構 9
1 3 子圖和連通分支 9
1 3 1 子圖 9
1 3 2 導出子圖 10
1 3 3 連通分支 11
1 3 4 距離和中心 13
習題一 14
第2章 重要圖類與圖運算 18
2 1 重要圖類 18
2 1 1 完全圖 18
2 1 2 正則圖 19
2 1 3 二部圖 20
2 1 4 其他常見的圖 21
2 2 有向圖 23
2 2 1 定義 23
2 2 2 基礎圖 24
2 2 3 出度和入度 24
2 2 4 有向途徑 25
2 2 5 強連通分支 25
2 3 網絡 26
2 3 1 無向網絡和有向網絡 26
2 3 2 Dijkstra 算法 27
2 4 矩陣表示 30
2 4 1 鄰接矩陣 30
2 4 2 Laplace矩陣 33
2 4 3 關聯矩陣 33
2 4 4 可達矩陣 35
2 5 運算 37
2 5 1 刪去、添加和補圖 37
2 5 2 交和並 38
2 5 3 收縮和剖分 39
2 5 4 笛卡兒積 39
2 5 5 克羅內克積 40
習題二 41
第3章 樹及其算法 47
3 1 樹和森林 47
3 1 1 樹的基本概念 47
3 1 2 破圈法和避圈法 47
3 1 3 六個等價命題 49
3 2 支撐樹的計數 52
3 2 1 遞推公式 52
3 2 2 矩陣-樹定理 54
3 3 樹上頂點和邊的性質 58
3 3 1 割邊 58
3 3 2 邊割 59
3 3 3 割點 62
3 4 最小支撐樹 63
3 4 1 定義 64
3 4 2 Prim算法 64
3 4 3 Kruskal算法 67
3 5 二元樹與前綴碼 69
3 5 1 二元樹 69
3 5 2 有序二元樹的個數 70
3 5 3 前綴碼 73
3 5 4 Huffman樹 74
3 6 與樹有關的猜想 76
3 6 1 優美樹猜想 76
3 6 2 強九龍樹猜想 76
3 6 3 Erdos-Sos猜想 78
習題三 78
第4章 最大流及其算法 83
4 1 網絡模型 83
4 1 1 容量網絡 83
4 1 2 流 84
4 1 3 流值 85
4 1 4 最大流 85
4 2 最大流算法 87
4 2 1 增廣鏈 87
4 2 2 最大流 Ford-Fulkerson算法 88
4 2 3 最大流最小截定理 93
4 2 4 最短增廣鏈算法 96
4 3 最小費用最大流 98
4 3 1 問題描述 99
4 3 2 f 增廣圈 99
4 3 3 Klein算法 101
習題四 103
第5章 遍歷性及其算法 109
5 1 Euler圖和有向Euler圖 109
5 1 1 定義 109
5 1 2 Fleury算法 111
5 1 3 編碼盤設計 114
5 2 中國郵遞員問題 115
5 2 1 問題描述 115
5 2 2 奇偶點圖上作業法 117
5 3 Hamilton圖 120
5 3 1 定義 120
5 3 2 閉包 121
5 3 3 格雷碼與立方體的 Hamilton圈 125
5 4 有向 Hamilton圖 126
5 4 1 強連通的充要條件 126
5 4 2 Hamilton回路 127
5 4 3 有向Hamilton圖的充分條件 129
5 5 連通度和邊連通度 134
5 5 1 定義 134
5 5 2 2 連通圖 136
5 5 3 3 連通圖 137
5 6 堅韌度 138
5 6 1 定義 139
5 6 2 邊堅韌度 141
5 7 相關猜想 142
5 7 1 關於Hamilton圖的 Graffiti PC猜想 142
5 7 2 Chvatal猜想 143
習題五 143
第6章 最立集及其算法 149
6 1 最立集和覆蓋 149
6 1 1 最立數和覆蓋數 149
6 1 2 性質 150
6 1 3 極大最立集的計算 151
6 1 4 最立集與連通度的聯繫 152
6 2 Ramsey數 154
6 2 1 定義 154
6 2 2 Ramsey數的上界 156
6 2 3 Ramsey數的下界 157
6 2 4 廣義Ramsey數 159
6 2 5 類似Ramsey數的問題 163
6 2 6 Turan定理 165
6 3 頂點著色 169
6 3 1 色數 169
6 3 2 色數上界 170
6 3 3 色數的下界 173
6 3 4 色多項式 175
6 4 支配集 180
6 4 1 定義 181
6 4 2 性質 181
6 4 3 極小支配集的計算 182
習題六 184
第7章 匹配及其算法 189
7 1 邊最立集和邊覆蓋 189
7 1 1 邊最立數和邊覆蓋數 189
7 1 2 完美匹配 191
7 2 邊著色 192
7 2 1 邊色數 192
7 2 2 Vizing定理 193
7 2 3
第1類圖和第二類圖 195
7 3 二部圖的最大匹配 198
7 3 1 M飽和頂點 199
7 3 2 M增廣鏈 199
7 3 3 Hall定理 201
7 3 4 匈牙利算法 204
7 3 5 Tutte定理 204
7 4 最優匹配 207
7 4 1 最優匹配的概念 208
7 4 2 可行頂標 208
7 4 3 Kuhn-Munkres算法 210
習題七 214
第8章 平面性及其算法 221
8 1 平面圖 221
8 1 1 平面圖和平圖 221
8 1 2 對偶圖 223
8 2 Euler 公式和平面圖必要條件 224
8 2 1 Euler 公式 224
8 2 2 平面圖的必要條件 226
8 3 極大平面圖和極大外平面圖 228
8 3 1 極大平面圖 228
8 3 2 極大外平面圖 228
8 4 Kuratowski定理 230
8 4 1 剖分圖和H分枝 230
8 4 2 Kuratowski定理 232
8 5 四色問題 235
8 5 1 四色問題的三種數學描述 235
8 5 2 五色定理 237
8 6 平面性檢測算法 238
8 6 1 DMP算法 238
8 6 2 DMP算法的證明 241
習題八 243
第9章 應用案例拓展 246
9 1 圖上隨機遊走 246
9 1 1 隨機遊走概念 246
9 1 2 遊走矩陣的性質 248
9 1 3 惰性隨機遊走的穩態分佈 249
9 1 4 帶吸收態的隨機遊走 252
9 1 5 隨機遊走在圖像分割中的應用 255
9 1 6 小結 258
9 2 圖能量及其應用 259
9 2 1 圖能量的定義 259
9 2 2 圖能量的計算 262
9 2 3 Laplace能量 265
9 2 4 圖能量在蛋白質序列二維圖形表示中的應用 266
9 2 5 小結 268
9 3 智能集群控制中的圖論問題 268
9 3 1 Laplace結構可控性 268
9 3 2 最小完美關鍵集 272
9 3 3 關鍵集的一個充分條件 274
9 3 4 簡化圖 276
9 3 5 k最小完美關鍵集 (2≦k≦3) 276
9 3 6 最立關鍵集的圖特徵 279
9 3 7 支配集在最小領航集中的應用 281
9 3 8 小結 282
習題九 283
參考文獻 285
詳細資料或其他書籍請至台灣高等教育出版社查詢，查後請於客服中心或Line或本社留言板留言，我們即儘速上架。