《图论及其算法》求取 ⇩

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