本书由实际问题展开，在介绍用图建立数学模型并阐述相关数学原理的基础上，进一步介绍用计算 

机解决相关问题的方法，包括经典算法的设计和基于数学原理的算法分析，使理论与算法融会贯通，并 

通过大量的思考题引导读者自己完成推导过程。 

本书共 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