本书由实际问题展开，在介绍用图建立数学模型并阐述相关数学原理的基础上，进一步介绍用计算 机解决相关问题的方法，包括经典算法的设计和基于数学原理的算法分析，使理论与算法融会贯通，并 通过大量的思考题引导读者自己完成推导过程。 本书共 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