图论导引 原书第2版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

图论导引 原书第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