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

第1章 图的基本概念 1

1.1 图的概念 1

1.2 同构 5

1.3 图的矩阵和顶点的度 9

1.4 子图 11

1.5 路和连通性 14

1.6 圈 18

1.7 最短路问题 19

第2章 树 23

2.1 树和割边 23

2.2 边割和键 28

2.3 割点 34

2.4 连线问题 36

2.5 生成树的计数及Cayley公式 39

3.1 连通度 42

第3章 连通度 42

3.2 块 45

3.3 Menger定理 48

3.4 可靠通信网的建设问题 54

3.5 边的共圈性及共闭迹性 54

第4章 遍历问题 57

4.1 Euler环游 57

4.2 最优环游 59

4.3 Hamilton圈 62

4.4 旅行售货员问题 67

4.5 Hamilton问题进阶 69

第5章 匹配 74

5.1 匹配 74

5.2 独立集、团、覆盖和匹配间的关系 76

5.3 偶图的匹配和覆盖 77

5.4 完美匹配 82

5.5 人员分派问题 86

5.6 最优分派问题 89

5.7 稳定匹配 92

第6章 着色问题 100

6.1 边着色 100

6.2 排课表问题 107

6.3 顶点着色和色数 108

6.4 Brooks定理 116

6.5 围长和色数 117

第7章 平面图 119

7.1 平图和平面图 119

7.2 对偶图 124

7.3 Kuratowski定理 126

7.4 五色定理和四色猜想 129

7.5 平面性算法 135

第8章 有向图 138

8.1 有向图 138

8.2 竞赛图 143

8.3 有向Hamilton圈 147

第9章 网络 150

9.1 流 150

9.2 最大流最小割定理 156

9.3 Menger定理进阶 161

9.4 可行流 165

第10章 NP-完全问题 171

10.1 引言 171

10.2 优化问题的三种提法 171

10.3 P类和NP类 173

10.4 多项式变换及NP-完全性 179

10.5 Cook定理 180

10.6 六个基本NPC问题 182

习题提示 191

习题解答 194

参考文献 270