圖論導引

目錄
前言
緒論 1
第1章 圖的基本概念 8
1.1 圖的定義 8
1.2 頂點度數(shù) 10
1.3 子圖與圖的運算 13
1.4 路徑與連通 16
1.5 圖的同構 21
1.6 有向圖 23
1.7 *短路徑問題 24
習題 28
第2章 樹 31
2.1 樹的基本概念 31
2.2 生成樹 35
2.2.1 生成樹的定義 35
2.2.2 生成樹的計數(shù) 37
2.3 *小生成樹 39
2.3.1 Kruskal 算法 40
2.3.2 Prim 算法 42
2.3.3 破圈法 43
2.4 二叉樹及其應用 44
2.4.1 二叉樹 45
2.4.2 Huffman 樹 47
2.4.3 決策樹 52
習題 53
第3章 圖的連通性 56
3.1 頂連通度 56
3.2 扇形定理 62
3.3 邊連通度 65
3.4 割頂、橋與塊 66
3.5 可靠通信網的構造 69
習題 71
第4章 平面圖 74
4.1 平面圖及平面嵌入 74
4.1.1 平面圖 76
4.1.2 平面圖的Euler 公式 77
4.1.3 平面圖的性質 79
4.2 極大平面圖 80
4.3 可平面圖的判定 81
4.3.1 圖的厚度 83
4.3.2 可平面性算法？ 84
習題 91
第5章 匹配理論 93
5.1 兩個例子 93
5.2 匹配的定義 94
5.3 二分圖中的匹配 96
5.3.1 Hall 定理 96
5.3.2 匹配與覆蓋 98
5.4 任意圖的完備匹配 100
5.5 *大匹配算法 104
5.6 *佳匹配算法 109
習題 113
第6章 Euler 圖與Hamilton 圖 115
6.1 Euler 圖 115
6.1.1 Euler 圖的應用 117
6.1.2 Euler 回路算法 121
6.2 中國郵遞員問題 124
6.2.1 問題的提出 124
6.2.2 *優(yōu)投遞路線算法 125
6.3 Hamilton 圖 126
6.3.1 Hamilton 圖的定義 126
6.3.2 Hamilton 圖的判定條件 128
6.4 旅行商問題 135
6.4.1 *近鄰法 136
6.4.2 *小生成樹法 137
6.4.3 *小權匹配法 139
習題 141
第7章 圖的著色 144
7.1 頂點著色 144
7.1.1 頂點著色與色數(shù) 144
7.1.2 頂點著色的應用 145
7.2 邊著色 147
7.2.1 邊著色與邊色數(shù) 147
7.2.2 邊著色的應用 153
7.3 平面圖著色 156
7.3.1 平面圖著色 156
7.3.2 五色定理 157
7.3.3 Appel 和Haken 的機器證明？ 159
7.4 顏色多項式 166
習題 168
第8章 有向圖 171
8.1 有向圖 171
8.2 有向圖的連通性 172
8.3 競賽圖 174
8.4 有向Hamilton 圖 178
習題 183
第9章 網絡流理論 185
9.1 網絡與流函數(shù) 185
9.2 Ford-Fulkerson 算法 189
9.3 容量有上下界的網絡*大流 194
9.4 有供需需求的網絡流 200
9.5 網絡流在連通度中的應用 206
9.5.1 循環(huán) 207
9.5.2 Menger 定理 209
9.5.3 無向圖的連通性問題 210
9.6 本章 小結 211
習題 212
第10章 圖矩陣與圖空間 215
10.1 線性空間簡介 215
10.2 圖的空間 217
10.2.1 邊空間 217
10.2.2 圈空間 218
10.2.3 斷集空間 221
10.3 鄰接矩陣 225
10.3.1 無向圖的鄰接矩陣 225
10.3.2 有向圖的鄰接矩陣 227
10.4 關聯(lián)矩陣 231
10.4.1 無向圖的關聯(lián)矩陣 231
10.4.2 有向圖的關聯(lián)矩陣 235
10.5 開關網絡及其優(yōu)化 239
習題 247
第11章 無標度圖 251
11.1 無標度圖的概念和性質 251
11.2 圖的中心性指標 252
11.2.1 度中心性 252
11.2.2 接近中心性 253
11.2.3 中介中心性 254
11.3 圖上的若干算法 257
11.3.1 隨機游走 257
11.3.2 圖采樣 261
11.3.3 相似性 263
11.4 典型應用問題 265
11.4.1 影響力傳播 265
11.4.2 個性化推薦 267
11.4.3 PageRank 268
11.4.4 子圖模式分析 269
習題 270
第12章 圖計算系統(tǒng) 272
12.1 計算模型 272
12.1.1 以頂點為中心 273
12.1.2 以邊為中心 275
12.1.3 其他計算模型 276
12.2 存儲模型 277
12.2.1 數(shù)據(jù)存儲 277
12.2.2 數(shù)據(jù)訪問 279
12.3 典型的圖計算系統(tǒng) 282
12.3.1 GraphChi 282
12.3.2 X-Stream 285
12.3.3 Graphene 288
習題 290
參考文獻 291