目  录

第 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