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

第1章 基本概念 1

1.1 什么是图 1

定义 1

图模型 2

矩阵和同构 4

分解和特殊图 7

习题 10

1.2 路径、环和迹 13

图的连通性 14

二部图 17

欧拉回路 19

习题 22

1.3 顶点度和计数 25

计数和双射 26

极值问题 28

图序列 32

习题 35

1.4 有向图 40

定义和例子 40

顶点度 44

欧拉有向图 45

定向和竞赛图 46

习题 47

第2章 树和距离 51

2.1 基本性质 51

树的性质 51

树和图中的距离 54

不相交生成树（选学） 56

习题 57

2.2 生成树和枚举 63

树的枚举 63

图的生成树 65

分解和优美标记 67

分叉和欧拉有向图（选学） 69

习题 71

2.3 最优化和树 74

最小生成树 74

最短路径 76

计算机科学中的树（选学） 78

习题 80

第3章 匹配和因子 84

3.1 匹配和覆盖 84

最大匹配 84

Hall匹配条件 86

最小－最大定理 87

独立集和覆盖 88

支配集（选学） 90

习题 92

3.2 算法和应用 96

最大二部匹配 96

加权二部匹配 98

稳定匹配（选学） 102

快速二部匹配（选学） 103

习题 105

3.3 一般图中的匹配 106

Tutte1-因子定理 107

图的f-因子（选学） 110

Edmonds开花算法（选学） 110

习题 113

第4章 连通度和路径 117

4.1 割和连通度 117

连通度 117

边－连通度 118

块 121

习题 123

2－连通图 126

4.2 k－连通图 126

有向图的连通度 129

k－连通图和k－边连通图 130

Menger定理的应用 133

习题 135

4.3 网络流问题 138

最大网络流 138

整数流 142

供应和需求（选学） 144

习题 147

定义和实例 151

5.1 顶点着色和上界 151

第5章 图的着色 151

上界 153

Brooks定理 156

习题 157

5.2 k－色图的结构 162

大色数图 163

极值问题和Turan定理 164

颜色－临界图 167

强制细分 169

习题 171

真着色的计数 175

5.3 计数方面的问题 175

弦图 179

完美图点滴 181

无环定向的计数（选学） 182

习题 183

第6章 可平面图 186

6.1 嵌入和欧拉公式 186

平面作图 186

对偶图 188

欧拉公式 191

习题 193

6.2 可平面图的特征 195

Kuratowski定理的预备知识 196

凸嵌入 197

可平面性测试（选学） 200

习题 202

6.3 可平面性的参数 204

可平面图的着色 204

交叉数 208

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

习题 214

边着色 218

第7章 边和环 218

7.1 线图和边着色 218

线图的特征（选学） 223

习题 225

7.2 哈密顿环 229

必要条件 229

充分条件 230

有向图中的环（选学） 234

习题 235

7.3 可平面性、着色和环 240

Tait定理 240

Grinberg定理 242

鲨鱼图（选学） 243

流和环覆盖（选学） 245

习题 251

第8章 其他主题（选学） 255

8.1 完美图 255

完美图定理 256

弦图的再研究 258

其他类型的完美图 261

非完美图 266

强完美图猜想 271

习题 274

8.2 拟阵 278

遗传系统和示例 278

拟阵的性质 282

生成函数 285

拟阵的对偶性 287

拟阵的子式和可平面图 288

拟阵的交 291

拟阵的并 293

习题 296

鸽巢原理的再研究 301

8.3 Ramsey理论 301

Ramsey定理 303

Ramsey数 306

关于图的Ramsey理论 308

Sperner引理和带宽 309

习题 312

8.4 其他极值问题 316

图的编码 317

分叉和流言 323

序列着色和可选择性 326

使用路径和环的划分 329

周长 332

习题 337

8.5 随机图 339

存在性和期望值 340

几乎所有图均具有的性质 343

阈值函数 345

演变和图参数 348

连通度、团和着色 350

鞅 353

习题 358

8.6 图的特征值 362

特征多项式 362

实对称矩阵的线性代数 365

特征值和图参数 367

正则图的特征值 368

特征值和扩张图 371

强正则图 372

习题 374

附录A 数学基础 378

附录B 最优化和复杂度 394

附录C 部分习题的提示 405

附录D 术语表 412

附录E 补充阅读材料 439

附录F 参考文献 443