---------------------------概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）---------------------------
第2版前言
本书的初版已经过了10年，随着大数据分析、机器学习和数据挖掘的重要性越来越突出，概率方法对于计算机科学来说也变得越来越核心．许多相关领域的应用成果，其算法和思路都是建立在对概率与统计的成熟理解基础之上的，要想正确地使用这些工具，对于这些数学概念的透彻理解是必不可少的．而第2版新增的主要内容就是着重于这些概念的介绍．
近年来，诸如万维网、社交网络、基因数据等使得我们能够产生、收集和存储大量的样本数据集，这对我们建立模型和分析这些数据的结构提出了新的挑战．熟练掌握一些标准的分布可以给建立和分析模型打下一个好的基础，新增的第9章包含了绝大多数常见的统计分布，同时也像之前一样，会强调这些分布在计算机科学中如何应用，比如确定分布的尾界等．然而，诸如万维网和社交网络等现代数据集有着一个奇妙的现象，在其中我们往往见不到正态分布，取而代之的是一种有着非常不同性质的、很少见的、特征明显的重尾分布．例如，在万维网中，一些页面经常会有大量的网页链接它们，其被链接的数量要高过平均水平一个数量级．第2版新增的第16章将包含对于建模和理解这种现代数据集来说非常重要的那些特殊分布．
机器学习是近年来计算机科学领域的重大成果之一，它提供了许多高效的工具来建模、理解和预测大数据．但是预测的准确性，特别是准确性和样本容量的关系这一点却常常被人忽略．第2版中新增的第14章将会对这些重要的内容进行详细的介绍．
在新版中，我们也对之前的部分内容进行了充实和更新．例如，我们介绍了重要的洛瓦兹局部引理的算法变化的一些新进展，也新增了一小节用来介绍布谷鸟散列这种享誉盛名且越来越实用的散列法．最后，除了这些新增内容，新版也包括了修正、勘误和许多新习题．
我们对几年来向我们发送了诸多勘误的读者表示由衷的感谢，可惜人数过于众多，我们在此不一一列出了，还望海涵．
第1版前言
为什么要研究随机性
计算机科学家为什么要研究和使用随机性呢?这是因为计算机出现了太多不可预见的状况!加入随机性似乎是一个缺点,它使得有效地使用计算机这种已经具有挑战性的工作变得更加复杂．
从20世纪开始,科学研究已经将随机性视为建模和分析中的基本组成部分．例如,在物理学上,牛顿定律使人们相信宇宙的位置是确定的:如果有一个足够大的计算工具和合适的初始条件,人们可以确定若干年后行星的位置．然而量子理论的发展却提出了不同的观点:宇宙仍旧按照自然法则运转,但是这些自然法则的核心是随机性的．“上帝不会同宇宙玩骰子”，这是爱因斯坦用来反驳现代量子力学的一句名言．然而,当代亚微粒子物理学的主要理论仍然是建立在随机现象和统计规律基础之上的,并且在从生物学的遗传与进化到自由市场经济的价格波动模型等几乎所有其他科学领域中,随机性都起着非常重要的作用．
计算机科学也不例外，从一些概率定理证明的高深理论到个人计算机以太网卡的实用性设计,随机性和概率方法在现代计算机科学中都扮演了关键角色．过去20年以来,概率论在计算中的应用得到了巨大的发展,越来越高级、越来越复杂的概率技术已经被应用于更加广泛和更富挑战性的计算机科学应用中．在本书中,我们主要研究随机性应用于计算机科学的基本方法:随机化算法和算法的概率分析．
随机化算法:随机化算法是执行过程中要求作随机选择的算法．实际上,随机化程序会使用由随机数发生器产生的数值,从若干执行分支中决定下一步执行哪个分支．例如,以太网卡协议用随机数决定何时试图访问共享的以太网通信介质．随机性在打破对称性、防止不同的以太网卡同时重复访问介质方面是非常有用的．随机化算法的其他常见应用还包括蒙特卡罗模拟和密码学中的初始检验．在这些以及其他重要应用中,随机化算法比最有名的确定性方法更有效,并且在大多数情况下更简单,更容易编写程序．
当然，这些优点也是需要付出一定代价的,问题的答案在一定的概率下是不正确的,或者只以某个概率保证有效．虽然设计一个有可能错误的算法似乎有点奇怪,但是如果错误发生的概率很小,那么提高运行速度和减少占用的内存是有价值的．
算法的概率分析:复杂性理论根据计算的复杂性对问题进行分类,尤其是区分简单问题和有难度的问题．例如,复杂性理论认为流动推销员问题是一个NP难题．如果城市数量以次指数增长,那么不可能存在可以解决流动推销员问题的任何一个实用的算法．对于经典的最坏情况复杂性理论,一个令人困惑的现象是,在分类上属于有难度的计算问题,实际上却很容易解决，概率分析对这种现象给出了理论上的解释．虽然对某些不合理的输入数据,问题难以解决,但对大多数输入(尤其是在日常的应用中),这些问题实际上却容易解决．更确切地说,如果我们认为输入是随机选择的结果,而随机选择是根据所有可能输入数据集上的某个概率分布作出的,就很有可能得到一个易于解答的问题实例,而这些实例不能求解的概率是相对较小的．算法的概率分析是研究当输入来自某一适当定义的概率空间时算法如何运行的一种方法．书中我们将会看到,即使是NP难题,也会有对于几乎所有输入都极其有效的算法．
. 关于本书
本书可以作为计算机科学和应用数学专业高年级本科生或低年级研究生一至两个学期的课程教材．在众多较好的大学中,随机化和概率技术已经从高年级研究生讨论班的主题变为高年级本科生和低年级研究生的正式课程．在这方面有大量相当高深的、研究性的著作,但仍然需要一本介绍性的教科书,我们希望本书能起到这方面的作用．
本书的内容是从近几年在布朗大学(CS 155)和哈佛大学(CS 223)讲授计算机科学中的概率方法这类课程发展而来的．这些课程和本书强调的是概率技术以及具体的范例,而非特定的应用领域．每章介绍一种方法或者技术,通过一些随机化算法分析或基于随机输入算法的概率分析例子来阐述．其中许多例子来自网络中的问题,反映了网络领域的主要趋势(和作者的兴趣)．
本书第1版共有14章,可分成两部分,第一部分(第1～7章)是核心内容．本书只要求读者具备基本的概率论知识,相当于计算机科学专业的离散数学课程包含的内容．第1～3章复习初等概率论,并介绍一些有意义的应用,内容包括随机抽样、期望、马尔可夫不等式、方差和切比雪夫不等式．如果教学班有充分的概率论背景,那么这几章可以很快地讲过去,但是建议读者不要跳过这些章节,因为这里介绍了随机化算法和算法的概率分析概念,并且还有一些贯穿全书的例子．
第4～7章介绍高级课题,包括切尔诺夫界、球和箱子模型、概率方法和马尔可夫链．同前面几章相比,这几章介绍的内容更具有挑战性．难度特别大的章节书中标有星号(教师可以根据需要考虑是否跳过这部分内容)．根据教学进度,前7章介绍的核心内容可以作为四分之一学年或半学年的课程．
本书第二部分(第8章、第10～13章、第15章、第17章)介绍另外一些高级内容,这些内容既可以作为基本课程的必要补充,也可以作为另一门更高级的课程．这些章节是各自独立的,教师可以选择最适合学生的内容来讲授．将连续概率和熵这两章纳入基本课程中可能是比较好的选择．对连续概率(第8章)的介绍主要集中在均匀分布和指数分布,其中还包括一些排队论的例子,对熵(第10章)的介绍包括如何度量随机性,以及在随机提取、压缩和编码中，熵是如何自然地产生的．
第11章和第12章分别介绍了蒙特卡罗方法和耦合,这两章是密切相关的,最好放在一起学习；第13章是关于鞅的知识,包含了如何处理相关随机变量的各种重要问题；而第15章则从不同的思路继续研究两两独立和消去随机性的进展；最后一章(第17章)讨论了均衡配置问题,介绍了作者的一些想法,该章与第5章的球和箱子问题密切相关．
本书各个章节的顺序,尤其是第一部分的顺序,是根据它们在算法中的相对重要性安排的,例如,我们先介绍切尔诺夫界,而其他一些基本的概率知识(如马尔可夫链)则放在后面,但是,教师在讲授时可以按照不同顺序进行．在更强调一般随机过程的课程中,可以在第1～3章后直接讲授马尔可夫链(第7章),随后讲授球、箱子和随机图(第5章,略去哈密顿圈的例子），接下来可以跳过第6章关于概率方法的内容,而讲授连续概率和泊松过程(第8章)．本书其余大部分内容都会用到第4章中关于切尔诺夫界的知识．
书中的大部分练习都是理论性的,但我们也选取了一些编程练习——包括两个需要编程的探索性作业．我们发现偶尔的编程练习,对于加强本书的思想和增添课程的多样性很有帮助．
我们将本书的内容严格限制在数学分析的方法和技术之内,除去一些特殊情况,本书的所有定理都给出了完整的证明．显然,许多相当有用的概率方法并不在这种严格的限制之内．例如,在蒙特卡罗方法的重要领域中,大多数实际解具有启发性,从而证实了试验估计比严格数学分析更有效．我们认为,为了很好地应用和理解启发性方法的优缺点,扎实地掌握基础概率理论和本书给出的严格技术是十分必要的,我们希望读者在学完本书之后能够喜欢这种处理方式．
致谢
首先我们要感谢许多曾经研究本书选取的极好题材的概率论专家和计算机科学家．我们没有把大量原始论文作为参考文献放入书中,只是提供一些优秀的参考书目作为本书各章的背景材料和更进一步的讨论依据．
书中许多内容来自布朗大学CS 155课程和哈佛大学CS 223课程的学生和老师的建议和反馈,我们特别要感谢Aris Anagnostopoulos、Eden Hochbaum、Rob Hunter和Adam Kirsch,他们阅读了本书的初稿,并提出了修改意见．
我们尤其要感谢Dick Karp,2003年秋季,他在伯克利大学授课(CS 174)期间,使用了本教材的初稿,他的早期建议和修改意见对改进教材是非常有价值的．Peter Bartlett在2004年春季于伯克利大学授课(CS 174)期间,也提出了很多有用的建议和修改意见．
感谢在本书编写过程中认真读过部分初稿的同事,他们在内容及表达方面指出许多错误,提出重要的改进意见．他们是:Artur Czumaj、Alan Frieze、Claire Kenyon、Joe Marks、Salil Vadhan、Eric Vigoda．另外,感谢为出版社审稿的一些不知道姓名的评审者．
感谢Rajeev Motwani和Prabhakar Raghavan同意我们引用他们优秀的著作《Randomized Algorithms》中的某些练习．
最后感谢剑桥大学出版社的Lauren Cowles,她在本书的准备和组织过程中提供了很多编辑方面的帮助和意见．
本书的写作得到了美国国家科学基金会信息技术研究基金(授权号CCR-0121154)的部分资助．
---------------------------图论导引（原书第2版）典藏版---------------------------
图论是训练离散数学证明技巧的乐园，其结果在计算科学、社会科学和自然科学等多个领域具有广泛应用本书可作为本科生或低年级研究生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
伊利诺伊大学厄巴纳分校
![[套装书]概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）+图论导引（原书第2版）典藏版（2册）](http://images.china-pub.com/ebook8065001-8070000/8067361/zcover.jpg)
