国家工科数学课程教学基地 研究生教学用书 网论及应机 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