第1章 基本概念1
1.1 什么是图1
定义1
图模型3
矩阵和同构6
分解和特殊图11
习题14
1.2 路径、环和迹19
图的连通性20
二部图24
欧拉回路26
习题31
1.3 顶点度和计数34
计数和双射35
极值问题38
图序列44
习题47
1.4 有向图53
定义和例子53
顶点度58
欧拉有向图60
定向和竞赛图61
习题63
第2章 树和距离67
2.1 基本性质67
树的性质68
树和图中的距离70
不相交生成树（选学）73
习题75
2.2 生成树和枚举81
树的枚举81
图的生成树83
分解和优美标记87
分叉和欧拉有向图（选学）89
习题92
2.3 最优化和树95
最小生成树95
最短路径97
计算机科学中的树（选学）100
习题103
第3章 匹配和因子107
3.1 匹配和覆盖107
最大匹配108
Hall匹配条件110
最小–最大定理112
独立集和覆盖113
支配集（选学）116
习题118
3.2 算法和应用123
最大二部匹配123
加权二部匹配125
稳定匹配（选学）130
快速二部匹配（选学）132
习题134
3.3 一般图中的匹配136
Tutte 1-因子定理136
图的f-因子（选学）140
Edmonds开花算法（选学）142
习题145
第4章 连通度和路径149
4.1 割和连通度149
连通度149
边–连通度152
块155
习题158
4.2 k–连通图161
2–连通图161
有向图的连通度164
k–连通图和k–边连通图166
Menger定理的应用170
习题172
4.3 网络流问题176
最大网络流176
整数流181
供应和需求（选学）184
习题188
第5章 图的着色191
5.1 顶点着色和上界191
定义和实例191
上界194
Brooks定理197
习题199
5.2 k–色图的结构204
大色数图205
极值问题和Turán定理207
颜色–临界图210
强制细分212
习题214
5.3 计数方面的问题219
真着色的计数219
弦图224
完美图点滴226
无环定向的计数（选学）228
习题229
第6章 可平面图233
6.1 嵌入和欧拉公式233
平面作图233
对偶图236
欧拉公式241
习题243
6.2 可平面图的特征246
Kuratowski定理的预备知识247
凸嵌入248
可平面性测试（选学）252
习题255
6.3 可平面性的参数257
可平面图的着色257
交叉数261
具有更高亏格的表面（选学）266
习题269
第7章 边和环273
7.1 线图和边着色273
边着色274
线图的特征（选学）279
习题282
7.2 哈密顿环286
必要条件287
充分条件288
有向图中的环（选学）293
习题294
7.3 可平面性、着色和环299
Tait定理300
Grinberg定理302
鲨鱼图（选学）304
流和环覆盖（选学）307
习题314
第8章 其他主题（选学）319
8.1 完美图319
完美图定理320
弦图的再研究323
其他类型的完美图328
非完美图334
强完美图猜想340
习题344
8.2 拟阵349
遗传系统和示例349
拟阵的性质354
生成函数358
拟阵的对偶性360
拟阵的子式和可平面图363
拟阵的交366
拟阵的并369
习题372
8.3 Ramsey理论378
鸽巢原理的再研究378
Ramsey定理380
Ramsey数383
关于图的Ramsey理论386
Sperner引理和带宽388
习题392
8.4 其他极值问题396
图的编码397
分叉和流言404
序列着色和可选择性408
使用路径和环的划分413
周长416
习题422
8.5 随机图425
存在性和期望值426
几乎所有图均具有的性质430
阈值函数432
演变和图参数436
连通度、团和着色439
鞅442
习题448
8.6 图的特征值452
特征多项式453
实对称矩阵的线性代数456
特征值和图参数458
正则图的特征值460
特征值和扩张图463
强正则图464
习题467
附录A 数学基础471
附录B 最优化和复杂度493
附录C 部分习题的提示507
附录D 术语表515
附录E 补充阅读材料533
附录F 参考文献567
作者索引569
术语索引575
Contents
Preface xi
Chapter 1 Fundamental Concepts
1.1 What Is a Graph?
The Definition, 1
Graphs as Models, 3
Matrices and Isomorphism, 6
Decomposition and Specia] Graphs, 11
Exercises, 14
1.2 Paths, Cycles, and Trails 19
Connection in Graphs, 20
Bipartite Graphs, 24
Eulerian Circuits, 26
Exercises, 31
1.3 Vertex Degrees and Counting 34
Counting and Bijections, 35
Extremal Problems, 38
Graphic Sequences, 44
Exercises, 47
1.4 Directed Graphs 53
Definitions and Examples, 53
Vertex Degrees, 58
Eulerian Digraphs, 60
Orientations and Tournaments, 61
Exercises, 63
Chapter 2 Trees and Distance
2.1 Basic Properties
Properties of Trees, 68
Distance in Trees and Graphs, 70
Disjoint Spanning Trees (optional), 73
Exercises, 75
2.2 Spanning Trees and Enumeration
Enumeration of Trees, 81
Spanning Trees in Graphs, 83
D
鄂公网安备 42010302001612号 