《图算法》求取 ⇩

第一章图和图的路算法1

1.1 图的基本概念1

1.2 描述图的数据结构5

1.3 欧拉（Euler）图9

1.4 最短路算法13

1.5 所有顶点对间的最短路算法19

第二章树及其算法26

2.1 树26

2.2 连通图的生成树29

2.3 最小生成树算法36

第三章图的搜索技术42

3.1 无向图的深度优先搜索（DFS）42

3.2 不可分离分支算法49

3.3 有向图的深度优先搜索（DFS）56

3.4 强连通分支算法60

3.5 广度优先搜索（BFS）65

第四章有序树及赫夫曼优化问题68

4.1 唯一可译代码（UDC）68

4.2 定位树及赫夫曼（Huffmam）问题74

4.3 卡塔兰（Catalan）数86

第五章网络最大流问题92

5.1 福特（Ford）－富尔克逊（Fulkerson）算法92

5.2 戴尼克（Dinic）算法101

5.3 具有上界和下界的网络流109

第六章网络流技术的应用118

6.1 0/1网络流118

6.2 图的顶点连通性124

6.3 二分图的最大对集算法135

第七章可平面性及其判定算法139

7.1 图的曲面嵌入和欧拉公式139

7.2 可平面性判定算法146

7.3 对偶性153

第八章NP－完全性理论160

8.1 问题的可解性及有效算法160

8.2 判定问题的NP－类164

8.3 NP－完全性及库克（Cook）定理168

第九章图论中的NP－完全问题178

9.1 证明NP－完全性的技术178

9.2 团、独立集及顶点覆盖182

9.3 哈密顿（Hamilton）通路和回路184

9.4 图的着色问题189

9.5 有向图中反馈集合196

9.6 STEINER树198

9.7 网络最大割200

9.8 线性排序205

主要参考文献211