图论及其应用PDF电子书下载

第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