图论及其应用

《图论及其应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、类硕士研究生及高年级本科生的图论教材或参考书，也可作为其他相关专业科技工作者及图论爱好者的学习参考书。图书在版编目（ＣＩＰ）数据图论及其应用／孙惠泉编著．—北京：科学出版社，２００４　（信息与通信工程研究生系列教材）ＩＳＢＮ７０３０１３８６６Ｘ　Ⅰ．图…　Ⅱ．孙…　Ⅲ．图论研究生教材　Ⅳ．Ｏ１５７．５中国版本图书馆ＣＩＰ数据核字（２００４）第０６８５８０号责任编辑：匡敏姚庆爽／责任校对：宋玲玲责任印制：张克忠／封面设计：陈敬出版北京东黄城根北街１６号邮政编码：１００７１７ｈｔｔｐ：／／ｗｗｗ．ｓｃｉｅｎｃｅｐ．ｃｏｍ印

3、刷科学出版社发行各地新华书店经销２００４年９月第一版开本：Ｂ５（７２０×１０００）２００６年８月第三次印刷印张：１７１／４印数：４５０１—６０００　　　　字数：３４００００定价：２７．００元（如有印装质量问题，我社负责调换枙环伟枛）前言本书是作者在给北京邮电大学研究生和本科生讲授了二十多年“图论及其应用”课程的基础上，将教学资料及体会整理编写而成的。通过这些年的教学，除了因许多图论算法已包含在数据结构等教科书中，以及教学时间不足等原因外，笔者越来越感到应该把侧重点放在训练学生掌握图论基本证明方法上。如果一个学生学完这门课后，仍

4、然不能自己判定自己做的作业是对或错，那么可以说他没有学好这····门课。掌握了基本证明方法也就有了这方面的自学能力，这将使学生在科研工作中，面对图论（网络）的新旧结论以及专业知识纵横交错的复杂对象，会感到更自主、更自在。为此，在定理证明中，笔者往往不满足于一个证明，但凡有来自名家的经典证明，书中一般都会收录其中。因此，第一个证明总是“正统的”，其他证明只好请读者“自取”。书中的附录及打号的章节也属“自取”部分。甩掉这些内容后，６０学时的教学并不轻松，其根源是掌握基本证明方法要有不少揣摩和适应的功夫。此外，笔者对许多ＮＰ完全或

5、ＮＰ困难的图论问题，在相关的章节中都及时加以指出，以便在设计算法时明确方向，这是本书的另一重要特色。习题是学好图论的必由之路，不但要多做，而且要做好。凡是序号用黑体字标出的习题，都应尽量做。本书除了有题解外，对打号的习题还有提示。题解主要是为自学的读者提供参考。大多数习题都是较容易的，有些只是对正文的一个补充，因此一般读者应尽量不要看题解，自己做往往比看题解更省时省力，何况看题解的效果并不好。此外，笔者还把一部分内容转移到了习题中。虽然笔者尽量完善本书，但由于时间仓促，疏漏之处仍在所难免，敬请读者不吝施教，不胜感谢。本书的出

6、版得到了北京邮电大学以郭军教授为首的信息工程学院院领导的大力支持，以及胡正名、阮传概、陆传赉诸教授和罗群、王维嘉、卓新建等同事的关心和帮助，特此一并表示感谢。科学出版社匡敏女士为本书的出版做了不少工作，在此一并致谢。孙惠泉２００４年６月１８日于北京·ｉ·目录前言第１章图的基本概念………………………………………………………………１　　１．１　图的概念……………………………………………………………１　　１．２　同构…………………………………………………………………５　　１．３　图的矩阵和顶点的度………………………………………………９

7、　　１．４　子图…………………………………………………………………１１　　１．５　路和连通性…………………………………………………………１４　　１．６　圈……………………………………………………………………１８　　１．７　最短路问题…………………………………………………………１９第２章树…………………………………………………………………………２３　　２．１　树和割边……………………………………………………………２３　　２．２　边割和键……………………………………………………………２８　　２．３　割点………………………………………

8、…………………………３４　　２．４　连线问题……………………………………………………………３６　　２．５生成树的计数及Ｃａｙｌｅｙ公式……………………………………３９第３章连通度……………………………………………………………………４２　　３．１　连通度…………