图论简明教程2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

图论简明教程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.110

1.2 数学归纳法12

1.2.1 数学归纳法14

1.2.2 第二数学归纳法19

习题1.220

1.3 排列组合21

1.3.1 排列21

1.3.2 组合23

习题1.326

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

1.4.1 递归式32

1.4.2 Pascal三角形行性质33

1.4.3 几个组合恒等式35

习题1.439

本章难题与工程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.149

2.2 子图与图的分类50

2.2.1 基本概念50

2.2.2 子图51

2.2.3 一些重要类型的图53

习题2.254

2.3 图的同构56

2.3.1 度序列58

习题2.361

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.470

参考文献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.177

3.2 最小生成树78

3.2.1 生成树78

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

3.2.3 最小代价生成树80

习题3.284

3.3 二分图85

习题3.388

3.4 匹配与工作分配问题89

3.4.1 二分图中的匹配89

3.4.2 最大匹配90

3.4.3 二分图中的完全匹配92

3.4.4 相异代表系94

3.4.5 更一般的匹配94

习题3.495

推荐读物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.1104

4.2 图的连通性106

4.2.1 割点、桥与连通性106

4.2.2 块108

4.2.3 Menger定理109

习题4.2111

4.3 应用112

4.3.1 F-图112

4.3.3 简单的概率计算114

4.3.2 网络可靠性114

习题4.3115

参考文献116

推荐读物116

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

5.1 欧拉图117

5.1.1 多重图117

5.1.2 哥尼斯堡七桥问题118

习题5.1121

5.2 哈密顿图的性质123

5.2.1 哈密顿图123

5.2.2 哈密顿游戏124

5.2.3 哈密顿图的充分条件125

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

5.2.5 网格与哈密顿图127

习题5.2128

5.2.6 超立方体128

5.3 应用130

5.3.1 中国邮递员问题130

5.3.2 旅行售货员问题131

习题5.3132

参考文献134

推荐读物134

第6章 图着色135

6.1 结点着色与独立集135

6.1.1 色数135

6.1.2 色数与独立性137

6.1.3 可惟一K着色图138

习题6.1140

6.2 边着色141

6.2.1 边色数141

6.2.2 Kn中的单色三角形144

习题6.2147

6.3 图着色的应用148

习题6.3153

参考文献154

推荐读物154

第7章 矩阵155

7.1 矩阵的基本概念155

7.1.1 矩阵运算156

7.1.2 矩阵的乘法158

习题7.1161

7.2 邻接矩阵162

7.2.1 一个简单的实例162

7.2.2 图的邻接矩阵163

7.2.3 关联矩阵164

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

7.2.5 子阵和矩阵的块166

习题7.2168

7.3 距离矩阵169

7.3.1 一个简单的实例169

7.3.2 由A推出D170

7.3.3 距离矩阵的图化171

习题7.3172

参考文献173

推荐读物174

第8章 图算法175

8.1 图搜索175

8.1.1 广度优先搜索175

8.1.2 深度优先搜索178

习题8.1180

8.2 图着色算法181

8.2.1 顺序着色181

8.2.2 最大色度着色182

习题8.2184

Prüfer编码185

8.3 树编码185

树的二进制编址187

习题8.3190

参考文献190

推荐读物191

第9章 可平面图192

9.1 可平面性192

9.1.1 欧拉公式195

9.1.2 可平面图中的边数195

9.1.3 可平面图的特性196

习题9.1197

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

9.2.1 图与地图199

9.2.2 嵌入201

9.3.1 对偶性203

习题9.2203

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

9.3.2 场地布局206

习题9.3208

参考文献210

推荐读物210

第10章 有向图与网络211

10.1 有向图211

10.1.1 强有向化213

10.1.2 有向无圈图及偏序214

10.1.3 锦标赛216

习题10.1217

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.2228

10.3 关键路径法230

10.3.1 统筹图230

10.3.2 关键路径法231

习题10.3233

参考文献236

推荐读物237

第11章 专题讨论238

11.1 RAMSEY理论238

11.1.1 Ramsey定理238

11.1.2 一般化ramsey数240

习题11.1243

11.2.1 支配的概念244

11.2 图支配244

11.2.2 覆盖、支配和独立集247

习题11.2248

参考文献249

推荐读物249

附录A 部分习题答案250

第1章250

习题1.1250

习题1.2251

习题1.3252

习题1.4252

第2章253

习题2.1253

习题2.2254

习题2.3255

习题2.4256

习题3.1257

第3章257

习题3.3259

习题3.2259

习题3.4260

第4章261

习题4.1261

习题4.2263

习题4.2263

第5章263

习题5.1263

习题5.2264

习题5.3265

第6章266

习题6.1266

习题6.2267

习题6.3268

习题7.1269

第7章269

习题7.2270

习题7.3271

第8章271

习题8.1271

习题8.2272

习题8.3273

第9章275

习题9.1275

习题9.2277

习题9.3278

第10章280

习题10.1280

习题10.2283

附录B 本书符号列表286