图论简明教程PDF电子书下载

第1章 基础知识 1

1.1 数学预备知识 1

1.1.1 取整运算 1

1.1.2 奇偶性 2

1.1.3 集合 3

1.1.4 子集 5

1.1.5 集合运算 6

1.1.6 笛卡尔积 8

习题1.1 10

1.2 数学归纳法 12

1.2.1 数学归纳法 14

1.2.2 第二数学归纳法 19

习题1.2 20

1.3 排列组合 21

1.3.1 排列 21

1.3.2 组合 23

习题1.3 26

1.4 Pascal三角形与组合恒等式 30

1.4.1 递归式 32

1.4.2 Pascal三角形行性质 33

1.4.3 几个组合恒等式 35

习题1.4 39

本章难题与工程 40

参考文献 41

推荐读物 41

第2章 图的基本概念与应用 42

2.1 图论模型 42

2.1.1 图 42

2.1.2 数学模型 43

2.1.3 在化学领域的应用 44

2.1.4 商业应用：仓库／零售店问题 45

2.1.6 应用：冰淇淋车的路线图 46

2.1.5 应用：最短航线问题 46

2.1.7 应用：旅行售货员问题 47

2.1.8 应用：考试时间安排问题 48

2.1.9 应用：一个任务分配模型 48

习题2.1 49

2.2 子图与图的分类 50

2.2.1 基本概念 50

2.2.2 子图 51

2.2.3 一些重要类型的图 53

习题2.2 54

2.3 图的同构 56

2.3.1 度序列 58

习题2.3 61

2.4 图操作 63

2.4.1 并与和 63

2.4.2 边与结点的删除 64

2.4.3 补图 65

2.4.4 笛卡尔积 66

2.4.5 超立方体 67

2.4.6 网格 68

2.4.7 线图 69

2.4.8 边收缩 70

习题2.4 70

参考文献 71

推荐读物 71

第3章 树与二分图 72

3.1 树的性质 72

3.1.1 树的一些性质 72

3.1.2 树的度序列 73

3.1.3 非同构树 74

3.1.4 树的叶子数 75

3.1.5 饱和烃 76

习题3.1 77

3.2 最小生成树 78

3.2.1 生成树 78

3.2.2 生成树中的k-差结点 79

3.2.3 最小代价生成树 80

习题3.2 84

3.3 二分图 85

习题3.3 88

3.4 匹配与工作分配问题 89

3.4.1 二分图中的匹配 89

3.4.2 最大匹配 90

3.4.3 二分图中的完全匹配 92

3.4.4 相异代表系 94

3.4.5 更一般的匹配 94

习题3.4 95

推荐读物 97

参考文献 97

第4章 距离与连通性 98

4.1 图的距离 98

4.1.1 偏心距、中心、半径与直径 98

4.1.2 树与距离 101

4.1.3 树的中心 101

4.1.4 自补图与距离 102

4.1.5 树的重心 103

习题4.1 104

4.2 图的连通性 106

4.2.1 割点、桥与连通性 106

4.2.2 块 108

4.2.3 Menger定理 109

习题4.2 111

4.3 应用 112

4.3.1 F-图 112

4.3.3 简单的概率计算 114

4.3.2 网络可靠性 114

习题4.3 115

参考文献 116

推荐读物 116

第5章 欧拉图与哈密顿图 117

5.1 欧拉图 117

5.1.1 多重图 117

5.1.2 哥尼斯堡七桥问题 118

习题5.1 121

5.2 哈密顿图的性质 123

5.2.1 哈密顿图 123

5.2.2 哈密顿游戏 124

5.2.3 哈密顿图的充分条件 125

5.2.4 均匀连通图与哈密顿连通图 126

5.2.5 网格与哈密顿图 127

习题5.2 128

5.2.6 超立方体 128

5.3 应用 130

5.3.1 中国邮递员问题 130

5.3.2 旅行售货员问题 131

习题5.3 132

参考文献 134

推荐读物 134

第6章 图着色 135

6.1 结点着色与独立集 135

6.1.1 色数 135

6.1.2 色数与独立性 137

6.1.3 可惟一K着色图 138

习题6.1 140

6.2 边着色 141

6.2.1 边色数 141

6.2.2 Kn中的单色三角形 144

习题6.2 147

6.3 图着色的应用 148

习题6.3 153

参考文献 154

推荐读物 154

第7章 矩阵 155

7.1 矩阵的基本概念 155

7.1.1 矩阵运算 156

7.1.2 矩阵的乘法 158

习题7.1 161

7.2 邻接矩阵 162

7.2.1 一个简单的实例 162

7.2.2 图的邻接矩阵 163

7.2.3 关联矩阵 164

7.2.4 不同类型图的邻接矩阵 166

7.2.5 子阵和矩阵的块 166

习题7.2 168

7.3 距离矩阵 169

7.3.1 一个简单的实例 169

7.3.2 由A推出D 170

7.3.3 距离矩阵的图化 171

习题7.3 172

参考文献 173

推荐读物 174

第8章 图算法 175

8.1 图搜索 175

8.1.1 广度优先搜索 175

8.1.2 深度优先搜索 178

习题8.1 180

8.2 图着色算法 181

8.2.1 顺序着色 181

8.2.2 最大色度着色 182

习题8.2 184

Prüfer编码 185

8.3 树编码 185

树的二进制编址 187

习题8.3 190

参考文献 190

推荐读物 191

第9章 可平面图 192

9.1 可平面性 192

9.1.1 欧拉公式 195

9.1.2 可平面图中的边数 195

9.1.3 可平面图的特性 196

习题9.1 197

9.2 可平面图，图着色和镶嵌 199

9.2.1 图与地图 199

9.2.2 嵌入 201

9.3.1 对偶性 203

习题9.2 203

9.3 对偶图和可平面图的应用 203

9.3.2 场地布局 206

习题9.3 208

参考文献 210

推荐读物 210

第10章 有向图与网络 211

10.1 有向图 211

10.1.1 强有向化 213

10.1.2 有向无圈图及偏序 214

10.1.3 锦标赛 216

习题10.1 217

10.2 网络 219

10.2.1 网络中的距离 219

10.2.2 网络流 220

10.2.4 最大流最小割定理 223

10.2.3 极小割和最小割 223

10.2.5 求增流半路径 224

10.2.6 网络、匹配和连通性 228

习题10.2 228

10.3 关键路径法 230

10.3.1 统筹图 230

10.3.2 关键路径法 231

习题10.3 233

参考文献 236

推荐读物 237

第11章 专题讨论 238

11.1 RAMSEY理论 238

11.1.1 Ramsey定理 238

11.1.2 一般化ramsey数 240

习题11.1 243

11.2.1 支配的概念 244

11.2 图支配 244

11.2.2 覆盖、支配和独立集 247

习题11.2 248

参考文献 249

推荐读物 249

附录A 部分习题答案 250

第1章 250

习题1.1 250

习题1.2 251

习题1.3 252

习题1.4 252

第2章 253

习题2.1 253

习题2.2 254

习题2.3 255

习题2.4 256

习题3.1 257

第3章 257

习题3.3 259

习题3.2 259

习题3.4 260

第4章 261

习题4.1 261

习题4.2 263

习题4.2 263

第5章 263

习题5.1 263

习题5.2 264

习题5.3 265

第6章 266

习题6.1 266

习题6.2 267

习题6.3 268

习题7.1 269

第7章 269

习题7.2 270

习题7.3 271

第8章 271

习题8.1 271

习题8.2 272

习题8.3 273

第9章 275

习题9.1 275

习题9.2 277

习题9.3 278

第10章 280

习题10.1 280

习题10.2 283

附录B 本书符号列表 286