《网论-网络流》求取 ⇩

目录3

前言3

第一章图和网络3

1.1 抽象图的基本定义3

1.2 图的运算12

1.3 不可分图和二分图16

1.4 平面图19

1.5 对偶图36

1.6 2-同构49

1.7 图的矩阵52

1.7.1 关联矩阵53

1.7.2 回路矩阵57

1.7.3 割矩阵62

1.7.4 矩阵A、Bf和Qf间的关系68

1.7.5 节点-参考点路径矩阵70

1.8 有向图72

1.8.1 有向图的矩阵78

1.8.2 各矩阵间的相互关系86

1.8.3 一些重要的有向图88

1.9 平面图或有向图的回路矩阵90

1.10 小结及推荐读物92

参考文献94

第二章 最短有向路径问题96

2.1 最短有向路径97

2.2 最短有向路径的算法100

2.2.1 狄克斯拉（Dijkstra）算法100

2.2.2 福特-莫尔-贝尔曼（Ford-Moore-Bellman）算法110

2.2.3 叶（Yen）算法119

2.2.4 福特-福克森（Ford-Fulkerson）算法127

2.3 多端最短有向路径138

2.3.1 矩阵算法138

2.3.2 佛洛特-沃歇尔（Floyd-Warshall）算法145

2.4 用分解法计算最短有向路径152

2.5 小结及推荐读物160

参考文献162

第三章 最大网络流167

3.1 流167

3.2 s-t割170

3.3 最大流177

3.4 福特-福克森（Ford-Fulkerson）算法184

3.4.1 整数定理192

3.4.2 无理弧容量193

3.5 分层网198

3.6 阻塞流算法206

3.7.1 艾特蒙斯-卡普（Edmonds-Karp）算法217

3.7 福特-福克森（Ford-Fulkerson）的衍生算法217

3.7.2 狄尼克（Dinic）算法220

3.7.3 其它的衍生算法224

3.8 卡萨诺夫（Karzanov）算法225

3.9 无向网和混合网中的流232

3.10 对节点-弧限定容量的网中的流234

3.11 小结及推荐读物237

参考文献240

第四章 最小树与通信网243

4.1 森林、子树和树244

4.2 最小树和最大树249

4.3 最小和最大树算法255

4.3.1 波留夫卡（Boruvka）算法257

4.3.2 克鲁斯科（Kruskal）算法262

4.3.3 普林姆（Prim）算法265

4.3.4 小结270

4.4 端子容量矩阵270

4.5 流等价树的合成280

4.5.1 戈莫里-胡（Gomory-Hu）算法284

4.5.2 戈莫里-胡（Gomory-Hu）算法的证明296

4.6 最优通信网的综合298

4.6.1 戈莫里-胡（Gomory-Hu ）方法303

4.6.2 支配流实现308

4.7 定向通信网313

4.8 小结及推荐读物320

参考文献322

第五章 可行性定理及其应用325

5.1 供求定理325

5.2 一个扩展的供求定理342

5.3 环流定理352

5.4 可行环流算法365

5.5 对弧规定下界的网流375

5.6 对节点与弧限定容量的网的可行流381

5.7 小结及推荐读物392

参考文献394

第六章 网络流定理在子图问题中的应用395

6.1 有向图的子图问题395

6.2 有向图序列422

6.3 图的子图问题442

6.4 图序列450

6.5 （p，s）-矩阵458

6.6 1-矩阵和（1，0）-矩阵的实现473

6.7 最小变换478

6.8 小结及推荐读物490

参考文献492