图论导引 第2版PDF电子书下载

第1章 基本概念 1

1.1 什么是图 1

1.1.1 定义 1

1.1.2 图模型 2

1.1.3 矩阵与同构 4

1.1.4 分解和特殊图 7

1.1.5 习题 9

1.2 路径、环和迹 13

1.2.1 图的连通 13

1.2.2 二分图 16

1.2.3 欧拉回路 18

1.2.4 习题 21

1.3 顶点度和计数 24

1.3.1 计数和双射 24

1.3.2 极值问题 27

1.3.3 图解序列 31

1.3.4 习题 33

1.4 有向图 38

1.4.1 定义和例子 38

1.4.2 顶点度 41

1.4.3 欧拉有向图 42

1.4.4 定向图和竞赛图 44

1.4.5 习题 45

第2章 树和距离 48

2.1 基本性质 48

2.1.1 树的性质 48

2.1.2 树和图中的距离 50

2.1.3 不相交生成树（选学） 53

2.1.4 习题 54

2.2 生成树和枚举 58

2.2.1 树的枚举 58

2.2.2 图的生成树 60

2.2.3 分解和优美标记 63

2.2.4 分叉与欧拉有向图（选学） 64

2.2.5 习题 66

2.3 优化和树 69

2.3.1 最小生成树 69

2.3.2 最短路径 71

2.3.3 计算机科学中的树（选学） 73

2.3.4 习题 75

第3章 匹配和因子 78

3.1 匹配与覆盖 78

3.1.1 最大匹配 79

3.1.2 Hall匹配条件 80

3.1.3 最小－最大定理 81

3.1.4 独立集与覆盖 82

3.1.5 支配集（选学） 84

3.1.6 习题 86

3.2 算法及应用 90

3.2.1 最大二分匹配 90

3.2.2 加权二分匹配 91

3.2.3 稳定匹配（选学） 95

3.2.4 快速二分匹配（选学） 97

3.2.5 习题 98

3.3 一般图中的匹配 99

3.3.1 Tutte 1-因子定理 100

3.3.2 图的f-因子（选学） 102

3.3.3 Edmonds开花算法（选学） 103

3.3.4 习题 106

第4章 连通度和路径 109

4.1 割与连通度 109

4.1.1 连通度 109

4.1.2 边连通度通常 111

4.1.3 块 113

4.2 k-通图 117

4.2.1 2-连通图 117

4.2.2 有向图的连通度 119

4.2.3 k-通图与k-边连通图 120

4.2.4 Menger定理的应用 123

4.2.5 习题 125

4.3 网络流问题 128

4.3.1 最大网络流 128

4.3.2 整数流 132

4.3.3 供应与需求（选学） 134

4.3.4 习题 137

第5章 图的着色 140

5.1 顶点着色和上界 140

5.1.1 定义和实例 140

5.1.2 上界 142

5.1.3 Brooks定理 145

5.1.4 习题 146

5.2 k-色图的构造 150

5.2.1 大色数图 150

5.2.2 极值问题与Turán定理 151

5.2.3 颜色－临界图 153

5.2.4 强制细分 155

5.2.5 习题 157

5.3 计数方面的问题 161

5.3.1 真着色的计数 161

5.3.2 弦图 164

5.3.3 完美图点滴 166

5.3.4 无环定向的计数（选学） 167

5.3.5 习题 168

第6章 可平面图 171

6.1 嵌入与欧拉公式 171

6.1.1 平面作图 171

6.1.2 对偶图 173

6.1.3 欧拉（Euler）公式 176

6.1.4 习题 178

6.2 可平面图的特征 179

6.2.1 Kuratowski定理的预备知识 180

6.2.2 凸嵌入 181

6.2.3 可平面性的测试（选学） 184

6.2.4 习题 186

6.3 可平面性的参数 188

6.3.1 可平面图的着色 188

6.3.2 交叉数 191

6.3.3 具有更高亏格的表面（选学） 195

6.3.4 习题 198

第7章 边和环 201

7.1 线图与边着色 201

7.1.1 边着色 201

7.1.2 线图的性质（选学） 206

7.1.3 习题 208

7.2 哈密顿环 210

7.2.1 必要条件 211

7.2.2 充分条件 212

7.2.3 有向图中的环（选学） 216

7.2.4 习题 216

7.3 可平面性、着色与环 220

7.3.1 Tait定理 220

7.3.2 Grinberg定理 222

7.3.3 鲨鱼图（选学） 223

7.3.4 流与环覆盖（选学） 225

7.3.5 习题 230

第8章 其他主题 234

8.1 完美图 234

8.1.1 完全图定理 235

8.1.2 弦图的再研究 237

8.1.3 其他完美图类 240

8.1.4 非完美图 245

8.1.5 强完美图猜想 249

8.1.6 习题 252

8.2 拟阵 255

8.2.1 遗传系统及示例 256

8.2.2 拟阵的性质 259

8.2.3 生成函数 262

8.2.4 拟阵的对偶 264

8.2.5 拟阵的子式与可平面对偶 266

8.2.6 拟阵的交 268

8.2.7 拟阵的并 271

8.2.8 习题 273

8.3 拉姆齐理论 278

8.3.1 鸽巢原理的再研究 278

8.3.2 拉姆齐（Ramsey）定理 279

8.3.3 拉姆齐数 282

8.3.4 图的拉姆齐理论 284

8.3.5 Sperner引理和带宽 286

8.3.6 习题 289

8.4 其他极值问题 292

8.4.1 图的编码 293

8.4.2 分叉和流言 299

8.4.3 序列着色和可选择性 302

8.4.4 由路径和环构成的划分 305

8.4.5 周长 307

8.4.6 习题 312

8.5 随机图 314

8.5.1 存在性和数学期望 315

8.5.2 几乎所有图均具有的性质 318

8.5.3 阈值函数 320

8.5.4 图的演变和图的参数 323

8.5.5 连通度、团和着色 326

8.5.6 鞅 328

8.5.7 习题 333

8.6 图的特征值 336

8.6.1 特征多项式 337

8.6.2 线性代数和实对称阵 339

8.6.3 特征值和图参数 341

8.6.4 正则图的特征值 343

8.6.5 特征值与扩张图 345

8.6.6 强正则图 346

8.6.7 习题 349

附录A数学基础 352

附录B最优化和复杂度 369

附录C部分习题提示 379

附录D术语表 385

附录E补充阅读 404

附录F参考文献 408

附录G术语对照表 440