图论
2009-8
科学出版社
王树禾
238
无
图论是离散数学的骨干分支，离散数学则是计算机科学技术与网络信息科学的理论基础。多年来，为了实现高速计算的目的，数学促进了计算机科学的形成与发展。例如图灵机的数学理论为计算机的诞生打下了基础；另一方面，随着计算机科学在社会发展中作用的日益提升，它又反过来促进数学的发展。例如1976年，伊利诺大学的Appel和Haken用计算机证明了四色猜想成立。我国著名数学家吴文俊、张景中等用计算机进行了几何定理的机器证明，发展出一套成熟的机器证明的新理论与新方法。离散数学，特别是图论，近年来如异军突起般蓬勃发展，实乃数学与计算机科学交互作用的范例。图论与计算机科学结盟解决了有关离散事物的结构与关系当中定性与定量的各种优化问题。在信息科学与网络技术迅猛发展的时代背景之下，接受图论教育与进行图论研究成了众多相关的青年科学家与工程师的强烈追求。图论自身的美好形象，诸如它的强有力的逻辑，漂亮的图形，高明的数学技巧等等，也对每个爱好科学的年轻人产生了挥之不去的诱惑，在高等学校的教学当中，图论课成了广大大学生和研究生争相选修的最受欢迎的热门课程之一。 学习图论，除了能使我们采用它的成果与方法之外，同样重要的是它能培养我们思考问题与解决问题的能力。图论中的问题，看似通俗简单，却往往含有非平凡的难度，每个学习研究图论的人在它面前必须全力以赴、严肃认真地思考问题，有时百思方得其解，有时则是百思仍不得其解的！
《图论(第2版)》系统阐述图论与算法图论的基本概念、理论、算法及其应用，建立图的重要矩阵与线性空间，论述计算复杂度理论中的NP完全性理论和著名的一些NPC问题等。《图论(第2版)》概念明确，立论严谨，语言流畅生动，注重算法分析及其有效性；内容全面深入，可读与可教性强，是一部理想的图论基础性著作。 《图论(第2版)》读者对象为高等院校数学、计算机科学、信息与网络等专业的大学生与研究生，以及科研工作者与图论爱好者。
第一章 图1.1 从哥尼斯堡七桥问题谈起1.2 图的基本概念1.3 轨道和圈*1.4 Brouwer不动点定理1.5 求最短轨长度的算法*1.6 图上博弈习题第二章 树2.1 树的定义与性质2.2 生成树的个数2.3 求生成树的算法2.4 求最优树的算法2.5 有序二元树2.6 n顶有序编码二元树的数目*2.7 最佳追捕问题习题第三章 平面图3.1 平面图及其平面嵌入3.2 平面图Euler公式3.3 极大平面图3.4 平面图的充要条件*3.5 平面嵌入的灌木生长算法习题第四章 匹配理论及其应用4.1 匹配与许配4.2 匹配定理4.3 匹配的应用4.4 图的因子分解习题第五章 着色理论5.1 图的边着色5.2 图的顶着色*5.3 四色猜想为真的机器证明5.4 颜色多项式5.5 独立集5.6 Ramsey数习题第六章 Euler图和Hamilton图6.1 Euler图6.2 中国邮递员问题6.3 Hamilton图习题第七章 有向图7.1 弱连通、单连通与强连通7.2 循环赛图、有向轨和王7.3 有向Hamilton图习题第八章 最大流的算法8.1 2F算法*8.2 Dinic分层算法8.3 有上下界网络最大流的算法8.4 有供需要求的网络流算法8.5 关于PERT的两个问题习题第九章连通度9.1 顶连通度9.2 边连通度*9.3 一种边数最少的κ连通图习题第十章 图的线性空间与矩阵10.1 图的线性空间10.2 图矩阵10.3 开关网络习题第十一章 图论中的NPC问题11.1 问题、实例和算法的时间复杂度11.2 Turing机和NPC11.3 满足问题和Cook定理11.4 图论中的一些NPC问题习题习题解答与提示参考文献
当时数学界并未对欧拉解决七桥问题的意义有足够的认识，甚至仅仅视其为一个数学游戏而已，图论诞生后并未及时获得足够的发展。1936年，匈牙利数学家柯尼希（Konig）出版《有限图与无限图理论》，这是图论的第一部专著，它总结了图论200年的成果，是图论发展的第一座里程碑。此后，图论进入发展与突破的快车道，又经过半个多世纪的发展，现已成长为数学科学的一个独立的重要学科。它的分支很多，例如图论、算法图论、极值图论、网络图论、代数图论、随机图论、模糊图论、超图论等等。由于现代科技尤其是大型计算机的迅猛发展，使图论大有用武之地，无论是数学、物理、化学、天文、地理、生物等基础科学，还是信息、交通、战争、经济乃至社会科学的众多问题，都可以应用图论方法予以解决。图论又是计算机科学最重要的基础之一。 1976年世界上发生了不少大事，其中有一件是美国数学家Appel和Haken在Koch的协作之下，用计算机证明了图论难题——四色猜想（4CC）： 任何地图，用四种颜色，可以把每国领土染上一种颜色，使邻国异色。 4CC的提法和内容十分简朴，以至于可以向随便一个人（哪怕他不识字）在几分钟之内讲清楚。1852年英国的一个大学生格思里（Guthrie）向他的老师德·摩根（DeMorgan）请教这个问题。德·摩根是当时十分有名的数学家，他不能判断这个猜想是否成立，于是很快在数学界流传开来。
无