图论简明教程

图论是一门应用范围非常广泛的科学，本书针对初学者编写，采用实例、示意图、课后练习等手段，逐步揭示图论中的典型问题，解决策略以及重要应用。国外经典教材·计算机科学与技术图论简明教程〔美)Fred Buckley着Marty Lewinter李慧霸王凤芹译清华大学出版社北京内客筒介木記是一本通佟易懂的图论入门教材。个→分11汽,寸中第1章回顾了所需的数学基础幻识:第2讲解了图论领域的各种其木概念:斤面的8章讲鲜了几类特妹的图及战用,并给出了·些要而常用的算法;最后一章讨论两个附加的专题: Ramsey理论和图支为了于读名理解和掌据基本理谛,书中不仪提供了富的预题,前且每节后配们大量以题,并在!的最后提供部分习题的答案。Simplified Chinese edision copyright C 2005 by PEARSON EDUCATION ASIA LIMITED andTSINGHUA UNIVERSTY PRESSOriginal English language tide from Proprietor's edition of the WorkOriginal English language tite: A Friendly Introd uction to Graph Theory by Fred Buckley, Martytewinter, Copyright C 2003E|sBN:0-13-066949-0Al Righ:s ReservedPublished by arrangement with the origina! publisher, Pearson Educatien, inc, publishing asPearson Education, IncThis edition is authorized for sale only in the People's Republic of China (excluding the SpecialAdministrative Region of Hang Kong and Macao)本书中文体御译版内 Pearson educatian授权给清华大学出板社f巾国增内(不包括中国香港、澳门特别行政区)H版发行北京市版秋局著作杈合同登号图字:(-2042823版权所有,翻印必究。举报电话:410-62782989139110429713801310933本书封百贴有 Pearson edueation(培生教育出版集团)激光防伪标签,无标签者不得销售图书在版编目(IP〕数据图论简明教程/(关)巴克利( Buckley,F.},(关)勒文特( Lewinter,M.)著:李慧,工风芹北京:清华大学业版入,205.1国外经典教材·计算机科学与技术书名原文; A Friendly Introduction to Graph TheoryISBN7-302-10150-7I图…1.①D巴…②勒…③个…④王…图论一教材Ⅳ0575中国版本图书馆CIP数据核字(2004)第1355%6号出版者:潸华大学出版社地址:北京清华大学学研大厦http://www.tur.com.cr邮编1O00A4社总机:0106277017客户服务:0-6277696文膏编辑:徐刚封面设计:久久度文化即装者:北京鑫海金澳胶印有限公司发行者:新华书店总店北京发行所开本:185×260印张:19.25字数:429千了版次:2005年1月第1版2005年1月第:次卬刷书号:1SB、7-302-1015-7TD·1063印教:1~300定价;39.00元本书刘存在文字不清、漏印以及缺页、倒页脱页等印裝质量问题,请与清华大学出版社出版部联系调换。联系电计;《010)627791753103或010)62795704出版说明近年来,我国的高等教育特别是计算机学科教育。进行了一系列大的调整和改革,急需·批门类齐仝、具有国际先进水平的计算机经典教材,以适应当前我国计算机科学的教学需要。通过使用国外先进的经典教材,可以了解并吸收国际先进的教学思想和教学方法,仗我国的计算机科学教育能够跟上国际计算机教育发展的步伐,从而培育出更多具有国际水准的计算机与业人小,增强我国计算机产业的核心竞争力。为此,我们从国外知名的出版集团 Pearson引进这套“国外经典教材·计算机科学与技术”教材。作为全球最大的图书出版机构, Pearson在离等教育领域有着不凡的表现,其下属的Prentice hall和 Addison wesley出版社是全球计算机高等教育的龙头出版机构。清华大学出版社与 Pearson出版集团长期保持着紧友好的合作关系,这次引进的“外经典教材·计算机科学与技术”教材大部分出自 Prentice Hall和 Addison Wesley两家出版社。为了织诿套教材的出版,我们在国内聘诮了一批知名的专家和教授,成立了一个专门的教豺编审委员会。教材编审委员会的运作从教材的选题阶段即开始启动,各位委员根据匡內外高等院校计算机科学及相关专业的现有课程体系,并结合各个专业的培养方向,从 Pearson出版的计算机系列教材中精心挑选针对性强的题材,以保证该套教材的优秀性和领先性,避免出现“低质重复引进”或“高质消化不良”的现象为了保证出版质量:我们为该套教材配备了批经验丰高的编辑、排版、校对人员,制定了更加严格的出版流程。本套教材的译者,仝部来自于对应专业的高校教师或拥有相关经验的I!专家。每本教材的责编在翻译伊始,就定期不间断地与该书的译者进行交流与反馈。为」尽可能地保与发扬教材原者的精华,在经过翻译、排版和传统的三审二校之后,我们还请编审委员或相关的专家教授对文稿进行审读,以最大程度地弥补和修止在前面一系列加工过程中对教材造成的误差和瑕疵。由于时间紧迫和受全体制人员白身能力所限,该套教材在出版过程中很可能还存在些遗憾,欢迎广大师生来电来信批评指正。同时,也欢迎读者朋友积极向我们推荐各类优秀的豳外计算杌教材,共同为我国高等院校计算机教育事业贡献力量。清华大学出版社200403.20国外经典教材·计算机科学与技术编审委员会主任委员孙家广清华大学教授副主任委员周立柱清华大学教授委员(按姓氏笔画排序):王成山天津大学教授王珊中国人民人学教授冯少荣厦门大学教授钙全源西南交通大学教授刘乐善华中科技人宁教授刘腾红中财经政法大学教授吉根林南京师汇大学教授孙吉贵吉林大学教授阢秋琦北京交通大学教授何晨上海交通大学教授是锋复日大学教授李肜云南大学教授沈钓毅西安父通大学教授邵志清华东理工大学教授陈纯浙江大学教授陈钟北京人学教授陈道蓄南京大亭教授周伯生北京航空航天人学教授孟祥旭山尔大学教授姚淑珍北京航空航天大学教授徐佩霞中科学技术大学教授徐晓飞哈尔滨J业大学教授秦小麟南京航窄航天大学教授钱培德外州大学教授兽兀人北京理T人学教授龚卢蓉苏州大学教授谢术亻中国人民解放军喱工大学教授译者序当欧拉在1736年汸问哥尼斯堡城时,他发现当地有一条名叫普雷哥尔的河流横经城中,在沁七建七桥。市民巾在从事一项非常有趣的消逍活动,这项活功是在星期六进行的,要求一次走过所有七座桥,且每座桥只能经过…次,而且起点与终点必须是同地点。这项活动难到了许多人这类似于常的“笔画”问题。欧拉证明了这是不可能完成的,理由如下:除了起点以外,每次画到一个点,那么一定会离开这个点,所以与该点相连的边数一定为偶数山于最后必回到起点,所以与起点相连的边亦为偶数。七桥河对应的图形中,没们一点迕有偶数条边,扶此上述的任务是小可能实现的。此后,欧拉发衣了著名的论文《依据几何位置的解题方法》,这是图论领域的第篇论文,标志荐图论的诞生。这种利用模型图来解决问题的方法在当时还只是个别现象图论的真正发展始于二十纪五六|年代,这和计算机技术的发展是同步的。由此也可以说,图论是一门既古老又年轻的学科,冂显现出活力。本书的英文原名是 A friendly introduction如 o graph theon,正如名称所表述的那样,书牛的內容通俗易懂,对读者的基础知识要求不高,各种概念十分湑楚,所有的证明和算法也都力求简洁明了此外,虽是-本以理论为主的书,但作者引用了大量现实生活的事例,既使得内容趣味盎然,又能引导读者理论联系实际。总之,这是一本出色的图论入门教材冂以为读者打下良好的理论基础主要H李霸、于风芹翻谧。全书最后巾李隸霸统稿。在翻译过程中,顾剑,钞吗、吕雅帅、王睿伯、于潇、孙元波、万光宁绺予我们很大的帮助,在此特别感谢。我们还要特别感谢严琰祠忐在这段时间对我们的支持和鼓励。肖国尊负责本书翻译质量和进度的控制与管理。在本书翻译过科中,我们对书中的疏漏之处进行了更止。此外,对一些笔浜和排版错误也进行了校止。敬请各似读者就本书提供反馈意见,我们希望通过读者的意见来了解自己的不足,以求在今后的译作中更多地和更切实际地考虑读者的需要译老前言终论是-门极们趣味的学问,其疒阔的应川域涵盖∫人类学、计算机科苧、化学境保护、沇体动力峃、心埤学、社会学、交通管理、电信领域等等。在20凹纪,隄着运筹学的出现,图论更是为确立其越的地位起到了1分重要的作用。严格地讲,图论是组合数学的个分艾,哲如,它交叉运用了拓扑学、群论和数论。图论旷定理和证明的难度高低不等,有的简单易愷,有的儿乎不习理解,然图论终究还只是研究点相线的学问。图论的应用非常广泛,不仅局限于数学和计算机科学,因此各业的学生都应该打下定的图论基础,这样他们就会多掌握-种强大而灵活的工具米分析和处理自己学科领域中的问题。这本教材主焐面向≯科水平的读者,使他们能计较容易理解。我们仅仅假设读耆具台定的代数基仙,因此,本书儆开了座大门,无论数学、计算机科学、社会科学、鹿学还是工程学专业的学生,只要有需求,你都能尽早地接触这个精彩而颇有益的研究域。然这是本易懂拊教材,仉读的时候还是应该拿上纸和笔——这不烂睡前的休闲读物。书中的习題有易有堆,能够体现相应章节的内容。书有解答或提示,其涵盖了大部分的巧题。此外,应该意识到,数学个是项观赏性质的体育赛事(当然当您看到仃人刈某个重要结论做出了简学得惊人的证明,您也定会觉得这是件激动人心的事),请务必要做习题,否则当您读到最后一章时,第一章的內容就会被忘到脑后。能够做完较难习题的勤勉的学生会得到很大益处——为今后的图论研究打卜坚实基础,他们也会有能力将图论的馬想应用到纷乱复杂的现实问题牛大代第1章,我们讨论了必备的础機念,议者应该熟练掌握这些内容。我们虽然称这章为复习,但其闪容仍然十分亢备,提供了必要的数学工具来帮助读者理解全书其余部分的内容。因此这·章讲了集合、函数、奇偶性、数学法、证明技巧、计数原理、排列组合、 Pascal三闫形和组合恒等式。刈于不熟悉证明技巧的学生来说,太章对他们会有很大的帮助。而刈于基础比较扎实的学生,老师可有选择地跳过本章的部分甚至全部內容如前所述,图论的应用极为广泛。在第2章中,我们将介组图论中最基本的概念,同时也将展示图论的些应用领域。当然:我们会在后看到许多其他的应用有一类非常重要的图值得我们用单独的一章(第3章〕来介绍,这就是树。由于结构简单,树常常被用作新理论的试验沥。树的慨念起源于许多领域,例如分析务层次、求具有最小代价的运输网终等等,此外树也是计算机科学中的一种十分重要的数据结构ε树足更大的一类图的特例:这类图称作二分图。在第3章中,我们讲述了树、:分图以及它们」应用。最后,木以「作分配题结束Ⅵ囡沧简明教程距离的觀念在图论的理论和实践中应用很广泛,许多有关图的操作都要仅用距离例如构判定、改问题。另外,距离也是许多对称概念的基础。许多图屮心的概念亦由距离来定义,中心的概念在场地布局问题中起着关键的作用。图论的众多算法都与距离相关,这些算法往往需要在图中搜索各种长度的路。出离也在连通性生问题中扮演着重要的角色,而迕通性问趣涉及到计算机网络的可靠性和健壮性问题,因而有|分关键的地位。在第4阜,我们将讨论关亍距离和蓬通性的一屿重媭概念和结论,然作为总结.我们将解决一个场地布局问题,并给出计算机网络的可靠性概念图论中亡多的理论和实际问题都需要我们以某种法遍历整个图。例如在某些问题中,我们的目标是求出·条迹或回路,满足经过每条边·次且仅次;在丹-些问题中我们可能需要求出一条路或圈,满足经过每个结点次且仅一次。我们在第5章中讨论这些问题,然后以两个著名的问题结束,这两个问题是中国邮递员问题和旅行售货员问题许多由图论描述的现实问题都需要把结点集或边集划分为一些不相交的子集,使同子集中的所有元素互不相邻。这类问题中比较常见的有;安排会议或考试的日程以兔冲突还有安排化学品的存储以避免互相反应。这些问题都与第6章的主题图着色相关。矩阵是由数字红成的矩形表。在计算机中存储图的一种最简单的方法就是用矩阵,或者说数组,这是矩阵在计算机科学中的对应数琚结构。图论有效地利用了矩阵,将其作为检測结构和其他性质的工具。在第7章中,我们首先复与了矩阵的一些基本概念,然后讲述了矩阵在图论的一些应用。图论和计算机科学之间有着千丝力缕的联系,因此算法在现代图论中有举足轻重的地位,以至好几本著作都专注于图的算法。在第8章中,我们将简单地介绍一下图论算法及其应用。首先给出了重要的广度优先搜索和深度优先搜索算法,然后考察了图着色和树编码算法,其他一些算法也在行文中有所体现。我们将不在这里考察算法的效率和NP完全性,但是建议有兴趣的读者参考一下 Buckley利 Harary、 Chartrand和 Gellermann还有Goud剎这些问题的讨论如果能在平面内将图画出且使其边各不相交叉,那么这个图就是可平面化的。可平面图曾经受到了多年的广泛关注,其原因在于个长期困惑人们的问题——四色猜想,这个问题最终花费了百多年的时间才得到证明。时至今日,可平图在其应用领域仍然占有很重要的地位,例如在运筹学中的场地布局,或是计算杌科学中的印刷电路板设讦等问题中,可平面图都起着至关重要的作月。在第9章中我们就来讨论可平面图及其性质简单的图论模型不足以刻某些现实问题,我们已经见过不少这样的实例。在第10,我们将考虑丹一些结树。有向图和图类似,只是边有方向。有些问题中,流(信息交通、液体、电予等)的方向性比较重要,有向图就是对这种问题建模的。当有向边上存在流的大小限制后,就得到了网络。一类特殊的没有燃的有向图称统筹图,它的边上有权,表示工作持续时问。这种有向图用来安排复杂工程的各项工作。在第10章,将介绍不同种类的有向图及特点,也将研究网络流问题并缭出求最大流的算法,最后讨论统筹图前言VIl及共应用在第章,我们讨论了两个专题: Ramsey理论科图支配。前者沙及图的边着色,而后者则与距离和独京性有关,并且有着广泛的应用。这两个专题有-个共同之处,就是研究它们都很有趣我们衷心希望这本书将带来一个愉快的阅读过程,止如我们愉快的写作过程-样