《青少年国际和全国信息学 计算机 奥林匹克竞赛指导 图论的算法与程序设计》

第一章 基本概念1

1.1 引言1

1.2 图的定义2

1.3 道路与回路4

1.4 树6

第二章 求最短路径的算法及应用8

2.1 求最短路8

2.2 服务点设置问题1——求图的中心11

2.3 服务点设置问题2——求图的P中心14

2.4 服务点设置问题3——求图的中央点19

第三章 求最小生成树23

3.1 求无向图的最小生成树23

3.2 求有向图的最小树形图25

第四章 图的连通性31

4.1 连通性的基本概念和定义31

4.2 深度优先搜索（dfs）33

4.3 求割顶和块37

4.4 求极大强连通子图42

4.5 求最小点基46

4.6 可靠通讯网的构作51

第五章 支配集与独立集54

5.1 求支配集54

5.2 求独立集57

第六章 网络流及其应用62

6.1 求网络的最大流62

6.2 求容量有上下界的网络的最大流和最小流68

6.2.1 求容量有上下界的网络的最大流68

6.2.2 求容量有上下界的网络的最小流73

6.3 最小费用最大流问题76

6.4 求容量有上下界的网络的最小费用最小流和应用实例87

6.4.1 求容量有上下界的网络的最小费用最小流87

6.4.2 一个应用实例——餐厅问题93

6.5 求有供需约束的可行流98

6.6 求图的连通度102

6.7 求图的边连通度106

第七章 匹配问题111

7.1 匹配的基本概念111

7.2 求二分图的最大匹配115

7.3 求二分图的完备匹配118

7.4 求二分图的最佳匹配122

7.5 求任意图的最大匹配127

7.6 求最小边的覆盖133

第八章 着色问题138

8.1 求顶色数138

8.2 求边色数143

8.2.1 边色数143

8.2.2 边色数的一个实际应用146

第九章 可行遍性问题152

9.1 中国邮路问题152

9.2 货郎问题1157

9.3 货郎问题2162

9.4 工作的最佳排序问题165