程序员的数学4:图论入门

第 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