目  录

第 1 章 基本概念  1 

1.1  图的概念 1 

1.2  图的代数表示 8 

习题 1 13 

第 2 章  道路与回路  16 

2.1  图的连通性  16 

2.2  道路与回路的判定 22 

2.3  欧拉道路与回路 26 

2.4  哈密顿道路与回路 29 

2.5  旅行商问题  33 

2.6  最短路径 37 

2.7  关键路径 42 

2.8  中国邮路 46 

习题 2 50 

第 3 章  树 59 

3.1  树的有关定义 59 

3.2  基本关联矩阵及其性质 61 

3.3  支撑树的计数 63 

3.4  回路矩阵与割集矩阵  68 

3.5  Huffman 树  76 

3.6  最短树 78 

习题 3 82 

第 4 章  平面图与图的着色 88 

4.1  平面图 88 

4.2  极大平面图  89 

4.3  非平面图 91 

4.4  对偶图 93 

4.5  色数与色数多项式 98 

习题 4 103 

第 5 章  匹配 107 

5.1  二分图的最大匹配 107 

5.2  完全匹配 110 

5.3  最佳匹配及其算法 112 

习题 5 119 

第 6 章  网络流 122 

6.1  网络流图 122 

6.2  Ford-Fulkerson 最大流标号算法 125 

6.3  最大流的 Edmonds-Karp 算法 128 

6.4  最大流的 Dinic 算法 131 

6.5  最小费用流 134 

习题 6 137 

第 7 章  代数结构预备知识  139 

7.1  集合与映射  139 

7.2  等价关系 143 

7.3  代数系统的概念 146 

7.4  同构与同态 149 

习题 7 154 

第 8 章  群  156 

8.1 半群 156 

8.2  群、群的基本性质  161 

8.3  循环群和群的同构  167 

8.4  变换群和置换群 Cayley 定理  173 

8.5  陪集和群的陪集分解 Lagrange 定理 179 

8.6  正规子群与商群 184 

8.7  群的同态和同态基本定理 187 

8.8  群的直积 193 

8.9  环和域  195 

习题 8 199 

第 9 章  图论编程实验 203 

9.1  图的代数表示  203 

9.2  最短路径问题  203 

9.3  欧拉回路 204 

9.4  最优二叉树  205 

9.5  最短树 205 

9.6  二分图匹配  205 

9.7  网络流 206 

9.8  挑战实验：俄罗斯方块 206 

9.9  挑战实验：欧拉回路加强版  206 

9.10  挑战实验：游走问题  207 

参考文献  208