第1章 图的概念 1
1.1什么是图？ 6
习题1-1 11
1.2图的同构 11
习题1-2 23
1.3子图 24
习题1-3 28
1.4路和连通性 28
习题1-4 37
1.5圈 38
习题1-5 41
1.6图的数据结构 42
习题1-6 50
第2章 最短路问题 52
2.1最短路问题与Dijkstra算法 52
习题2-1 58
2.2Bellman-Ford算法 59
习题2-2 65
2.3Floyd-Warshall算法 65
习题2-3 68
2.4最短路问题的应用 69
习题2-4 75
第3章 树与最优树 76
3.1树的概念 76
习题3-1 80
3.2生成树、余树和键 81
习题3-2 85
3.3生成树的计数及Caley公式 86
习题3-3 88
3.4树的应用 88
习题3-4 102
第4章 匹配与覆盖 103
4.1匹配 103
习题4-1 106
4.2独立集、团、覆盖和匹配及其之间的关系 107
习题4-2 108
4.3偶图的匹配和覆盖 108
习题4-3 113
4.4完美匹配 114
习题4-4 118
4.5匹配的应用 118
习题4-5 133
第5章 遍历问题 135
5.1Euler环游 135
习题5-1 139
5.2中国邮递员问题 140
习题5-2 144
5.3Hamilton圈 144
习题5-3 153
5.4旅行售货员问题 154
习题5-4 158
第6章 网络流问题 159
6.1网络与流 159
习题6-1 162
6.2网络最大流 163
习题6-2 176
6.3最小费用流问题 177
习题6-3 182
6.4可行流 183
习题6-4 189
第7章 连通度问题 190
7.1连通度 190
习题7-1 193
7.2块 193
习题7-2 196
7.3Menger定理 197
习题7-3 200
7.4节 可靠通信网的建设问题 200
习题7-4 202
第8章 着色问题 204
8.1边色数 204
习题8-1 210
8.2排课表问题 211
习题8-2 213
8.3色数 213
习题8-3 221
8.4Brooks定理、围长 222
习题8-4 224
第9章 平面图 226
9.1平图和平面图 226
习题9-1 231
9.2对偶图 232
习题9-2 234
9.3Kuratowski定理 234
9.4五色定理和四色猜想 236
习题9-4 238
9.5平面性算法 239
习题9-5 243
参考文献 244