图论与算法

本书介绍了图论中的连通、匹配/独立、覆盖、支配、染色、平面等数学问题及相关的数学概念和重要定理，继而介绍了对应的计算问题及相关的经典算法的设计与分析，并通过大量的思考题引导读者开展自我探索和深入思考。 （1）内容上，理论(数学)与算法(计算机)融会贯通：每章由实际问题开始，“理论”部分通过概念定理帮助读者建立实际问题背后的数学模型并掌握数学原理，然后“算法”部分通过算法设计与分析帮助读者掌握实际问题对应的算法问题的解法，理论与算法篇幅各半。 （2）形式上，帮助读者通过自我探索完成知识内化：正文部分几乎没有形式化的证明，而是通过思考题引导读者自己完成推导过程，对部分思考题在附录部分给出提示或答案，其初衷是尽可能推迟向读者呈现答案，为读者保留更多思考机会，而非从外部直接灌输知识。 本书特色：
（1）将实际问题建模为数学问题，进而解决其中的算法问题，使理论和算法融会贯通。
（2）将完整证明移至附录部分，正文通过思考题引导读者自己推导，有助于知识的内化。

本书由实际问题展开，在介绍用图建立数学模型并阐述相关数学原理的基础上，进一步介绍用计算 
机解决相关问题的方法，包括经典算法的设计和基于数学原理的算法分析，使理论与算法融会贯通，并 
通过大量的思考题引导读者自己完成推导过程。 
本书共 10 章：第 1 章介绍图的基本概念；第 2~4 章介绍图的连通性和遍历方法，包括基于圈的特 
殊遍历方法；第 5 章介绍匹配；第 6 章和第 7 章分别介绍赋权图和有向图，包括流网络；第 8 章介绍独 
立、覆盖和支配；第 9 章介绍边和顶点的染色；第 10 章介绍平面，包括面的染色。每节后均附有练习 
题，包括理论题和编程练习题。 
本书可作为高等学校计算机及相关专业本科生和研究生的教材。

第 1 章 图的基本概念.  1 
1.1 图的定义  2 
1.2 图的表示  4 
1.3 图的关系  7 
1.4 图的运算  9 
第 2 章 连通和遍历.  12 
2.1 连通和 DFS  13 
2.1.1 理论 13 
2.1.2 算法 14 
2.2 割点和割边.  17 
2.2.1 理论 17 
2.2.2 算法 19 
2.3 距离和 BFS  23 
2.3.1 理论 23 
2.3.2 算法 24 
第 3 章 圈和遍历.  30 
3.1 圈和树 .  31 
3.1.1 理论 31 
3.1.2 算法 33 
3.2 二分图 .  34 
3.2.1 理论 34 
3.2.2 算法 36 
3.3 欧拉图 .  38 
3.3.1 理论 38 
3.3.2 算法 39 
3.4 哈密尔顿图.  44 
3.4.1 理论 44 
3.4.2 算法 45 
第 4 章 连通度 .  46 
4.1 块 46 
4.1.1 理论 47 
4.1.2 算法 49 
4.2 割集和连通度 52 
4.2.1 理论 52 
4.2.2 算法 55 
第 5 章 匹配  57 
5.1 匹配和最大匹配  58 
5.1.1 理论 58 
5.1.2 算法 59 
5.2 完美匹配.  69 
第 6 章 赋权图 .  71 
6.1 赋权图和距离 72 
6.1.1 理论 72 
6.1.2 算法 73 
6.2 最小生成树.  76 
6.2.1 理论 76 
6.2.2 算法 77 
6.3 赋权欧拉图.  82 
6.3.1 理论 82 
6.3.2 算法 83 
6.4 赋权哈密尔顿图  85 
6.4.1 理论 86 
6.4.2 算法 86 
第 7 章 有向图 .  92 
7.1 有向图的定义 92 
7.2 有向图的表示 95 
7.3 有向图的连通 96 
7.3.1 理论 96 
7.3.2 算法 98 
7.4 有向图的距离 .  104 
7.4.1 理论 .  104 
7.4.2 算法 .  104 
7.5 流网络和最大流.  105 
7.5.1 理论 .  105 
7.5.2 算法 .  109 
第 8 章 独立、覆盖和支配. 114 
8.1 边的独立、覆盖和支配  115 
8.1.1 理论 .  115 
8.1.2 算法 .  118 
8.2 顶点的独立、覆盖和支配 121 
8.2.1 理论 .  122 
8.2.2 算法 .  126 
第 9 章 染色 . 132 
9.1 边的染色 133 
9.1.1 理论 .  133 
9.1.2 算法 .  135 
9.2 顶点的染色  145 
9.2.1 理论 .  145 
9.2.2 算法 .  146 
第 10 章 平面  . 150 
10.1 可平面图 .  150 
10.1.1 理论.  150 
10.1.2 算法.  154 
10.2 面的染色  . 158 
A 部分思考题提示  162 
B 部分思考题完整证明  166 
术语小结  209 
参考文献  214

动机与历程
2013 年，我开始承担南京大学计算机科学与技术系开设的“图论”课程的教学工作，这是面向本科生的专业选修课。此前的参考教材是多西（John Dossey）等的《离散数学》和迪斯特尔（Reinhard Diestel）的《图论》，备课期间我也翻阅了市面上的其他图论教材，发现其内容均以概念定义和定理证明等“理论”为主。这并不意外，因为图论被认为是数学的分支，关注与图有关的“数学问题”，“图论”课程在很多高校也由数学专业开设。对于计算机专业，这些理论内容有用，但不够用，因为图在计算机领域常作为一种理论工具被用于建模实际问题，继而研究解决相关的“算法问题”，而“算法”在传统的图论教材和图论课程教学内容中占比有限。因此，我认为有必要调整教学内容，使之更适合计算机及相关专业的教学。
为此，我重新挑选了教材，以高随祥的《图论与网络流理论》为主要教材，以韦斯特（Douglas B. West）的《图论导引》为参考教材，因为这两本教材包含相对较多的算法。在随后数年的教学中，我注意到由于这些并非专门的算法教材，其对算法设计与分析的讲解方式与计算机专业教材的风格有些不同，同时也缺少一些我认为较重要的算法。因此，在不断扩充讲义的同时，我开始酝酿编写一本更适合计算机专业教学的图论教材。
经过多年的内容积累和实践沉淀，2020 年，我主要利用寒暑假和工作日的夜间时间着手编写这本《图论与算法》。2022 年春季学期，我将课程更名为“图论与算法”，表明其与传统图论课程的区别，并试讲了初步编写完成的几个章节，也得到一些有益的反馈。2023 年1 月，计划编写的章节全部完成。2023 年春季学期，正式用于课程教学。

内容与形式
在内容上，如果只看目录的前两级，本书似乎与传统图论教材区别不大，涉及图的连通、匹配、染色、平面等经典主题。然而，如第三级目录所示，绝大部分主题由“理论”和“算法”两部分组成，每个主题通常从一两个实际问题开始，“理论”部分通过概念和定理为其建立数学模型并阐述相关数学原理，“算法”部分将其表述为交由计算机解决的算法问题，阐述算法设计并基于数学原理分析算法的正确性和效率，使两部分融会贯通。因此，本书是传统图论教材的纵向延伸，增加了大量经典易懂的算法，理论与算法各占一半篇幅。同时，为使总篇幅适合一个学期的教学，理论部分相比传统图论教材进行了删减，遴选了最核心或与算法最相关的内容，使教学可以更聚焦。希望以后有机会再编写一本进阶教材，阐述未选入本书的理论与算法，包括我本人团队的研究成果。
在形式上，本书的特点是正文部分几乎没有形式化的证明，而是通过思考题引导读者自己完成推导过程。对于有一定难度的思考题（用◇标记），附录部分给出了简略提示，启发读者思考。对于较重要的思考题（用?标记），例如重要定理的证明，附录部分给出了完整证明，供读者比对。该设计的初衷是尽可能推迟向读者展现答案，为读者保留更多的思考机会，让读者尽量通过自我探索完成知识的内化，而非从外部直接灌输。对这种学习方法不熟悉的读者可能担心对知识的掌握不够全面，但我认为多思考会比多阅读更有收获。

读者的范围
本书在内容和形式上的特点，决定了其主要适用于如下范围的读者。首先，理论与算法相结合的内容组织，使本书更适合计算机及相关专业的人员阅读。其次，以思考题引导为主的讲解形式，使本书更适合作为初学者使用的课堂教材或自学教材。总之，本书主要适合作为高等学校计算机及相关专业的课程教材。
在阐述算法的设计与分析时，读者被假定为熟悉基本的数据结构（如队列和栈）和算法分析方法（如正确性证明和时间复杂度分析），这些知识也可通过互联网等渠道快速学习。

课程与课件
本书适合一个学期约16 周、每周1 次课、每次课2_3 课时的本科生或研究生课程教学，以下是建议的教学周历。
首先，可以安排约10 次课进行课堂讲授，每次课讲1 章，考虑到学生在选修这门课程之前通常已修完“离散数学”和“数据结构”等前导课程，因此，部分内容在讲解时可以压缩。课堂讲授的形式建议采用引导式，以书中的思考题引导学生思考和发言。课后布置书面作业可采用各节末尾的理论练习题，这些练习被设计为实际问题，帮助学生强化用图建模并解决实际问题的能力；也可将部分思考题作为作业。
同时，可以安排4_5 次课开展编程训练，大约每两次课堂讲授课之后安排一次上机编程课，可采用各节末尾的编程练习题，帮助学生巩固对算法细节的理解并提升编程技能。
此外，可以安排1 次课开展论文研讨，遴选几篇与课程内容相关的经典论文，例如本书未详细介绍的算法，作为教学内容的深化，提前1_2 周布置给学生阅读，并要求学生制作课件，在课堂上相互研讨论文内容，帮助学生提高文献阅读和讲解的能力。

致谢与致歉
本书的顺利完成离不开很多人的支持和帮助，以下致谢难免遗漏，若未提及，还望海涵。
感谢我的家人，特别是我的妻子和女儿，她们本可享有来自我的更多陪伴，这本书献给她们，希望可以成为她们的骄傲。
感谢东南大学对我的培养。感谢南京大学营造的宽松的工作氛围，让我可以没有顾虑地投入时间完成本书的编写。
感谢我所在南京大学计算机科学与技术系的多位领导和同事。瞿裕忠教授是我学习图论、开展图算法相关研究和图论课程教学的引路人。陶先平教授、仲盛教授、赵建华教授先后在分管系本科教学工作期间对我开展教学改革的尝试给予了充分的支持和悉心的指导。陈道蓄教授对“计算机问题求解”课程教学内容和方法的诸多创新实践让我受益匪浅。周志华教授在百忙之中编写完成了广受好评的《机器学习》为我树立了榜样。陆桑璐教授的不断鼓励是我完成本书的重要推动力。
感谢曾选修我的课程的所有同学们，他们在课堂和课后主动思考并积极参与讨论的热情感染了我，这本书是我对这种热情的回馈。
感谢清华大学出版社，感谢卢先和副社长、张瑞庆编审和常建丽编辑，本书得以顺利出版，离不开他们的大力支持和悉心帮助。
本书中的每句话、每条公式、每张图表都由我本人完成，水平有限，难免有误，责任全在我一人，先行致歉，请读者见谅。

程龚
2023 年4 月于南京