本书系统介绍了图与网络流理论的基本概念、基本算法、基本定理以及某些应用. 第1~7 章主要介绍无向图的基本概念和相关内容, 如树图的性质、图的连通性、图的点无关集和覆盖集、欧拉问题与哈密顿问题、平面图以及图的染色问题等. 第8~12 章是有向图以及网络流理论的相关内容，图的覆盖、分解和装填问题以及图空间等. 本书论证严谨, 深入浅出, 每章末附有典型习题及大量相关参考文献, 有助于读者深入理解本书内容. 对于学习和研究图论的读者来说, 本书是一本比较理想的入门书.
样章试读
目录
- 第二版前言
常用符号表
绪论
第1 章图的基本概念5
1.1图与子图5
1.2链,圈和连通分图10
1.3—些特殊图类12
1.4图的关系和运算14
1.5反圈17
1.6图的若干不变量18
1.7Turan 19
1.8几点说明21
习题 22
参考文献23
第 2 章 树25
2.1树的基本性质25
2.2图的规树28
2.3树的基本变换32
2.4最小支撑树34
2.5Cayley 定理37
习题40
参考文献41
第3 章图的连通性43
3.1图的连通度43
3.2截点,截边和块49
3.3Menger 型定理51
3.4k-连通图的性质56
3.5极小k-连通图60
3.6最短链问题69
习题70
参考文献72
第4章图的点无关集和覆盖集74
4.1边无关集74
4.2寻求二部图最大边无关集的反圈法75
4.3Konig 定理77
4.4Hall 定理80
4.5一般图的最大边无关集算法82
4.6强边无关集88
4.7完美边无关集91
4.8稳？定边无关集95
4.9点无关集和边覆盖集98
4.10 Ramsey 数106
习题 110
参考文献112
第5章欧拉问题和哈密顿问题114
5.1欧拉问题114
5.2中国邮递员问题116
5.3引人入胜的哈密顿问题118
5.4哈密顿图的必要条件和充分条件121
5.5图的泛圈性152
5.6Thomason引理和Smith定理的推广157
5.7特殊图类的哈密顿问题155
习题166
参考文献167
第6章平面图173
6.1图的可平面性173
6.2Euler 公式177
6.3Kuratowski 定理179
6.4与图的平面性问题有关的不变量183
习题185
参考文献186
第7章图的染色问题188
7.1图的边染色188
7.2唯一k-边可染图192
7.3图的点染色193
7.4平面图的染色200
7.5图的列表染色206
7.6图的色多项式208
7.7完美图猜想212
习题219
参考文献220
第 8 章有向图224
8.1有向图的基本概念224
8.2有向图的核？半核及其应用230
8.3树形图235
8.4Gallai-Roy-Vitaver 定理243
8.5有向图的哈密顿回路和欧拉回路246
8.6有向图的最短路问题250
8.7与有向图有关的未解决问题251
习题253
参考文献254
第9章网络最大流问题257
9.1基本概念和基本定理257
9.2最规霞262
9.3相容性定理268
9.4循环流定理274
9.5流量矩阵277
习题280
参考文献282
第10章最小费用流问题284
10.1基本定理284
10.2最小费用最大流的算法288
10.3最小费用循环流的算法293
习题299
参考文献300
第11章图的覆盖？分解和装填301
11.1图的子图分解302
11.2图的完美双链覆盖307
11.3双圈覆盖猜想309
11.4有向图路覆盖的Gallai-Milgram定理318
11.5树的装填问题322
11.6有向图中的最大最小定理330
习题339
参考文献340
第12章图的空间与矩阵343
12.1图的向量空间343
12.2图的矩阵346
12.3有向图的矩阵349
12.4矩阵-树定理352
习题355
参考文献355
索引356
《运筹与管理科学丛书》已出版书目365
京公网安备 11010102004214号