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

第1章 图的基本概念 1

1.1 图论发展简史 1

1.2 图的概念 3

1.2.1 图 4

1.2.2 子图 5

1.2.3 一些重要类型的图 6

1.3 顶点的度和图的同构 7

1.3.1 顶点的度 7

1.3.2 图的同构 11

1.4 图的运算 13

1.4.1 并与和 13

1.4.2 笛卡儿积 14

1.4.3 超立方体 14

1.4.4 网格 15

1.4.5 边收缩 15

1.4.6 线图 16

1.5 路和连通 16

1.5.1 路和回路的定义 16

1.5.2 连通性 18

1.6 有向图 19

1.6.1 有向图的概念 20

1.6.2 有向图的度 21

1.6.3 有向网络 22

1.6.4 有向图的连通性 22

1.7 图的矩阵表示 23

1.7.1 关联矩阵 23

1.7.2 邻接矩阵 24

1.7.3 距离矩阵 27

1.7.4 连通矩阵 27

1.7.5 特殊类型图的邻接矩阵 27

1.7.6 有向图的矩阵表示 29

1.8 习题 30

第2章 树 32

2.1 树的基本性质 32

2.1.1 树的概念 32

2.1.2 树的性质 32

2.1.3 树的度序列与同构 34

2.1.4 树的叶子数 35

2.1.5 有向树 36

2.2 生成树 37

2.2.1 生成树的概念 37

2.2.2 生成树的计数 40

2.3 最优生成树 41

2.3.1 Kruskal算法 42

2.3.2 Prim算法 44

2.3.3 破圈法 45

2.4 深度优先搜索与广度优先搜索 45

2.4.1 深度优先搜索 45

2.4.2 广度优先搜索 46

2.5 最优二元树与前缀码 47

2.5.1 最优二元树 47

2.5.2 前缀码 51

2.6 树的Prüfer编码 52

2.7 习题 54

第3章 距离与连通性 57

3.1 图的距离 57

3.1.1 离径、中心、半径与直径 57

3.1.2 树的中心 58

3.1.3 自补图与距离 59

3.2 图的连通性 61

3.2.1 点连通度、边连通度 61

3.2.2 点、边连通度的性质 63

3.2.3 块 64

3.3 连通图 65

3.3.1 k-连通图 65

3.3.2 2-连通图 66

3.3.3 Menger定理 67

3.4 最短路算法 68

3.4.1 从一个始点到一个终点的最短路 68

3.4.2 任意两点间的最短路 72

3.5 习题 76

第4章 图的遍历问题 79

4.1 欧拉图 79

4.1.1 欧拉图的相关定义 80

4.1.2 一笔画问题 80

4.1.3 k笔画问题 83

4.2 中国邮递员问题 84

4.3 哈密尔顿图 87

4.4 格雷码 94

4.5 旅行售货员问题 96

4.6 E-图与H-图的关系 98

4.7 习题 100

第5章 图的匹配与独立集 104

5.1 二分图 104

5.2 图的匹配 107

5.3 二分图的匹配 112

5.3.1 二分图的完全匹配 112

5.3.2 二分图最大匹配的生成算法 114

5.4 最优匹配 117

5.4.1 求最优匹配的Kuhn-Munkres算法 118

5.4.2 求最小基数最优匹配的算法 120

5.5 稳定匹配 121

5.6 独立集和覆盖 124

5.7 Ramsey数 128

5.7.1 Ramsey定理 128

5.7.2 一般化的Ramsey数 130

5.8 习题 132

第6章 图的染色 135

6.1 顶点染色 135

6.1.1 色数 135

6.1.2 色数的一个算法 137

6.2 边染色 138

6.2.1 边色数的概念 138

6.2.2 Vizing定理 138

6.3 色多项式 141

6.4 图染色的应用 144

6.4.1 点染色的实际应用 144

6.4.2 边染色的实际应用 146

6.5 习题 149

第7章 平面图 151

7.1 平面图的概念及Euler公式 151

7.1.1 平面图的概念 151

7.1.2 Euler公式 153

7.2 一些特殊平面图及平面图的对偶图 154

7.2.1 一些特殊平面图 154

7.2.2 对偶图 158

7.3 Kuratowski定理 160

7.4 平面性算法 164

7.5 五色定理和四色猜想 168

7.6 习题 170

第8章 网络流 172

8.1 流与割 172

8.2 最大流最小割定理 175

8.3 最大流问题的算法 177

8.3.1 最大流问题的标号算法（2F算法） 177

8.3.2 最大流问题的最短增广路算法 179

8.4 Menger定理 184

8.5 最小费用流问题 186

8.6 最小费用流问题的算法 188

8.6.1 负回路算法 188

8.6.2 最小费用路算法 191

8.7 习题 195

第9章 图参数A（H）值 198

9.1 图参数A（H） 198

9.1.1 图参数A（H）的概念 198

9.1.2 2-图 199

9.1.3 2-图母图的结构 199

9.1.4 3-图的存在性 200

9.1.5 3-图的推广 202

9.2 树的A（T）值 204

9.2.1 关于树的A（T）值的结论 204

9.2.2 由树构造的A(H)=3图 205

9.2.3 方法证明 205

9.3 顶点数不超过7的图按参数A（H）的分类 207

9.3.1 顶点数不超过7的3-图 208

9.3.2 顶点数不超过7的4-图 211

9.3.3 ｜V（H）｜≤7的图按A（H）值的分类 211

9.4 习题 212

附录 213

附录A 部分习题参考答案 213

第1章习题答案 213

第2章习题答案 217

第3章习题答案 223

第4章习题答案 228

第5章习题答案 231

第6章习题答案 234

第7章习题答案 235

第8章习题答案 237

第9章习题答案 238

附录B 本书符号列表 240

参考文献 242