第 1章 图的基础知识 1
1．1 什么是图 1
1．2 图的表示法 6
1．3 其他图论术语 9
1．4 几类特殊的图 17
1．5 图的度序列 26
章末习题 31

第 2章 最小生成树 33
2．1 什么是最小生成树 33
2．2 克鲁斯卡尔算法 35
2．3 普里姆算法 39
2．4 最小斯坦纳树问题 41
章末习题 43

第3章 最短路径问题 45
3．1 什么是最短路径问题 45
3．2 迪杰斯特拉算法 46
章末习题 52

第4章 欧拉回路与哈密顿圈 53
4．1 定义 53
4．2 欧拉回路 56
4．3 哈密顿圈 59
章末习题 63

第5章 图着色 65
5．1 顶点着色 65
5．2 边着色 79
章末习题 84

第6章最大流问题 85
6．1 什么是最大流问题 85
6．2 福特- 富尔克森算法 89
6．3 最大流最小割定理 96
章末习题 99

第7章 匹配问题 101
7．1 什么是匹配 101
7．2 二部图中的匹配 104
7．3 匈牙利算法 108
7．4 用求解最大流问题的算法求解匹配问题 115
章末习题 118

第8章 章末习题解答 119

索引 131