有向图的理论、算法及其应用【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

有向图的理论、算法及其应用PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 基本术语及结论1

1.1 集合、子集、矩阵和向量1

1.2 有向图、有向子图、邻集和度数2

1.3 有向图的同构及其基本运算6

1.4 途径、迹、路、圈和路圈有向子图10

1.5 强连通性和单侧连通性15

1.6 无向图、双定向和定向性17

1.7 混合图和超图21

1.8 有向图和无向图的分类23

1.9 算法简介26

1.9.1 算法及其复杂性26

1.9.2 NP完全问题和NP困难问题30

1.10 应用：求解2可满足性问题32

1.11 习题35

第2章 距离40

2.1 关于距离的术语和记号40

2.2 最短路结构42

2.3 寻找有向图距离的算法44

2.3.1 宽度优先搜索（BFS）44

2.3.2 无圈有向图46

2.3.3 Dijkstra算法47

2.3.4 Bellman-Ford-Moore算法48

2.3.5 Floyd-Warshall算法51

2.4 半径、出半径和直径之间的不等式52

2.4.1 强有向图的半径和直径52

2.4.2 出半径和直径的极值53

2.5 定向图的最大有限直径54

2.6 多重图定向的最小直径55

2.7 完全多重图的最小直径定向59

2.8 图扩张的最小直径定向61

2.9 笛卡儿积图的最小直径定向63

2.10 有向图中的王66

2.10.1 竞赛图的2王66

2.10.2 半完全多部分有向图中的王66

2.10.3 广义竞赛图中的王68

2.11 应用：单行道问题和闲话问题69

2.11.1 单行道问题和有向图的定向69

2.11.2 闲话问题71

2.12 应用：旅行售货员问题的指数邻集局部搜索72

2.12.1 TSP局部搜索72

2.12.2 TSP的线性时间可搜索指数邻集74

2.12.3 分配邻集75

2.12.4 关于TSP的邻集结构有向图的直径76

2.13 习题78

第3章 网络流82

3.1 定义及基本性质82

3.1.1 流及流平衡向量83

3.1.2 剩余网络85

3.2 网络模型的简约86

3.2.1 消除下界86

3.2.2 单源单收点网络86

3.2.3 循环87

3.2.4 顶点上有费用及下界的网络88

3.3 流分解90

3.4 讨论剩余网络91

3.5 最大流问题93

3.5.1 Ford-Fullkerson算法96

3.5.2 最大流与线性规划98

3.6 寻找最大（s，t）流的多项式算法99

3.6.1 沿最短增广路的流增广99

3.6.2 在分层网络和Dinic算法中的块化流100

3.6.3 前置流推进算法101

3.7 单位容量网络和简单网络105

3.7.1 单位容量网络106

3.7.2 简单网络107

3.8 循环与可行流108

3.9 最小值可行（s，t）流110

3.10 最小费用流111

3.10.1 刻画最小费用流113

3.10.2 创建最优化解116

3.11 流的应用118

3.11.1 二部分图的最大匹配118

3.11.2 有向中国邮递员问题121

3.11.3 寻找具有预先指定度的有向子图123

3.11.4 有向多重图的路圈因子124

3.11.5 覆盖指定顶点的圈有向子图126

3.12 分配问题和运输问题127

3.13 习题136

第4章 有向图类148

4.1 深度优先搜索148

4.2 无圈有向图中的顶点无圈序151

4.3 可传递有向图、可传递闭包和简约153

4.4 强有向图155

4.5 线有向图158

4.6 deBruijn有向图和Kautz有向图及其特征162

4.7 系列平行有向图165

4.8 拟可传递有向图169

4.9 路重合性质和路可重合有向图171

4.10 局部入半完全有向图和局部出半完全有向图173

4.11 局部半完全有向图175

4.11.1 圆有向图175

4.11.2 非强局部半完全有向图179

4.11.3 强圆可分解局部半完全有向图181

4.11.4 局部半完全有向图类183

4.12 全Φi可分解有向图185

4.13 相交有向图187

4.14 平面有向图189

4.15 应用：高斯消去法191

4.16 习题193

第5章 哈密尔顿性及其相关问题196

5.1 有向图哈密尔顿性的必要条件197

5.1.1 路收缩197

5.1.2 拟哈密尔顿性198

5.1.3 伪哈密尔顿性和1拟哈密尔顿性200

5.1.4 关于伪哈密尔顿性和拟哈密尔顿性的算法201

5.2 路覆盖数201

5.3 无圈有向图的路因子及其应用203

5.4 路可重合有向图的哈密尔顿路与圈204

5.5 局部入半完全有向图的哈密尔顿路和圈205

5.6 具有度约束条件的有向图的哈密尔顿圈和路207

5.6.1 充分性条件207

5.6.2 多重插入技巧211

5.6.3 定理5.6.1和定理5.6.5的证明213

5.7 半完全多部分有向图中的最长路和最长路圈215

5.7.1 基本结论215

5.7.2 良圈因子定理217

5.7.3 引理5.7.12的推论220

5.7.4 Yeo不可约圈有向子图定理及其应用222

5.8 扩张局部半完全有向图的最长路和最长圈226

5.9 拟可传递有向图中的哈密尔顿路和圈227

5.10 拟可传递有向图中顶点最重路和最重圈230

5.11 有向图类的哈密尔顿路和圈234

5.12 习题236

第6章 深入研究哈密尔顿性241

6.1 具有预先指定起（终）点的哈密尔顿路242

6.2 弱哈密尔顿连通有向图243

6.2.1 关于扩张竞赛图的结论244

6.2.2 关于局部半完全有向图的结论248

6.3 哈密尔顿连通有向图251

6.4 在半完全有向图中寻找（x，y）哈密尔顿路253

6.5 有向图的泛圈性256

6.5.1 度约束有向图的（顶点）泛圈性256

6.5.2 扩张半完全有向图和拟可传递有向图的泛圈性257

6.5.3 泛局部半完全有向图和顶点泛局部半完全有向图260

6.5.4 关于图泛圈性的其他结果263

6.5.5 有向图的圈可扩张性264

6.6 弧泛圈性265

6.7 包含或避开预先指定弧的哈密尔顿圈267

6.7.1 包含预先指定弧的哈密尔顿圈268

6.7.2 避开预先指定弧的哈密尔顿圈270

6.7.3 避开2圈中弧的哈密尔顿圈272

6.8 弧不交的哈密尔顿路和圈273

6.9 定向的哈密尔顿路和圈275

6.10 用少量圈覆盖一个有向图的全部顶点280

6.10.1 具有固定圈数目的圈因子280

6.10.2 关于路和圈的支撑结构中α（D）的作用282

6.11 最小强支撑有向子图283

6.11.1 关于一般有向图的一个下界284

6.11.2 关于扩张半完全有向图的MSSS问题285

6.11.3 关于拟可传递有向图的MSSS问题286

6.11.4 可分解有向图的MSSS问题287

6.12 应用：TSP直观探索法的控制数288

6.13 习题290

第7章 全连通性294

7.1 附加的概念和预备知识295

7.2 耳朵分解297

7.3 Menger定理300

7.4 应用：确定弧强连通度和顶点强连通度303

7.5 撕裂运算305

7.6 最优化增长弧强连通性309

7.7 最优化增长顶点强连通性312

7.7.1 单行对313

7.7.2 最优化的k强增广315

7.7.3 特殊类有向图316

7.7.4 保持k强连通性的撕裂318

7.8 弧强连通性的一个推广320

7.9 弧反转和顶点强连通性322

7.10 最小k（弧）强有向多重图325

7.10.1 最小k弧强有向多重图326

7.10.2 最小k强有向图329

7.11 临界k强有向图333

7.12 弧强连通性与最小度334

7.13 特殊类有向图的连通性性质335

7.14 有向图的高连通定向337

7.15 拼装割集341

7.16 应用：关于k（弧）强连通性的小认证344

7.16.1 寻找强连通性的小认证345

7.16.2 寻找k强认证（k＞1）346

7.16.3 关于弧强连通性认证348

7.17 习题349

第8章 图的定向353

8.1 几类有向图的底图353

8.1.1 可传递有向图和拟可传递有向图的底图353

8.1.2 局部半完全有向图的底图356

8.1.3 正常循环弧图的局部竞赛图定向358

8.1.4 局部入半完全有向图的底图360

8.2 快速识别局部半完全有向图364

8.3 无偶圈定向367

8.4 图的着色与定向369

8.5 定向与无处零整流371

8.6 达到高弧强连通性的定向375

8.7 具有度约束的定向378

8.7.1 具有预先指定度序列的定向378

8.7.2 对顶点子集的限制382

8.8 子模流383

8.8.1 子模流模型383

8.8.2 可行子模流的存在性385

8.8.3 最小费用子模流388

8.8.4 子模流的应用388

8.9 混合图的定向392

8.10 习题396

第9章 不交路和不交树402

9.1 补充定义403

9.2 不交路问题403

9.2.1 k路问题的复杂性404

9.2.2 有向图是k链接的充分性条件408

9.2.3 无圈有向图的k路问题410

9.3 竞赛图和广义竞赛图的链接问题413

9.3.1 具有（局部）连通性的充分性条件413

9.3.2 半完全有向图的2路问题417

9.3.3 广义竞赛图的2路问题418

9.4 平面有向图的链接问题421

9.5 弧不交分枝424

9.5.1 Edmonds分枝定理的重要性426

9.6 边不交的混合分枝429

9.7 弧不交的路问题430

9.7.1 无圈有向多重图中弧不交的路432

9.7.2 欧拉有向多重图中弧不交的路433

9.7.3 竞赛图和广义竞赛图中弧不交的路438

9.8 整多物品流441

9.9 弧不交的出分枝和入分枝442

9.10 最小费用分枝447

9.10.1 拟阵相交的表述447

9.10.2 有关最小费用分枝问题推广的一个算法448

9.10.3 最小覆盖树形图问题453

9.11 添加新弧以增加有根弧强连通性455

9.12 习题456

第10章 有向图的圈结构462

10.1 有向图的向量空间462

10.2 关于路和圈的多项式算法466

10.3 不交圈和反馈弧集469

10.3.1 不交圈和反馈集问题的复杂性469

10.3.2 最大出度至少为k的有向图中不交圈470

10.3.3 有向图的反馈集和线性序472

10.4 不交圈对反馈集的比较476

10.4.1 参数vi和Ti的关系476

10.4.2 Younger猜想的解决477

10.5 应用：Markov链的周期480

10.6 模p下的k长圈482

10.6.1 模p下k长圈存在性问题的复杂度482

10.6.2 模P下k长圈存在的充分性条件483

10.7 半完全多部分有向图中的“短”圈486

10.8 半完全多部分有向图中圈对路的比较489

10.9 围长493

10.10 有关圈的补充专题495

10.10.1 圈的弦495

10.10.2 Adam猜想496

10.11 习题498

第11章 有向图的推广501

11.1 边着色多重图中的正常着色迹501

11.1.1 正常着色欧拉迹503

11.1.2 正常着色圈506

11.1.3 边着色多重图的连通性509

11.1.4 边着色二部分多重图的交错圈512

11.1.5 2边着色完全多重图的最长交错路和圈514

11.1.6 c边着色完全图中正常着色哈密尔顿路（c≥3）520

11.1.7 c边着色完全图中正常着色哈密尔顿圈（c≥3）521

11.2 弧着色有向多重图525

11.2.1 交错有向圈问题的复杂性526

11.2.2 函数f（n）和函数g（n）529

11.2.3 弱欧拉弧着色有向多重图531

11.3 超竞赛图532

11.3.1 超竟赛图的出度序列533

11.3.2 哈密尔顿路534

11.3.3 哈密尔顿圈535

11.4 应用：遗传学中的交错哈密尔顿圈536

11.4.1 定理11.4.1的证明538

11.4.2 定理11.4.2的证明539

11.5 习题540

第12章 一些重要的专题542

12.1 Seymour第二邻集猜想542

12.2 配对比较有向图的顶点排序545

12.2.1 配对比较有向图545

12.2.2 Kano-Sakamoto排序法547

12.2.3 半完全PCD的顶点排序548

12.2.4 相互序549

12.2.5 关于向前序和向后序的算法及其复杂性549

12.3 （k，l）核552

12.3.1 核552

12.3.2 拟核554

12.4 完全二部分有向图的列表边着色555

12.5 同态—着色的一个推广558

12.6 有向图独立性的其他度量法563

12.7 拟阵565

12.7.1 拟阵的对偶567

12.7.2 拟阵的贪婪算法567

12.7.3 独立性问答器569

12.7.4 拟阵的并569

12.7.5 二个拟阵的相交570

12.7.6 多个拟阵的相交571

12.8 为NP困难问题寻找好解572

12.9 习题575

参考文献580

记号索引616

术语索引625

译后记661

《现代数学译丛》已出版书目663