图论 王树禾

王树禾著。本书系统阐述图论与算法图论的基本概念、理论、算法及其应用，建立图的重要矩阵与线性空间，论述计算复杂度理论中的NP完全性理论和著名的一些NPC问题。本书概念明确、立论严谨，语言流畅生动，注重算法分析及其有效性，内容全面深入，可读与可教性强，是一部理想的图论基础性著作。目录：一、图；二、树；三、平面图；四、匹配理论及其应用；五、着色理论；六、Eiler图和Hamilton图；七、有向图；八、最大流的算法；九、连通度；十、图的线性空间与矩阵；十一、图论中的NPC问题。内容筒介本书系统阐述图论与算法图论的基本概念理论、算法及其应用,建立图的重要矩阵与线性空间论述计算复杂度理论中的NP完全性理论和著名的一些NPC问题等本书概念明确,立论严语言流畅生动注重算法分析及其有效性;内容全面深入,可读与可教性强是一部理想的图论基础性著作本书读者对象为高等院校数学计算机科学信息与网络等专业的大学生与研究生,以及科研工作者与图论爱好者图书在版编目(CP数据图论/王树禾编著.2版.一北京:科学出版社,2009(普通高等教育“十一五”国家级规划教材ISBN978703024595-3I.图…Ⅱ.王…Ⅲ.图论高等学校教材Ⅳ.O157.5中国版本图书馆CIP数据核字(2009)第076154号责任编辑:李晓鹏/责任校对:宣悬责饪印制:张克忠/封面设计:陈敬鼻学实出版化东戴城根北街]6号邮政纳码17http://www.sciencep.com霸砾刷广印刷科学出版社发行各地新华书店经销204年1月第一版开本:B5(720×1000)2009年8月第二版印张:153/42009年8月第七次印刷字数:29300印数:15501-19000定价:28.0元〔如有印装质量问题我社负责调换环伟))第二版前言从2004年起,本书共印刷6次,发行15500册,作为专业基础课教材,能有如此之众的读者群令人欣慰。2008年,教育部将本书列入普通高等教育“十一五”国家级规划教材。我们按教育部的标准和各地师生的反馈意见,对第一版进行全面修订,编写了第二版以适应各校图论教学的新要求。第二版对第一版的结构与内容大体保留,在论证与计算的细节及表达方式上进行了必要的修正与精炼。为强化图理论与图算法的实际应用第二版添加了PERT( program evaluation and review technique问题的图论解法与开关网络等内容。事实上,PERT是现代运筹学例如统筹法)的一种关键技术,利用图论模型与算法解决它极为便捷实用;开关网络则是大型计算机设计与通信系统中的重要课题,我们用图矩阵计算给出最优开关网络设计的有效算法,显示了代数图论对信息与网络技术的作用王树禾2009年3月于中国科学技术大学数学系第一版前言图论是离散数学的骨干分支,离散数学则是计算机科学技术与网络信息科学的理论基础多年来,为了实现高速计算的目的数学促进了计算机科学的形成与发展例如图灵机的数学理论为计算机的诞生打下了基础;另一方面随着计算机科学在社会发展中作用的日益提升,它又反过来促进数学的发展例如1976年,伊利诺大学的Appe和 Haken用计算机证明了四色猜想成立我国著名数学家吴文俊、张景中等用计算机进行了几何定理的机器证明,发展出一套成熟的机器证明的新理论与新方法.离散数学特别是图论,近年来如异军突起般蓬勃发展,实乃数学与计算机科学交互作用的范例图论与计算机科学结盟解决了有关离散事物的结构与关系当中定性与定量的各种优化问题.在信息科学与网络技术迅猛发展的时代背景之下接受图论教育与进行图论研究成了众多相关的青年科学家与工程师的强烈追求图论自身的美好形象,诸如它的强有力的逻辑漂亮的图形高明的数学技巧等等,也对每个爱好科学的年轻人产生了挥之不去的诱惑在高等学校的教学当中图论课成了广大大学生和研究生争相选修的最受欢迎的热门课程之学习图论除了能使我们采用它的成果与方法之外,同样重要的是它能培养我们思考问题与解决问题的能力图论中的问题,看似通俗简单,却往往含有非平凡的难度,每个学习研究图论的人在它面前必须全力以赴、严肃认真地思考问题,有时百思方得其解,有时则是百思仍不得其解的!例如四色猜想和Uem猜想之类的老大难问题以及算法理论中的著名难题“P=NP吗?,都是难到令人生畏的问题事实上,我们尚未弄清楚它们是否需要超长证明而必须使用机器证明,或者数学科学尚未发展到可以用手和纸解决它们的阶段本书除了重视图论的基本理论与常用技巧之外,同时重视有效算法的设计和算法复杂度的分析;研讨时间复杂度是本书的特色之一本书作者不是构造主义者,但本书确乎主要采用了构造性的组合技术来解决问题,由于计算机的介入,构造性解法在当今数学当中日益受到青睐本书另一个特点是对预修课程要求极少,主要靠加法乘法和逻辑推理来解决问题,只用了不多一些集合论与线性代数的知识当然,读者在使用本书时应该自觉调动自己的聪明才智和数学悟性本书每章都留有足够丰富而有趣的作业题大部分题目皆无公式可循,必须由读者自主设计一种方法去解答;可以指望,通过图论的学习和习题与考试的磨炼,读者将会获得一种非本能的智慧和科学思维气质本书共11章如果作本科生教材估计80到100学时可以授完全书.奶果受第一版前官到课时限制,可以略去带*号的内容使得教学可以在60学时左右完成第一章回答图是什么和交代图论最基本的概念从哥尼斯晕七桥问题谈起,通过四色猜想、Ulam猜想、 Hamilton周游世界游戏货郎问题、 Ramsey数NPC问题等数学史上的若干重要而有趣的问题的提出与初步分析,使读者获得对图论的直观认识,接着严格地给出图同构、顶的次数、轨道连通圈、子图、完全图、二分图、三分图等基本的定义还用这些基本概念和方法,严格证明拓扑学中重要的Brouwer不动点定理本章首次介绍“行为算法的概念,从实际模型出发介绍Djkstra最短轨道问题和 Dijkstra算法的规范表述,分析其有效性本章还编入图上博奕的一些内容,体现出聪明竞争的数学思想第二章讲树内容包含树的定义和性质生成树及其个数公式,求最佳生成树的 Kruskal算法,有序二元树, Catalan数, Huffman树,树上密码和树上追捕等有趣的问题事实上,树是图的骨骼和标架,而且是图论难题的试金石,许多图论难题往往首先用树来试探它是否成立,然后再向一般图推广第三章讲平面图得出平面图优美的 Euler拓扑公式,介绍波兰数学家Koratowsky1930年建立的平面图的充分必要条件;利用Euer公式证明正多面体恰有五种本章介绍了图论中最基本最有用的算法之一,即代号为DFS的纵深搜索算法它的“能前进时且前进行不通时则回头”的搜索精神是许多图论算法可以借鉴的基本思路DS还可以求取图的割顶块和极大强连通子图等关键部位,尤其重要的是DFS可以协助建立图的平面嵌入算法第四章讲匹配理论及其应用从Hall婚配问题谈起建立了一系列有关匹配的定理,对二分图介绍了分工问题当中的最大匹配与最佳匹配的匈牙利算法第五章讲着色理论它是图论中精彩纷呈又极其困难的内容介绍了边色数、顶色数、面色数颜色多项式等重要概念讨论诸如排课表安排全校考试仓库设置与信道分配等重要实际问题的色数解法,以及脍炙人口的4CC和颜色多项式等引起历史上大数学家们关注的理论问题4CC已于1976年被美国数学家 Appel和Haken等用计算机给出证明我们在书中介绍了他们的主要思想,即可约的不可避免集的思路以及“充电放电技术但手写的自然语言表述的4色定理的证明将来能否完成,仍是困扰数学家的难题之本章还讲了四大“图数独立数、支配数覆盖数和 Ramsey数它们是图论中非常重要的数字指标在信息传输等领域有重要应用第六章讲 Euler图与 Hamilton图的理论与应用 Euler建立了有效地判定图是否是 Euler图的充分必要条件,可惜对于 Hamilton图至今尚无有效的判别法,没有建立起像样的 Hamilton图的充分必要条件与 Euler图有关的中国邮路问题已被匈牙利数学家 Edmonds有效地解决了,但我们提出的多邮递员中国邮路问题却是一个NPC难题!在 Hamilton图方面,一个首当其冲的问题是为货郎问题设第一版前离计一条耗时最少的售货路线,这一问题亦被证明是NPC中的一员.另外,还有许多有趣的关于 Hamilton图的十分漂亮又十分难解的问题例如n×n的“马图”上国际象棋马的遍历问题等第七章讲有向图中的一些重要问题,包括尚未解决的所谓3x+1问题,有向图的强连通性和可行遍性问题,有向 Hamilton图问题,强连通竞赛图的泛圈定理,竞赛图中的有向 Hamilton轨和王点等许多既有趣又有用的问题第八章讲述网络上的流函数,介绍求最大流的2F算法、 Dinic算法、有上下界的网络最大流的存在性和求法以及有供需要求的流的有效算法,并且证明了“双最定理”,它是网络图论中的核心定理第九章讨论无向图与有向图的顶连通度与边连通度的概念,用网络流技术有效地求取顶连通度与边连通度,给出了一种边数最少的n顶k连通图的构造方法,建立k连通图的刷形结构与圈结构定理等,它们是网络流理论与技术的精彩应用第十章对于无向图与有向图,引人了若干重要矩阵,对于无向图在0-1二元域上建立了一些线性空间;用线性代数的方法对图进行定量研究,是图论由“看图说话”式的综合研究方法或日“文词图论向代数化方法过渡的重要标志;用矩阵演算进行了生成树数目的计算和从一顶到另一顶指定长的道路数目的计算等定量研究第十一章讲Cook定理和NPC理论,对图论中的一些重要问题严格证明了它们是NPC中的问题,例如团独立集、覆盖集、色数、最大断集、 Hamilton轨Hamilton圈货郎问题等都是NPC中的问题,本章内容对数学与计算机科学有原则的重要性,要当做重点内容来教来学,务求深入理解.所给的10道作业题,至少要留一平让学生做出本书是以作者在中国科学技术大学的图论教学内容为蓝本,吸收参加历届教学的师生之反馈意见,顾及近年来科研与教学新形势之要求写成的,应当感谢中国科学技术大学各系昕我主讲图论课的青年朋友们,在答疑和批改作业的过程当中,教学相长,从学生们活泼的解题细节和有趣的提问当中受到许多启发,使本书从内容到呈现方式上更适用于教学还应感谢科学出版社对本书出版的重视和支持,至于书中现存的差错盖因作者孤陋寡学所至,敬请读者批评指正王树禾2003年1月目录第一章图……s1.1从哥尼斯堡七桥问题谈起●◆●●··鲁●咖●●●眼山自自●●鲁鲁●●看昏鲁聊《司D●导司‘身身●●■1.2图的基本概念●●b●●··4鲁命备●■口■督曾口即如导看自鲁會音自曾昏自●曾曾●●41.3轨道和圈…101.4 Brouwer不动点定理●b自看4●●◆◆都命●●最自晶▲命香·●·鲁晶D·吾D·冒鲁冒·冒自1.5求最短轨长度的算法b●●D卓聊最银司聊自鲁鲁鲁鲁即●鲁鲁鲁号·罗令驴聊·早音命咖·171.6图上博弈备昏导↓罪●申·命●单·●●q●·D鲁口口冒甲qq司命口ψ命喜●命一●会鲁自●●昏●●号鲁●·19习题●b各●●自●命●●●●●命婚●哥即即■鲁自自白自鲁鲁D山↓自喜·●自●导?●p第二章树●●↓鲁●命●鲁鲁·●最司晕●◆·2821树的定义与性质●鲁●●●B●办·鲁小●号●·晶···鲁最·■■鲁會●冒■會号切·号282.2生成树的个数…s·323求生成树的算法322.4求最优树的算法…362.5有序二元树372.6n顶有序编码二元树的数目a422.7最佳追捕问题45习题·命念命●命·●■a·●·"48第三章平面图503.1平面图及其平面嵌入…rs5032平面图 Euler公式5233极大平面图…533.4平面图的充要条件35平面嵌入的灌木生长算法●●●●鲁督鲁鲁即最。号●……59习题第四章匹配理论及其应用“…674.1匹配与许配即鲁··p鲁●q曾甲甲D口司即曾中↓·自即●·命口西·口·●●b●各●●咖6742匹配定理6943匹配的应用鲁●●录●最44图的因子分解…80习题…aaa·82v日录第五章着色理论……………………845.1图的边着色…………………………………845.2图的顶着色………………………………………9x53四色猎想为真的机器证明955.4颜色多项式…10155独立集………10556 Ramsey数●刂@·吾■●●●·●4●曾●鲁↓●●●·●即●ψ白自●鲁曾日●春甲D命命■曹●自●p●·●习题■●自●●●●●·咖魯●鲁●●●●●·自會自自·迦命●●·咖自督‘鲁鲁自↓·●嗇噜白·血幽自●舀命·自音司伽自●自·鲁●●●自鲁●自·看串119第六章er图和 Fait图……………1226.1 Euler图……………………………………1226.2中国邮递员问题●↓●●司●q司阝●命聊·甲聊·●·鲁●·●↓●●即●●·●●哥●●口·●1266.3 Hamilton图…130习题……136第七章有向图…………1387.1弱连通、单连通与强连通……………41387.2循环赛图、有向轨和王■。●鲁●鲁●自●●看●鲁·◆●晋鲁鲁●口p口·鲁●鲁看曾●●●·●D看鲁417.3有向 Hamilton图144习题……………………………"…………149第八章最大流的算法1508.12F算法1508.2Dnc分层算法……………………1538.3有上下界网络最大流的算法……………15784有供需要求的网络流算法…………16085关于PERT的两个问题命申咖●◆!导4鲁●◆●咖章61习题…164第九章连通度……679.1顶连通度电b曲…616792边连通度●●·晋晋●●●●自中聊●自●咖會鲁司罪q·斗·旮·鲁··最鲁喜噜鲁唱导晕鲁曾口音自·●中鲁●17193一种边数最少的k连通图…………………………174习题175第十章图的线性空岣与矩阵17710.1图的线性空间1770.2图矩阵●●●自●鲁聊●●幽源●●最幽●最●●●鲁鲁鲁■…18310.3开关网络身自·會●命·●·■命●●命身b●·鲁命●·咖▲●·鲁●●●b自··●@母电_看●b194习题……………………s20l百录I第十一童图论中的NPC问题20411.1问题、实例和算法的时间复杂度………………2041.2 Turing机和NPC●昌鲁■口旮督倡●鲁■●個鲁·鲁·●昌■鲁鲁最●聊鲁■b聊最●4导4●t●20611.3满足问题和Cook定理20911.4图论中的一些NPC问题●ψ鲁●●ψ·◆●鲁●鲁鲁·●●鲁ψ●鲁●●伽●●●●●·44◆鲁●●●鲁·鲁台212习题…………22l习题解答与提示…223参考文献……239