《网络算法与复杂性理论》求取 ⇩

第一章 图与算法1

§1．1 图的基本概念1

§1．2 有向图的基本概念5

§1．3 图的矩阵表示8

§1．4 几类重要的图10

§1．5 网络最优化问题13

§1．6 算法及其复杂性19

习题一22

§2．1 树的基本性质23

第二章 最小树23

§2．2 最小树的基本性质29

§2．3 求最小树的算法31

§2．4 最小度限制树41

§2．5 支撑树的排序47

§2．6 过指定顶点的最小单圈子图50

习题二53

第三章 最小树形图56

§3．1 有根图及其基本性质56

§3．2 树形图及其基本性质59

§3．3 最小树形图63

§3．4 最大分枝69

习题三72

第四章 网络最优化与线性规划74

§4．1 线性规划74

§4．2 线性规划的对偶规划77

§4．3 全单位模矩阵79

§4．4 图的关联矩阵的一些性质84

§4．5 网络最优化问题的线性规划模型89

习题四96

第五章 最短路98

§5．1 引言98

§5．2 最短路方程100

§5．3 无回路网络的最短路算法106

§5．4 求非负权网络中最短路的Dijkstra算法110

§5．5 解最短路问题的Ford算法114

§5．6 求所有顶点对之间最短路的Floyd算法118

§5．7 负回路的检测方法123

§5．8 第二最短路130

§5．9 最短路算法的应用134

习题五138

第六章 最大流140

§6．1 流与截140

§6．2 Ford—Fulkerson算法144

§6．3 增量网络与分层增量网络147

§6．4 Dinic算法151

§6．5 循环流155

§6．6 带发点和收点的双容量网络165

习题六168

第七章 最小费用流171

§7．1 求最小费用流的负回路算法171

§7．2 求最小费用流的最小费用路算法177

§7．3 求最小费用流的原始—对偶算法184

§7．4 求最小费用循环流的状态算法190

习题七200

第八章 二部图的匹配202

§8．1 图的匹配202

§8．2 求二部图中最大匹配的算法206

§8．3 赋权二部图的最大权匹配209

§8．4 最大最小匹配214

习题八220

第九章 一般图的匹配222

§9．1 种上树222

§9．2 求最大匹配的花算法226

§9．3 求最大权匹配的Edmonds-Johnson算法232

习题九244

第十章 中国邮递员问题246

§10．1 Euler闭迹246

§10．2 有向Euler闭迹249

§10．3 赋权图上的邮递员问题250

§10．4 赋权有向图上的邮递员问题255

习题十264

第十一章 NP完全理论267

§11．1 最优化问题的判定形式267

§11．2 P类与NP类268

§11．3 NP完全类与Cook定理276

§11．4 六个基本的NP完全问题282

§11．5 NP完全性证明技术301

§11．6 更多的NP完全问题310

§11．7 NP难题322

习题十一324

第十二章 近似算法326

§12．1 近似算法的性能326

§12．2 旅行售货员问题的近似算法332

§12．3 背包问题与近似方法353

§12．4 一些否定结果357

习题十二362