图论是训练离散数学证明技巧的乐园，其结果在计算科学、社会科学和自然科学等多个领域具有广泛应用本书可作为本科生或低年级研究生1~2个学期的图论课程的教材本书不要求任何图论的预备知识尽管本书包含许多算法和应用，但重点是理解图的结构和解决图论问题的技巧。
目前已经有许多图论的教科书由J. A. Bondy和U. S. R. Murty撰写的优秀教材《Graph Theory with Applications》(Macmillan/NorthHolland［1976］)把重点放在证明和应用两个方面，本书的草稿参照了该书图论至今仍是一门年轻的学科，应该如何介绍图论的题材，大家仍然没有一致的看法主题的挑选和顺序的安排，证明方法、目标和基本题目的选择等，一直是众说纷纭作者在多次修改本书的过程中认识到，对于这些问题做决定是很困难的本书是作者对这些争议的一点贡献
第2版
第2版的修订主要是为了更易于学生学习和更便于教师教学本书的总体内容没有很大的变化，但是对内容的表述方式做了修改，使其更容易理解，这一点在本书的前几部分尤其明显有关第2版所做的某些修改，稍后将详细讨论，此处仅做一下概述
非选学节中的选学材料现在用*号标明这些内容不会在后续内容中使用，因而可以跳过多数选修内容忽略以后，本书可以作为一学期的图论教学内容如某一小节标记为“选学”，则整个小节的内容都是可选修的，而不再标记该小节中的各个项
对于缺乏基础知识的学生，附录A概述了有关集合、逻辑、归纳法、计数、二项式系数、关系和鸽巢原理等方面的相关知识
对于很多证明都重新进行了更细致的叙述，并增加了更多的例子
增加了350多道习题，其中多数是第1～7章中的比较容易的题目这样，本书的总习题量超过了1 200道
增加了100多幅插图本书的插图总量超过了400幅为区别插图中包括的几种类型的边，书中把原有的实线和虚线改变为粗线和实线，增加了插图的清晰度
相对简单的问题都集中放在各节习题的前面部分，用来作为热身练习一些习题进行了改写，使其语义更加清楚
对习题的提示做了补充，增加了一个“部分习题的提示”的附录
为了易于查找，概念术语都用黑体字给出，其中绝大多数都出现在概念定义中
为了易于查找，将术语集中在附录D中
有关欧拉回路、有向图和Turn定理的内容经过了重新编排，以提高学习效率
第6章和第7章交换了顺序以便先介绍平面性的思想，与复杂性有关的部分经过改编安排在附录中
改正了专业术语的错误，并更加强调与本书内容直接相关的术语
特点
本书特点就是使学生能够深入理解本书的内容. 本书包括对证明技巧的讨论、1 200多道习题、400多幅插图以及许多例子本书正文中出现的结论都有详细完整的证明.
很多本科生在开始学习图论前很少涉足证明技巧，附录A提供的背景阅读材料有助于初学者提高这方面的技巧如果初学者在理解和书写证明时有困难，请结合第1章仔细阅读附录A虽然本书前面的一些章节仍然讨论了一些证明技巧(特别是归纳法)，但是更多的背景知识（特别是集合、函数、关系和初等计数）已经安排在附录A中.
大多数习题都需要证明很多本科生在论证问题方面的实践不足，这将影响他们对于图论和其他数学知识的兴趣即使抛开数学，论证问题方面的智能训练也是极其重要的，作者希望学生喜欢这种训练在求解问题时，学生应该注意语言的使用(“说出的即是你要表达的”)，而且表达准确(“表达的即是你要说出的”).
. 虽然图论中许多术语本身就表明了它们各自的定义，但太多的专业术语定义会影响内容的可读性数学家喜欢一开始就给出一系列定义，但学生们大都愿意熟练掌握一个概念后再去接受下一个概念，这样他们会学得更好学生的这个意愿和审稿者的建议使作者推迟了很多定义的给出，直到需要的时候例如，笛卡儿积的定义在5.1节的着色问题部分给出，线图的定义则分别在4.2节的Menger定理部分和7.1节的边着色部分给出，诱导子图的定义和连接的定义分别推迟到1.2节和3.1节给出.
书中已经改变了对有向图介绍的位置，将其推迟到了1.4节如果在介绍图的同时介绍有向图，会使学生产生迷惑在第1章的最后介绍有向图相对容易学习，学生能够在了解两种图的差别的同时加强对基本概念的理解在连通性问题上，本书仍会将这两个模型放在一起讨论.
本书比其他图论书籍包含了更多的内容作为“其他主题”的可选章节，最后一章汇集了很多图论最新研究结果，使得本书适合不同层次的读者使用本科生的教学内容可以由前七章组成(去掉大部分选学内容)，第8章可作为对相应主题感兴趣的学生的阅读材料研究生的教学内容可以采用如下结构：第1章和第2章作为推荐阅读材料，在课堂上快速进入第3章，并讲授第8章的一些主题.第8章以及前面章节的选学内容也可作为高级图论课程的基本内容.
很多图论中的结论都有多个证明，这样有助于提高学生采用多种方法处理问题的灵活性对于同一个问题，本书可能在注记中谈及一些不同的证明方法，另外一些留作练习.
很多习题都有提示，一些提示在习题中直接给出，另一些在附录C中给出标记了“－”的问题比较简单，标记了“＋”的问题比较难标记了“+”的问题不应该作为本科生的作业标记了“！”的问题则特别有价值、有启发性或有趣标记了“*”的问题涉及可选内容
每节习题都以标记“－”的问题开始，根据相关章节内容的先后顺序排列，这部分问题的结束由一组点来标记这部分问题要么是检查对概念的理解，要么是对相关章节内容的结论的直接应用作者在课堂上推荐一些这样的问题作为热身练习，在完成主要的作业题(多数这样的习题标记了“！”)之前检查学生对基本概念的理解多数标记“－”的问题是很好的考试题如果在考试中使用其他习题，从附录C中选取一些提示是很好的做法
涉及多个概念的习题在最后一个相关概念介绍完之后给出正文中一个概念介绍完后有时会有指针指向与该概念相关的习题全书有很多这样的指针每一节对本节习题的引用仅由该习题在这节的习题中的相对编号给出，对其他习题的交叉引用将通过其章、节和习题编号给出
组织和修改
本书第1版力求内容的承接关系以及证明难度和算法复杂性循序渐进
在第2版中，本书继续保持这种风格欧拉回路和哈密顿环仍在不同章节，并且离得更远欧拉回路的简单介绍在1.2节，其中包括了与之密切相关的材料原来2.4节的部分内容移到其他章节的相关部分，并删除了Fleury算法
第1章被彻底改写本书仍然没有使用术语“多重图”它引起的问题比它能解决的问题要多，因为很多学生认为一个多重图必须有多条边一般来说，只在需要的时候才在图的前面加上“简单”，而将“图”理解成普通的图，这样不会引起误解，因为偶尔在一些特定场合中仅考虑简单图才有意义
第2版中对第1章的定义进行了处理，使其更加容易理解和精确，特别是路径、轨迹和通道等概念原来1.1节对于基本定义的非正式分组已经由一个“定义”部分所取代定义部分能够帮助学生更容易找到所需要的定义
除了有关同构的内容，1.1节对Petersen图进行了更精确的介绍，对于分解和围长的概念也有清晰的阐述这为以后的相关讨论提供了方便，同时也可以激发读者对图同构之外的其他问题的兴趣
1.2节到1.4节变得更加条理清晰对欧拉回路的处理进一步完善了1.2节 1.3节的一些内容被删除了，从而突出了度和计数，这节还包含了原1.4节有关顶点度的材料1.4节现在主要是对有向图的介绍
由于树和距离之间具有很多联系，所以第2章同时包含了这两部分内容很多习题包含这些概念计算距离的算法也会产生或用到树
很多图论专家认为KnigEgervry 定理需要一个与网络流无关的独立证明学生在区分“k连通”和“连通度k”时感到困难，而且“k可染色”和“色数k”也有同样的问题因此，书中首先介绍匹配，然后用匹配证明Menger定理匹配和连通性都在着色问题中有所应用
为了满足众多读者的要求，本书在3.1节结尾增加了一个可选小节，介绍支配集作者通过强调顶点覆盖而不是增广路径，并使用很多较好的例子，使得加权二部匹配的概念更加清晰易懂
在第1版中，Turn定理仅使用了顶点度和归纳的基本思想，因此这部分内容在第1章给出这样的安排使学生感到Turn定理太抽象，难以理解为此，考虑到与着色相关的极值问题，本书在1.3节仅保留了简单三角自由的情况(芒泰尔定理)，而将完整的Turn定理移至52节
关于平面性的章节现在移至“边和环”的前面当课时不足时，平面性应优先讲授，因为它比边着色和哈密顿环更重要与平面性相关问题的可视性较强，易于被学生接受，而且许多学生在这之前已经遇到过这些问题相对于本书前面的材料来说，平面图的一些想法似乎比证明边着色问题和哈密顿环问题使用的方法更易于接受和理解
先讨论平面性问题将会使第7章的内容更加条理清晰新的编排将会使平面性、边着色、哈密顿环等问题之间关系的讨论更全面，并自然引出超出四色定理的可选新内容
当学生们发现着色和哈密顿环问题缺乏好的算法时，很多人开始关心问题的NP完全性附录B满足了这些读者的好奇心使用形式语言来叙述NP完全性问题会使问题更抽象，因此很多学生更喜欢用图论的术语来描述NP完全问题NP完全性的证明也说明了“图变换”的多样性和有用性
本书探讨了基本结果之间的关系2-因子Petersen定理使用了欧拉回路和二部匹配；Menger定理和最大流最小割定理的等价关系比第1版有更深入的探讨；“棒球淘汰问题”（Baseball Elimination）的应用被论述得更加详尽；k-色-临界图的k-1-连通性(第5章)用到了二部匹配；5.3节对完美图做了简要的介绍，着重强调了弦图与其他书相比，本书不仅包括了Vizing定理的算法证明，还包括了使用Thomassen方法对Kuratowski定理的证明
本书的前七章还有很多其他的增加和改进第6章末尾对Heawood公式和RobertsonSeymour定理进行了简要的讨论7.1节增加了关于边色数的Shannon界的证明5.3节给出了一个有关单纯顶点的更强的结论，这使得对弦图的特征刻画变得更简单明了在63节，删掉了Birkhoff菱形的可归约性证明，增加了有关卸载问题的讨论定理证明的讨论是可选的，目的是在没有开始详细证明之前给出关于证明的思路从这个观点出发，可归约性证明似乎不是重点
第8章包含了一些图论的新内容，这些内容不适合作为本科生的教学内容这一章比前几章的内容更复杂而且撰写得更简练这一章的各节都是独立的，每节都从一个大的主题中选择了最具吸引力的研究结果某些节越接近结束理解起来越困难在讲授这部分内容时，教师应该选取某些节比较靠前的内容讲授，而不要讲授全部内容
第8章和前七章的可选部分可能偶有相关，但一般都有交叉引用指出这些联系与第1版相比，第8章的题材没有重大的改变，只是改正了错误并且许多地方的叙述更加清晰
在The Art of Combinatorics一书中将更全面地讨论高级图论其中，第Ⅰ卷介绍极值图论，第Ⅱ卷介绍图的结构，第Ⅲ卷讨论拟阵和整数规划（包括网络流），第Ⅳ卷重点介绍组合学中的方法并讨论图特别是随机图的各个方面
课程的设计
第1章到第7章的22节，每节可占用2个学时，跳过其中大部分可选内容(即标注了星号或选学小节)作者讲课时，用8个学时讲解第1章；用12个学时讲解第4章和第5章，每章6个学时；用20个学时讲解第2章、第3章、第6章和第7章，每章5个学时于是，本书的基本内容可以用40个学时讲授完毕教师也可以在第1章花更多的时间，而删掉后面章节的部分内容
在第1章后面的各章，最重要的内容都在第1节在一学期内只讲授这部分内容，也能使学生对图论有一个大致的了解在第2、4、5、6、7章的第2节中，分别讲授Cayley公式、Menger定理、Mycielski构造、Kuratowski定理和Dirac定理，这对学生是有益的
一些可选内容在课堂上讲授是很具有吸引力的例如，作者经常讲授2.1节的不相交生成树和3.2节的稳定匹配等内容作者也讲授33节有关f因子的可选子节前七章的某些子节标记为可选内容，是因为以后不再涉及这些内容，而且这些内容也不属于图论的基础部分然而，这些内容是能够引起学生兴趣的很好的应用对学生来说，可选内容在期末考试时不会出现
跳过前两章的研究生课程应该包括如下的内容：图序列、有向图的核、Cayley公式、矩阵树定理和Kruskal算法
如果在每年四学期制的一个学期中讲授图论课程，需要突出重点这里建议按照下面的大纲讲授：1.1节，邻接矩阵、同构和Petersen图；1.2节，全部；1.3节，度和公式和大二部子图；1.4节，讲授到强分量，加上竞赛图；2.1节，讲授到树中心；2.2节，讲授到矩阵树定理；2.3节，Kruskal算法；3.1节，几乎全部；3.2节，不讲；3.3节，Tutte定理的叙述以及Petersen结论的证明；4.1节，讲授到块的定义，忽略Harary图；4.2节，讲授到开放耳分解，加上Menger定理；4.3节，流和分割的对偶性并叙述最大流与最小割之间的相等关系；5.1节，讲授到SzekeresWilf定理；5.2节，Mycielski构造和Turn定理；5.3节，讲授到着色递归，加上弦图的完美性；6.1节，K5和K3,3 的非平面性、对偶图的例子以及欧拉公式及其应用；6.2节，Kuratowski定理和Tutte定理的叙述和例子；6.3节，五色定理和交叉数的思想；7.1节，讲授到Vizing定理；7.2节，讲授到Ore条件和Chvtal-Erds条件；7.3节，Tait定理和Grinberg定理
教学方法的进一步说明
在这一版中，作者强调可以自然地从相关材料中得到的那些结果，讲课时强调这些内容有助于内容的融会贯通
本书更多地强调了TONCAS这一要点，即“显然的必要条件也是充分的”书中明确指出，很多基本结果都可以用这种方式来理解这既为本课程提供了一个主题，也使得等价关系中简单的一面和复杂的一面之间的区别更加明朗
另外，第3章到第5章以及7.1节中强调较多的是极大、极小值问题间的对偶性在图论课程中，没有人想深入钻研线性最优化问题中对偶的本质，只需理解构成对偶对的两个最优化问题具有如下性质即可：极大值问题的任意可行解的值不超过极小值问题的任意可行解的值如果两个互为对偶问题具有相同取值的可行解，则由对偶性可知，这两个可行解都是最优的有关线性规划的讨论在8.1节中给出
其他的要点均属于证明技巧其一是用极端化方法来简化证明并避免使用归纳法其二就是用归纳法证明条件性命题，关于这一点在注记1325中有明确的说明
导出Kuratowski定理的过程有些长尽管如此，最好在一个学时内完成其证明为了节省时间，可以简单讨论将该问题归约到3连通情况的那些预备引理注意，用归纳法可以很自然地引出两个引理来证明3连通的情况此外，还要注意证明使用了5.2节中定义的S瓣这个概念
第6章的第1个学时不要就作图和区域等技术进行冗长的讨论最好将这些概念当作直观概念，除非有学生问起它们的细节正文中有这些概念的精确叙述
由于在后续内容中不再涉及，1.4节中得出有向图概念的应用例子被标记为选学内容但这些例子可以使读者更清晰地认识到模型(图或有向图)的选取是依赖于应用的
由于图论不强调数值计算而强调证明技巧和解释的清晰，因此是用来培养学生书面和口头表达能力的一门很好的课程除了布置一些书面作业并要求学生仔细书写其论述过程外，作者发现组织一些“讨论式学习”也是很有成效的，这时学生们讨论问题，教师则在教室里巡视、听学生的讨论并回答他们的问题记住，考察一个人是否真正理解了证明过程的最好方法就是让他给别人解释这个证明参与这种讨论的学生均受益匪浅
致谢
本书得益于许多大学在课堂教学中对其不断的改进按时间顺序排序，使用过这本教材的教师有：Ed Scheinerman(约翰斯·霍普金斯大学), Kathryn Fraughnaugh(科罗拉多大学丹佛分校), Paul Weichsel/Paul Schupp/Xiaoyun Lu(伊利诺伊大学), Dean Hoffman/Pete Johnson/Chris Rodger(厄本大学), Dan Ullman(乔治·华盛顿大学), Zevi Miller/Dan Pritikin(迈阿密大学俄亥俄分校), David Matula（南卫理公会大学）, Pavol Hell(西蒙·弗雷泽大学), Grzegorz Kubicki(路易斯维尔大学), Jeff Smith(普度大学), Ann Trenk(韦尔兹利学院), Ken Bogart(达特茅斯学院), Kirk Tolman(伯明翰扬大学), Roger Eggleton(伊利诺伊州立大学), Herb Kasube(布拉德雷大学), Jeff Dinitz(佛蒙特大学)其中很多人以及他们的学生都对本书提出了宝贵的修改意见
在此感谢Prentice Hall的George Lobell长期的帮助并找到本教材的审阅者.审阅者Paul Edelman、Renu Laskar、Gary MacGillivray、Joseph Neggers、Joseph Malkevitch、James Oxley、Sam Stueckle和Barry Tesman提出了宝贵的意见第8章的早期版本的审阅者包括Mike Albertson、Sanjoy Barvah、Dan Kleitman、James Oxley、Chris Rodger和Alan Tucker第2版的审阅者有Nate Dean、Dalibor Froncek、Renu Laskar、Michael Molloy、David Sumner和Daniel Ullman.
从第1版到第2版的很多修改意见来自读者这些修改包括从排版错误到简化证明、附加习题，这对本书的完成是非常重要的在此感谢他们对本书的评价和意见，包括：Troy Barcume, Stephan Brandt, Gerard Chang, Scott Clark, Dave Gunderson, Dean Hoffman, John D.Angelo, Charles Delzell, Thomas EmdenWeinert, Shimon Even, Fred Galvin, Alfio Giarlotta, Don Greenwell, Jing Huang, Garth Isaak, Steve Kilner, Alexandr Kostochka, Andr Kündgen, Peter Kwok, JeanMarc Lanlignel, Francois Margot, Alan Mehlenbacher, Joel Miller, Zevi Miller, Wendy Myrvold, Charles Parry, Robert Pratt, Dan Pritikin, Radhika Ramamurthi, Craig Rasmussen, Bruce Reznick, Jian Shen, Tom Shermer, Warren Shreve, Alexander Strehl, Tibor Szab, Vitaly Voloshin和C.Q.Zhang
特别感谢John Ganci对本书极其认真的阅读！
在第2版再版时，学生们发现了许多排版错误这些学生包括：Jaspreet Bagga, Brandon Bowersox, Mark Chabura, John Chuang, Greg Harfst, Shalene Melo, Charlie Pikscher和Josh Reed
第1版的封面（指英文原书）是由Ed Scheinerman使用美国军方Ballistic实验室的BRLCAD完成的第2版的封面是由Maria Muyot使用CorelDRAW完成的
Chris Hartman在为第1版参考文献的准备方面做了重要工作，新的参考文献现在已经被加入.Ted Harding帮助解决了第1版在排版方面的困难
本书第2版是使用TEX完成的TEX中的科学排版系统归功于Donald EKnuth书中的插图是使用gpic生成的，它是一种免费的软件
反馈
作者在这里欢迎大家对本书提出修改和建议，包括对本书主题的评论、结果的归属、更新、对习题的建议、排版错误、专业术语等请将您的宝贵信息发送至
west@math.uiuc.edu
如果在参考文献的引用上有所遗漏，在此表示特别的歉意，并请通知作者
作者建立了一个Web网站，包括课程提纲、勘误表、更新等辅助材料，欢迎您访问！
http://www.math.uiuc.edu/~west/igt
在印刷之前作者已将所知道的所有排版和数学错误更正完毕尽管如此，本书还难免会存在一些错误，请您帮助找到并通知作者，以便及时更正
Douglas B. West
伊利诺伊大学厄巴纳分校
