图论及其应用 (2010 年度畅销榜NO.14292 )

本书系统介绍了图论的基本知识，如树、连通性、遍历问题、匹配、顶点着色、边着色、平面图和网络等。作为正文的补充，书中收集了大量经典的习题，并在书后附有提示及解答，以便自学。与一般图论书不同的是，本书指明了许多应用中常见的图论问题是NP—困难问题，便于读者在科研工作中及时注意这种问题。本书力求立论严谨、简明易懂，只要是有一定数学基础的高中毕业生都可看懂。本书特别强调推理(而且还是在离散对象上的推理)的重要性，因为这是培养独立科研能力的必由之路。
本书可作为大学信息类及计算机类硕士研究生及高年级本科生的图论教材或参考书，也可作为其他相关专业科技工作者及图论爱好者的学习参考书。

第1章图的基本概念
1.1图的概念
1.2同构
1.3图的矩阵和顶点的度
1.4子图
1.5路和连通性
1.6圈
1.7最短路问题
第2章树
2.1树和割边
2.2边割和键
2.3割点
2.4连线问题
2.5生成树的计数及Cayley公式
第3章连通度
3.1连通度
3.2块
3.3Menger定理
3.4可靠通信网的建设问题
3.5边的共圈性及共闭迹性
第4章谝历问题
4.1Euler环游
4.2最优环游
4.3Hamilton圈
4.4旅行售货员问题
4.5Hamilton问题进阶
第5章匹配
5.1匹配
5.2独立集、团、覆盖和匹配间的关系
5.3偶图的匹配和覆盖
5.4完美匹配
5.5人员分派问题
5.6最优分派问题
5.7稳定匹配
第6章着色问题
6.1边着色
6.2排课表问题
6.3顶点着色和色数
6.4Brooks定理
6.5围长和色数
第7章平面图
7.1平图和平面图
7.2对偶图
7.3Kuratowski定理
7.4五色定理和四色猜想
7.5平面性算法
第8章有向图
8.1有向图
8.2竞赛图
8.3有向Hamilton圈
第9章网络
9.1流
9.2最大流最小割定理
9.3Menger定理进阶
9.4可行流
第10章NP—完全问题
10.1引言
10.2优化问题的三种提法
10.3P类和NP类
10.4多项式变换及NP—完全性
10.5Cook定理
10.6六个基本NPC问题
习题提示
习题解答
参考文献

本书是作者在给北京邮电大学研究生和本科生讲授了二十多年“图论及其应用”课程的基础上，将教学资料及体会整理编写而成的。通过这些年的教学，除了因许多图论算法已包含在数据结构等教科书中，以及教学时间不足等原因外，笔者越来越感到应该把侧重点放在训练学生掌握图论基本证明方法上。如果一个学生学完这门课后，仍然不能自己判定自己做的作业是对或错，那么可以说他没有学好这门课。掌握了基本证明方法也就有了这方面的自学能力，这将使学生在科研工作中，面对图论(网络)的新旧结论以及专业知识纵横交错的复杂对象，会感到更自主、更自在。为此，在定理证明中，笔者往往不满足于一个证明，但凡有来自名家的经典证明，书中一般都会收录其中。因此，第一个证明总是“正统的”，其他证明只好请读者“自取”。书中的附录及打*号的章节也属“自取”部分。甩掉这些内容后，60学时的教学并不轻松，其根源是掌握基本证明方法要有不少揣摩和适应的功夫。 此外，笔者对许多NP—完全或NP—困难的图论问题，在相关的章节中都及时加以指出，以便在设计算法时明确方向，这是本书的另一重要特色。 习题是学好图论的必由之路，不但要多做，而且要做好。凡是序号用黑体字标出的习题，都应尽量做。本书除了有题解外，对打*号的习题还有提示。题解主要是为自学的读者提供参考。大多数习题都是较容易的，有些只是对正文的一个补充，因此一般读者应尽量不要看题解，自己做往往比看题解更省时省力，何况看题解的效果并不好。此外，笔者还把一部分内容转移到了习题中。 虽然笔者尽量完善本书，但由于时间仓促，疏漏之处仍在所难免，敬请读者不吝施教，不胜感谢。 本书的出版得到了北京邮电大学以郭军教授为首的信息工程学院院领导的大力支持，以及胡正名、阮传概、陆传赉诸教授和罗群、王维嘉、卓新建等同事的关心和帮助，特此一并表示感谢。科学出版社匡敏女士为本书的出版做了不少工作，在此一并致谢。