图论及其算法PDF电子书下载

1 通论 1

1.1 图论的内容与历史回顾 1

1.2 图的定义 5

1.3 轨道与连通 9

1.4 Brouwer不动点定理 13

1.5 Dijkstra算法 16

习题 20

2 树 26

2.1 树及其性质 26

2.2 生成树的个数 30

2.3 Kruskal算法 33

2.4 几类常用树 35

习题 44

3 连通性 47

3.1 连通性和Whitney定理 47

3.2 割顶、桥、块 50

3.3 可靠通讯网的构作 52

习题 55

4 可行遍性 57

4.1 Euler图 57

4.2 中国邮路问题 59

4.3 Hamilton图 62

4.4 货郎问题 69

习题 73

5 平面图 76

5.1 平面图的概念 76

5.2 Euler公式 78

5.3 平面图的对偶图 79

5.4 Kuratowsky定理 83

5.5 图的厚度 87

习题 90

6 纵深搜索算法与平面嵌入算法 92

6.1 广度与深度优先搜索法 92

6.2 平面嵌入算法 100

习题 107

7 匹配理论及其应用 109

7.1 匹配与许配 109

7.2 匹配基本定理 111

7.3 二分图中最大匹配与最佳匹配的算法 118

习题 123

8 支配集与独立集 126

8.1 支配集与独立集的概念 126

8.2 支配集、覆盖数和独立数的计算 128

8.3 支配集与独立集的应用 131

8.4 Ramsey数r(k,l) 133

习题 139

9 着色理论 141

9.1 边色数 141

9.2 Ramsey数和Schur定理 144

9.3 时间表问题 146

9.4 顶色数 149

9.5 面色数 151

9.6 颜色多项式 153

9.7 求色数的一个算法 157

习题 159

10 有向图 163

10.1 有向图的连通性 163

10.2 有向Euler图 165

10.3 有向轨 168

10.4 有向圈 171

习题 176

11 网络中的最大流 178

11.1 Ford和Fulkerson算法 178

11.2 Dinic算法 181

11.3 容量有上下界的网络 187

11.4 有供需约束的流 191

习题 193

12 网络流方法的应用 196

12.1 顶连通度 196

12.2 有向图的连通度和无向图的边连通度 200

12.3 有向图的边连通度和弱独立外向生成树 202

12.4 二分图 205

12.5 关于PERT的两个问题 208

习题 211

13 无向图中的空间与矩阵 216

13.1 圈空间 216

13.2 断集空间 219

13.3 关联矩阵 223

13.4 圈矩阵 226

13.5 割集矩阵 228

13.6 邻接矩阵与道路矩阵 230

13.7 开关网络 233

习题 242

14 有向图中的矩阵 246

14.1 邻接矩阵与道路矩阵 246

14.2 关联矩阵和生成树的数目 250

14.3 圈矩阵与割集矩阵 254

14.4 电路网络 256

习题 264

15 NPC概念与Cook定理 266

15.1 算法的好与坏 266

15.2 判定问题的NP类 268

15.3 NPC与Cook定理 272

15.4 NPC中的几人组合问题 278

习题 283

16 NPC中若干著名的图论问题 285

16.1 团、独立集和顶覆盖 285

16.2 Hamilton轨和Hamilton圈 286

16.3 图的色数 289

16.4 有向图的反馈集 291

16.5 Steiner树 292

16.6 最大断集 293

16.7 图的直线排列 296

16.8 多商品整流问题 299

习题 302

17 拟阵与图 305

17.1 定义与例 305

17.2 拟阵与图论 310

习题 314

习题答案或提示 316

参考文献 334