前    言

动机与历程

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 月于南京