图算法PDF电子书下载

第一章 图和图的路算法 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