圖論導(dǎo)引

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