国家工科数学课程教学基地 研究生教学用书 网论及应机 Graph Theory and Its Applications 电子科技大学应用数学学院张先迪 李正良主编 高等教育出版社
图论及其应用 Graph Theory and Its Applications 电子科技大学应用数学学院 张先迪李正良主编 高等教育出版社
内容提要 本书是一本有一定学术参考价值的理工科研究生教学用书。它是根据作者多年 从事研究生图论教学的经验，并结合国内外优秀教材的长处和图论的新近发展状况编 写而成。全书共十章，分别讨论图的基本概念、树、图的连通度、Enler图与Hamilton 图、匹配与因子分解、平面图、图的着色、Ramsey定理、有向图以及代数图论中的一些 内容。其内容详尽，既有基本内容，又有提高内容；不仅较为全面地介绍了图论中的 一些基本概念，基本理论和基本方法，而且还反映了近期图论及其应用中的一些研究 课题和结论。 本书论证简明，叙述清晰，内容深人浅出，循序渐进，便于教学。书中还配有较多 数量的典型例题和习题，既可作为研究生教学用书，也可作为本科高年级学生的教材 以及有关科技工作者的参考书。 图书在版编目(CIP)数据 图论及其应用/张先迪，李正良主编.一北京：高等教 育出版社，2005.2 ISBN7-04-016090-0 I.图·Ⅱ①张.②李.Ⅲ.图论研究生 教材N.0157.5 中国版本图书馆CIP数据核字(2004)第140723号 策划编辑李艳馥 责任编辑张耀明 封面设计李卫青 责任绘图黄建英 版式设计史新藏 责任校对王超 责任印制陈伟光 出版发行高等教育出版社 购书热线010-58581118 杜址 北京市西城区德外大街4号 免费咨询800-810-0598 邮政编码100011 网 址hitp:/小www,hep.ed.c 总机010-58581000 http://www.hep.com.cn 网上订购 http://www.h raco.com 销北京蓝色畅想图书发行有限公司 http://www.landraco.com.cn 刷北京市白帆印务有限公司 印 次2005年2月第1版 印 次2005年2月第1次印刷 字 数320000 足 价26.80元 本书如有缺页、倒页、脱页等质量问题，请到所购图书销售部门联系调换。 版权所有侵权必究 物料号16090-00
前 言 现实生活中，许多问题都可归结为一个由点和线组成的图形的问题 例如，由点代表车站，线代表铁路线的铁路网络图；点代表路口，线代表街 道的城市交通图；点代表管道接头，线代表管道的自来水供水系统：点代 表电网络的结点，线代表结点间的电气元件的电网络图等等。图论正是 研究这些由点和线组成的“图形”问题的一门学科。 图论起源于18世纪，其第-篇论文是由Euler(1707-1782)于1736 年所完成。这篇论文不仅解决了一个当时还没有解决的著名问题 一哥 尼斯堡(Konigsberg)七桥问题（见第四章），也使欧拉成为了图论和拓扑 学的创始人。图论诞生后，特别是近30年来发展十分迅速，应用也十分 广泛。其应用已涉及物理学、化学、运筹学、计算机科学、信息论、控制论、 网络理论、社会科学以及管理科学等诸多领城。由于图论与计算机科学 紧密相联系，近若干年来，计算机科学、计算机网络的迅猛发展，更拓展了 图论的应用发展空间。在计算机的许多领域内，它都占有一席之地。图 论在其他数学分支中，如矩阵论、群论中也有其重要的应用。 本书是根据作者多年从事图论教学的经验并结合国内外优秀教材的 长处和图论的新近发展状况编写而成的。书中着重介绍了图论及其应用 中的一些基本概念、基本理论和基本方法，同时也对一些扩展问题展开了 讨论，并注意到了适当地反映图论研究中一些近期的研究问题和研究结 果。全书共十章，分别讨论图的基本概念、树、图的连通度、Euler图与 Hamilton图、匹配与因子分解、平面图、图的着色、Ramsey定理、有向图 以及代数图论中的一些基本内容。 本书既有基本内容，又有提高内容，编排由浅入深，循序渐进，层次分 明，并配有较多的实例和难易程度不同的习题。教师可根据教学要求、课 时多少、授课对象、灵活选取授课内容。书中§1.6、§1.7、§3.4、§4.7、 §4.9、§7.6、§7.7、§8.3、§9.7及第十章等章节具有相对独立性，这 些章节选讲或不讲基本不影响其他部分的学习。为了在有限的篇幅中包 含尽可能多的信息量，书中一些较繁的证明被省略。书中证明后的符号 “☐”表示“证毕”。 本书由张先迪教授和李正良教授主编。执笔分别为张先迪（第三 六、七、八、九、十章)、李正良（第一、四、五章）和杨春（第二章）
前言 本书由谢云荪教授（电子科技大学）主审。他在肯定本书的同时，提 出了十分宝贵的意见和建议，在此深表感谢。 本书的编写得到了电子科技大学研究生教材建设基金的资助，得到 了电子科技大学应用数学学院和高等教育出版社理科分杜的大力支持和 帮助，在此表示衷心感谢。同时还要感谢洪继俊和汪小平老师，他们为书 稿的录入作了大量的工作。 由于编者水平的局限，书中难免存在一些缺点和错误，悬请同行专家 及读者提出宝贵意见和建议，以使本书得以不断改进和完善。 编者 2004.10
目 录 第一章图的基本概念.1 §1.1图和简单图.1 §1.2子图与图的运算.5 S1.3路与图的连通性.10 S14最短路及其算法 §1.5图的代数表示及其特征 .15 51.6极图.20 §1.7交图与团图.26 习题1.29 第二章树.31 §2】树的概念与性质.31 §2.2树的中心与形心.33 §2.3生成树.35 §2.4最小生成树.40 习题2.43 第三章图的连通度.45 §3.1割边，割点和块.46 §3.2连通度.50 §33应用.55 §3.4图的宽距离和宽直径 .58 习题3.65 第四章Euler图与Hamilton图.69 §41Eler图.69 S42高效率计算机鼓轮的设计.71 §4.3中国邮递员问题.73 S4.4 Hamilton图.78 S4.5度极大非Hamilton图.84 S4.6旅行售货员问题.87 §4.7超Hamilton图.89 S4.8E图和H图的联系.94
目录 S4,9无限图中的Euler,Hamilton问题.96 习题4 .97 第五章匹配与因子分解.100 §5.1匹配.100 S5.2偶图的匹配与覆盖.101 §5.3 Tutte定理与完美匹配.104 §5.4因子分解.105 $5.5最优匹配与匈牙利算法 .111 §5.6匹配在矩阵理论中的应用 .116 习题5.117 第六章平面图.119 S6.1平面图119 S6.2一些特殊平面图及平面图的对偶图.127 §6.3平面图的判定及涉及平面性的不变量.134 6.4平面性算法. .138 习题6.143 第七章图的着色.147 §7.1图的边着色.147 §7.2顶点着色.152 7.3与色数有关的几类图.157 §7.4完美图. 163 S7.5着色的计数与色多项式. 166 S7.6Li5t着色.173 §7.7全着色.176 §7.8着色的应用.185 习题7.187 第八章Ramsey定理 .191 S8.1独立集和覆盖 .191 §8.2 Ramsey定理.195 S8.3广义Ramsey数.202 S84应用.205 习题8.206 第九章有向图. 209 S9.1有向图及其连通性. 209 S9.2有向树.217
目录 §93有向路与有向圈 .225 S9.4生成树的计数.232 89.5运输网络与最大流.240 S9.6求最大流的算法及最大流问题的推广.244 $9.7网络流与Menger定理.253 习题9.256 第十章图、群与矩阵 .260 §10.1图的特征值与谱.260 §10.2图的自同构群.267 S10.3图的对称性与强正则图.275 §10.4 Cayley图.281 10.5循环图.286 S10.6 Cayley图的Hamilton性. 291 习题10.295 主要参考文献.298
第一章图的基本概念 历史上，图论曾经被很多数学家各自独立地建立过，因为图论本身就 是应用数学的一部分，所以这种情况并不是偶然的巧合.事实上，最早是 Euler的著作中出现了这样的文字，虽然，他所考虑的原始问题似乎是 个颇为无聊的七桥问题，然而这个问题确实有其深刻的实际背景.后来， Kirechoff对电网络的研究导致他发展了图论的基本概念和关于图中的 树的定理；同时，Cayler则是为了有机化学中的同分异构物的计数问题而 考虑到树.随着Hamilton问题和四色猜想的出现，更大大地推动了图论 的发展。本章介绍图和描述图的局部结构的一些基本概念和术语.这里 的名词和概念较多，但它们都是基本的.此外，我们还要初步介绍完全子 图、极图理论、交图、团图和图的一些有用的运算.这些对以后的讨论是 非常重要的，希望读者能熟练地掌握， §1.1图和简单图 我们所讨论的图(graph)与人们通常所熟悉的图，例如圆、椭圆、函数 图表等是很不相同的.图论中所谓的图是指某类具体事物和这些事物之 间的联系。如果我们用点表示具体事物，用连线表示两个具体事物之间 的联系.那么，一个图就是由一个表示具体事物的点的集合和表示事物 之间联系的一些线的集合所构成 定义1一个图G定义为一个有序对(V,E),记为G=(V,E),其中 (1)V是一个非空集合，称为顶点集或点集，其元素称为顶点或点 V|表示顶点数： (2)E是由V中的点组成的无序点对构成的集合，称为边集，其元素 称为边，且同一点对在E中可出现多次. 图G的顶点集也记为V(G),边集也记为E(G).顶点集和边集都有 限的图称为有限图.只有一个顶点而无边的图称为平凡图.其他所有的 图都称为非平凡图.边集为空的图称为空图.图G的顶点数（或阶数）和 边数可分别用符号n(G)和m(G)表示.连接两个相同顶点的边的条数， 称为边的重数.重数大于1的边称为重边.端点重合为一点的边称为环 既没有环也没有重边的图称为简单图。其他所有的图都称为复合图
第一章图的基本概念 边记为uw,也可记uv为e,即e=um.此时称u和v是e的端点，并称 u和v相邻，u(或)与e相关联.若两条边有一个共同的端点，则称这两 条边相邻.若用小圆点代表点，连线代表边，则可将一个图用“图形”来 表示 一、图的同构 定义2设有两个图G=(V1,E)和G2=(V2,E2),若在其顶点集 合之间存在双射，即存在一一对应的关系，使得边之间有如下的关系：设 12,+h,∈V1,2∈V2;w∈E,当且仅当h∈E2,且 山)的重数与的重数相同，则称两图同构，记为G二G2, 例如在图1-1中的G和G2就是同构的， 图1-1 不难证明，图的同构关系是一个等价关系。所有的图的集合，按照同 构关系可划分为一些等价类，以所有等价类为元素构成的集合称为商集， 尽管商集中的元素是一个集合，但这个集合中的任两个图均有相同的结 构，差异只是顶点和边的名称不同.因此在图的图形表示中我们可以不 给图的点和边标上符号，称这样的图为非标定（号）图，否则称为标定（号） 图.非标定图实际上是代表一类相互同构的图。不误解时我们也不严格 区分标定图与非标定图。 二、完全图，偶图，补图 每两个不同的顶点之间都有一条边相连的简单图称为完全图.在同 构意义下，n个顶点的完全图只有一个，记为K,所谓偶图（或二部图）是 指具有二分类(X,Y)的图，它的点集可以分解为两个（非空）子集X和Y, 使得每条边的一个端点在X中，另一个端点在Y中：完全偶图是指具有 二分类(X,Y)的简单偶图，其中X的每个顶点与Y的每个顶点相连.若 |X|=m,|Y|=n,则这样的完全偶图记为Km·图1-2(a)是Ks的图 形，由立方体的顶点和边所确定的图（如图1-2(b)是偶图：图1-2(c)