●前言
緒論 1
第1章 圖的基本概念 8
1.1 圖的定義 8
1.2 頂點度數 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 生成樹的計數 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 很優投遞路線算法 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 頂點著色與色數 144
7.1.2 頂點著色的應用 145
7.2 邊著色 147
7.2.1 邊著色與邊色數 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 網絡與流函數 185
9.2 Ford-Fulkerson 算法 189
9.3 容量有上下界的網絡優選流 194
9.4 有供需需求的網絡流 200
9.5 網絡流在連通度中的應用 206
9.5.1 循環 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 關聯矩陣 231
10.4.1 無向圖的關聯矩陣 231
10.4.2 有向圖的關聯矩陣 235
10.5 開關網絡及其優化 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章 圖計算繫統 272
12.1 計算模型 272
12.1.1 以頂點為中心 273
12.1.2 以邊為中心 275
12.1.3 其他計算模型 276
12.2 存儲模型 277
12.2.1 數據存儲 277
12.2.2 數據訪問 279
12.3 典型的圖計算繫統 282
12.3.1 GraphChi 282
12.3.2 X-Stream 285
12.3.3 Graphene 288
習題 290
參考文獻 291

本書主要分為基礎知識與應用兩個部分。在基礎知識部分，繫統地介紹了圖論的基本概念、理論和方法,具體內容包括圖的基本概念、樹、圖的連通性、平面圖、匹配理論、Euler圖與Hamilton圖、圖的著色、有向圖、網絡流理論以及圖矩陣與圖空間，共十章。在應用部分，主要介紹了近年來圖計算方面的一些典型應用和繫統，具體內容包括無標度圖與圖計算繫統兩章。每章後面都附有一定數量的習題，供讀者練習和進一步思考。
本書可以作為高等學校應用數學、計算機科學技術、信息技術以及管理等專業高年級本科生與研究生的必修課或選修課教材，也可作為圖計算相關研究方向的高校老師與科研工作者的參考書。