图论导引(原书第2版典藏版)/华章数学译丛

译者序
1736年，瑞士数学家LEuler(欧拉)在他的一篇论文中讨论了哥尼斯堡(Knigsberg)七桥问题，由此诞生了一个全新的数学分支——图论(Graph Theory)在经历了200多年的发展之后，图论已经积累了大量的理论和结果，其应用领域也逐步扩大初，图论主要用来讨论游戏中遇到的问题；19世纪末期，图论已经用来研究电网络方程组和有机化学中的分子结构；20世纪中叶以后，借助于计算机，图论又用来求解生产管理、军事、交通运输、计算机以及通信网络等领域中的许多离散性问题，同时图论中的一些著名问题也借助于计算机得到了证明如今，图论本身及其在物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学和管理科学等领域中的应用越来越受到人们的重视因此，作为理工科相关专业的学生，全面系统地学习图论中的概念、基本定理和算法并了解图论中的一些悬而未决的问题是十分必要的.
本书是一部优秀的图论教科书，由Douglas BWest教授所著，目前已经是第2版了Douglas BWest教授是伊利诺伊大学数学系的资深教授，长期从事图论理论和组合优化方面的研究工作，发表了100多篇论文.
本书旨在介绍图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧另外，本书包含很多图论的新研究结果，并介绍了一些悬而未决的图论问题证明与应用并举是本书的一个重要特点图论中的许多问题都有多个证明，作者对这些证明进行了精心选择，深入浅出地介绍了图论的证明技巧；本书还设计了大量习题，总量超过1 200道，通过这些习题，读者可以深刻理解图论的基本概念和证明技巧，并能够补充正文未包括的知识.
本书可以作为高等院校数学系本科生和研究生、计算机专业和其他专业研究生的图论课程教材，也可以作为有关教师和工程技术人员的参考书.
限于译者水平，译文中难免存在疏漏和错误，望广大读者批评指正

前言
图论是训练离散数学证明技巧的乐园，其结果在计算科学、社会科学和自然科学等多个领域具有广泛应用本书可作为本科生或低年级研究生1~2个学期的图论课程的教材本书不要求任何图论的预备知识尽管本书包含许多算法和应用，但重点是理解图的结构和解决图论问题的技巧。
目前已经有许多图论的教科书由J. A. Bondy和U. S. R. Murty撰写的优秀教材《Graph Theory with Applications》(Macmillan/NorthHolland［1976］)把重点放在证明和应用两个方面，本书的草稿参照了该书图论至今仍是一门年轻的学科，应该如何介绍图论的题材，大家仍然没有一致的看法主题的挑选和顺序的安排，证明方法、目标和基本题目的选择等，一直是众说纷纭作者在多次修改本书的过程中认识到，对于这些问题做决定是很困难的本书是作者对这些争议的一点贡献
第2版
第2版的修订主要是为了更易于学生学习和更便于教师教学本书的总体内容没有很大的变化，但是对内容的表述方式做了修改，使其更容易理解，这一点在本书的前几部分尤其明显有关第2版所做的某些修改，稍后将详细讨论，此处仅做一下概述
 非选学节中的选学材料现在用*号标明这些内容不会在后续内容中使用，因而可以跳过多数选修内容忽略以后，本书可以作为一学期的图论教学内容如某一小节标记为“选学”，则整个小节的内容都是可选修的，而不再标记该小节中的各个项
 对于缺乏基础知识的学生，附录A概述了有关集合、逻辑、归纳法、计数、二项式系数、关系和鸽巢原理等方面的相关知识
 对于很多证明都重新进行了更细致的叙述，并增加了更多的例子
 增加了350多道习题，其中多数是第1～7章中的比较容易的题目这样，本书的总习题量超过了1 200道
 增加了100多幅插图本书的插图总量超过了400幅为区别插图中包括的几种类型的边，书中把原有的实线和虚线改变为粗线和实线，增加了插图的清晰度
 相对简单的问题都集中放在各节习题的前面部分，用来作为热身练习一些习题进行了改写，使其语义更加清楚
 对习题的提示做了补充，增加了一个“部分习题的提示”的附录
 为了易于查找，概念术语都用黑体字给出，其中绝大多数都出现在概念定义中
 为了易于查找，将术语集中在附录D中
 有关欧拉回路、有向图和Turn定理的内容经过了重新编排，以提高学习效率
 第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章同时包含了这两部分内容很多习题包含这些概念计算距离的算法也会产生或用到树
很多图论专家认为KnigEgervry 定理需要一个与网络流无关的独立证明学生在区分“k连通”和“连通度k”时感到困难，而且“k可染色”和“色数k”也有同样的问题因此，书中首先介绍匹配，然后用匹配证明Menger定理匹配和连通性都在着色问题中有所应用
为了满足众多读者的要求，本书在3.1节结尾增加了一个可选小节，介绍支配集作者通过强调顶点覆盖而不是增广路径，并使用很多较好的例子，使得加权二部匹配的概念更加清晰易懂
在第1版中，Turn定理仅使用了顶点度和归纳的基本思想，因此这部分内容在第1章给出这样的安排使学生感到Turn定理太抽象，难以理解为此，考虑到与着色相关的极值问题，本书在1.3节仅保留了简单三角自由的情况(芒泰尔定理)，而将完整的Turn定理移至52节
关于平面性的章节现在移至“边和环”的前面当课时不足时，平面性应优先讲授，因为它比边着色和哈密顿环更重要与平面性相关问题的可视性较强，易于被学生接受，而且许多学生在这之前已经遇到过这些问题相对于本书前面的材料来说，平面图的一些想法似乎比证明边着色问题和哈密顿环问题使用的方法更易于接受和理解
先讨论平面性问题将会使第7章的内容更加条理清晰新的编排将会使平面性、边着色、哈密顿环等问题之间关系的讨论更全面，并自然引出超出四色定理的可选新内容
当学生们发现着色和哈密顿环问题缺乏好的算法时，很多人开始关心问题的NP完全性附录B满足了这些读者的好奇心使用形式语言来叙述NP完全性问题会使问题更抽象，因此很多学生更喜欢用图论的术语来描述NP完全问题NP完全性的证明也说明了“图变换”的多样性和有用性
本书探讨了基本结果之间的关系2-因子Petersen定理使用了欧拉回路和二部匹配；Menger定理和流小割定理的等价关系比第1版有更深入的探讨；“棒球淘汰问题”（Baseball Elimination）的应用被论述得更加详尽；k-色-临界图的k-1-连通性(第5章)用到了二部匹配；5.3节对完美图做了简要的介绍，着重强调了弦图与其他书相比，本书不仅包括了Vizing定理的算法证明，还包括了使用Thomassen方法对Kuratowski定理的证明
本书的前七章还有很多其他的增加和改进第6章末尾对Heawood公式和RobertsonSeymour定理进行了简要的讨论7.1节增加了关于边色数的Shannon界的证明5.3节给出了一个有关单纯顶点的更强的结论，这使得对弦图的特征刻画变得更简单明了在63节，删掉了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节的稳定匹配等内容作者也讲授33节有关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节，讲授到SzekeresWilf定理；5.2节，Mycielski构造和Turn定理；5.3节，讲授到着色递归，加上弦图的完美性；6.1节，K5和K3,3 的非平面性、对偶图的例子以及欧拉公式及其应用；6.2节，Kuratowski定理和Tutte定理的叙述和例子；6.3节，五色定理和交叉数的思想；7.1节，讲授到Vizing定理；7.2节，讲授到Ore条件和Chvtal-Erds条件；7.3节，Tait定理和Grinberg定理
教学方法的进一步说明
在这一版中，作者强调可以自然地从相关材料中得到的那些结果，讲课时强调这些内容有助于内容的融会贯通
本书更多地强调了TONCAS这一要点，即“显然的必要条件也是充分的”书中明确指出，很多基本结果都可以用这种方式来理解这既为本课程提供了一个主题，也使得等价关系中简单的一面和复杂的一面之间的区别更加明朗
另外，第3章到第5章以及7.1节中强调较多的是极大、极小值问题间的对偶性在图论课程中，没有人想深入钻研线性化问题中对偶的本质，只需理解构成对偶对的两个化问题具有如下性质即可：极大值问题的任意可行解的值不超过极小值问题的任意可行解的值如果两个互为对偶问题具有相同取值的可行解，则由对偶性可知，这两个可行解都是的有关线性规划的讨论在8.1节中给出
其他的要点均属于证明技巧其一是用化方法来简化证明并避免使用归纳法其二就是用归纳法证明条件性命题，关于这一点在注记1325中有明确的说明
导出Kuratowski定理的过程有些长尽管如此，好在一个学时内完成其证明为了节省时间，可以简单讨论将该问题归约到3连通情况的那些预备引理注意，用归纳法可以很自然地引出两个引理来证明3连通的情况此外，还要注意证明使用了5.2节中定义的S瓣这个概念
第6章的第1个学时不要就作图和区域等技术进行冗长的讨论好将这些概念当作直观概念，除非有学生问起它们的细节正文中有这些概念的精确叙述
由于在后续内容中不再涉及，1.4节中得出有向图概念的应用例子被标记为选学内容但这些例子可以使读者更清晰地认识到模型(图或有向图)的选取是依赖于应用的
由于图论不强调数值计算而强调证明技巧和解释的清晰，因此是用来培养学生书面和口头表达能力的一门很好的课程除了布置一些书面作业并要求学生仔细书写其论述过程外，作者发现组织一些“讨论式学习”也是很有成效的，这时学生们讨论问题，教师则在教室里巡视、听学生的讨论并回答他们的问题记住，考察一个人是否真正理解了证明过程的好方法就是让他给别人解释这个证明参与这种讨论的学生均受益匪浅
致谢

Douglas B. West
伊利诺伊大学厄巴纳分校

本书全面介绍了图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧. 另外，书中包含很多图论的新研究成果，并介绍了一些悬而未决的图论问题. 证明与应用并举是本书的一个重要特点，书中对所有定理和命题给出了完整的证明，同时讨论了大量的实例和应用，并提供了1 200多道习题. 
本书可以作为高等院校数学系本科生和研究生、计算机专业和其他专业研究生的图论课程教材，也可以作为有关教师和工程技术人员的参考书. 

道格拉斯•B. 韦斯特（Douglas B. West） 美国伊利诺伊大学厄巴纳分校数学系教授。1978年他于马萨诸塞理工学院获得数学专业博士学位。他的研究方向为离散数学中的极值问题、结构问题以及算法问题。除本书外，他还著有《Mathematical Thinking：Problem-Solving and Proofs》《Combinatorial Mathematics》和《The Art of Combinatorics》等书。

译者序
前言
符号表
第1章基本概念
1.1什么是图
定义
图模型
矩阵和同构
分解和特殊图
习题
1.2路径、环和迹
图的连通性
二部图
欧拉回路
习题
1.3顶点度和计数
计数和双射
极值问题
图序列
习题
1.4有向图
定义和例子
顶点度
欧拉有向图
定向和竞赛图
习题
第2章树和距离
2.1基本性质
树的性质
树和图中的距离
不相交生成树（选学）
习题
2.2生成树和枚举
树的枚举
图的生成树
分解和优美标记
分叉和欧拉有向图（选学）
习题
2.3化和树
小生成树
短路径
计算机科学中的树(选学)
习题
第3章匹配和因子
3.1匹配和覆盖
匹配
Hall匹配条件
小定理
独立集和覆盖
支配集（选学）
习题
3.2算法和应用
二部匹配
加权二部匹配
稳定匹配（选学）
快速二部匹配（选学）
习题
3.3一般图中的匹配
Tutte 1-因子定理
图的f-因子（选学）
Edmonds开花算法(选学)
习题
第4章连通度和路径
4.1割和连通度
连通度
边连通度
块
习题
4.2k-连通图
2-连通图
有向图的连通度
k-连通图和k-边连通图
Menger定理的应用
习题
4.3网络流问题
网络流
整数流
供应和需求(选学)
习题
第5章图的着色
5.1顶点着色和上界
定义和实例
上界
Brooks定理
习题
5.2k-色图的结构
大色数图
极值问题和Turn定理
颜色-临界图
强制细分
习题
5.3计数方面的问题
真着色的计数
弦图
完美图点滴
无环定向的计数(选学)
习题
第6章可平面图
6.1嵌入和欧拉公式
平面作图
对偶图
欧拉公式
习题
6.2可平面图的特征
Kuratowski定理的预备知识
凸嵌入
可平面性测试(选学)
习题
6.3可平面性的参数
可平面图的