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

程龚，教授/博导，2006年和2010年于东南大学获学士和博士学位，随后进入南京大学工作，2017年入选江苏省“六大人才高峰”高层次人才计划，2022年入选国家级青年人才计划。主讲“图论与算法”、“计算机问题求解”等课程，2014年获国家级教学成果奖二等奖，2018年入选南京大学“我最喜爱的老师”。研究兴趣包括知识图谱、数据搜索、神经符号推理等。主持国家重点研发计划、国家自然科学基金等资助的多个项目课题。在TKDE、WWW、SIGIR、AAAI、IJCAI、ACL、ISWC等CCF-A/B类国际期刊会议上发表论文50余篇，获ISWC等国际会议最佳论文奖或提名6次，论文总引用3000余次。担任过ISWC短文程序委员会主席、CCKS程序委员会主席等职务，现任江苏省人工智能学会知识工程与智能服务专委会副主任。曾编著《语义网技术体系》，翻译《语义网基础教程》、《谷歌语义搜索》

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