具体描述
A comprehensive introduction to network flows that brings together the classic and the contemporary aspects of the field, and provides an integrative view of theory, algorithms and applications.* presents in-depth, self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including descriptions of polynomial-time algorithms for these core models. * emphasizes powerful algorithmic strategies and analysis tools such as data scaling, geometric improvement arguments, and potential function arguments. * provides an easy-to-understand descriptions of several important data structures, including d-heaps, Fibonacci heaps, and dynamic trees. * devotes a special chapter to conducting empirical testing of algorithms. * features over 150 applications of network flows to a variety of engineering, management, and scientific domains. * contains extensive reference notes and illustrations.
作者简介
目录信息
PREFACE, xl
1 INTRODUCTION, 1
1.1 Introduction, 1
1.2 Network Flow Problems, 4
1.3 Applications, 9
1.4 Summary, 18
Reference Notes, 19
Exercises, 20
2 PATHS, TREES, AND CYCLES, 23
2.1 Introduction, 23
2.2 Notation and Definitions, 24
2.3 Network Representations, 31
2.4 Network Transformations, 38
2.5 Summary, 46
Reference Notes, 47
Exercises, 47
3 ALGOlUTHM DESIGN AND ANALYSIS, ~3
3.1 Introduction, 53
3.2 Complexity Analysis, 56
3.3 Developing Polynomial-Time Algorithms, 66
3.4 Search Algorithms, 73
3.5 Flow Decomposition Algorithms, 79
3.6 Summary, 84
Reference Notes, 85
Exercises, 86
4 SHORTEST PA THS: LABEL-SETTING ALGOBITHMS, 93
4.1 Introduction, 93
4.2 Applications, 97
4.3 Tree of Shortest Paths, 106
4.4 Shortest Path Problems in Acyclic Networks, 107
4.5 Dijkstra's Algorithm, 108
4.6 Dial's Implementation, 113
4.7 Heap Implementations, 115
4.8 Radix Heap Implementation, 116
v
4.9 Summary, 121
Reference Notes, 122
Exercises, 124
15 SHORTEST PATHS: LABEL-COBBECTING ALGOBITHMS, 133
5.1 Introduction, 133
5.2 Optimality Conditions, 135
5.3 Generic Label-Correcting Algorithms, 136
5.4 Special Implementations of the Modified Label-Correcting Algorithm, 141
5.5 Detecting Negative Cycles, 143
5.6 All-Pairs Shortest Path Problem, 144
5.7 Minimum Cost-to-Time Ratio Cycle Problem, 150
5.8 Summary, 154
Reference Notes, 156
Exercises, 157
8 MAXIMUM FLOWS: BABIC IDEAS, 188
6.1 Introduction, 166
6.2 Applications, 169
6.3 Flows and Cuts, 177
6.4 Generic Augmenting Path Algorithm, 180
6.5 Labeling Algorithm and the Max-Flow Min-Cut Theorem, 184
6.6 Combinatorial Implications of the Max-Flow Min-Cut Theorem, 188
6.7 Flows with Lower Bounds, 191
6.8 Summary, 196
Reference Notes, 197
Exercises, 198
7 MAXIMUM FLOWS: POLYNOMIAL ALGOBITHMB, 207
7.1 Introduction, 207
7.2 Distance Labels, 209
7.3 Capacity Scaling Algorithm, 210
7.4 Shortest Augmenting Path Algorithm, 213
7.5 Distance Labels and Layered Networks, 221
7.6 Generic Preflow-Push Algorithm, 223
7.7 FIFO Preflow-Push Algorithm, 231
7.8 Highest-Label Preflow-Push Algorithm, 233
7.9 Excess Scaling Algorithm, 237
7.10 Summary, 241
Reference Notes, 241
Exercises, 243
8 MAXIMUM FLOWS: ADDITIONAL TOPICS, 2lJO
8.1 Introduction, 250
8.2 Flows in Unit Capacity Networks, 252
8.3 Flows in Bipartite Networks, 255
8.4 Flows in Planar Undirected Networks, 260
8.5 Dynamic Tree Implementations, 265
vi Contents
8.6 Network Connectivity, 273
8.7 All-Pairs Minimum Value Cut Problem, 277
8.8 Summary, 285
Reference Notes, 287
Exercises, 288
9 MINIMUM COST FLOWS: BABIC ALGOBITHMS, 294
9.1 Introducti"on, 294
9.2 Applications, 298
9.3 Optimality Conditions, 306
9.4 Minimum Cost Flow Duality, 310
9.5 Relating Optimal Flows to Optimal Node Potentials, 315
9.6 Cycle-Canceling Algorithm and the Integrality Property, 317
9.7 Successive Shortest Path Algorithm, 320
9.8 Primal-Dual Algorithm, 324
9.9 Out-of-Kilter Algorithm, 326
9.10 Relaxation Algorithm, 332
9.11 Sensitivity Analysis, 337
9.12 Summary, 339
Reference Notes, 341
Exercises, 344
10 MINIMUM COST FLOWS: POLYNOMIAL ALGORITHMS, 8lJ7
10.1 Introduction, 357
10.2 Capacity Scaling Algorithm, 360
10.3 Cost Scaling Algorithm, 362
10.4 Double Scaling Algorithm, 373
10.5 Minimum Mean Cycle-Canceling Algorithm, 376
10.6 Repeated Capacity Scaling Algorithm, 382
10.7 Enhanced Capacity Scaling Algorithm, 387
10.8 Summary, 395
Reference Notes, 396
Exercises, 397
11 MINIMUM COST FLOWS: NETWORK SIMPLEX ALGO.RlTHMS, 402
11.1 Introduction, 402
11.2 Cycle Free and Spanning Tree Solutions, 405
11.3 Maintaining a Spanning Tree Structure, 409
11.4 Computing Node Potentials and Flows, 411
11. 5 Network Simplex Algorithm, 415
11.6 Strongly Feasible Spanning Trees, 421
11.7 Network Simplex Algorithm for the Shortest Path Problem, 425
11.8 Network Simplex Algorithm for the Maximum Flow Problem, 430
11.9 Related Network Simplex Algorithms, 433
11.10 Sensitivity Analysis, 439
11.11 Relationship to Simplex Method, 441
11.12 U nimodularity Property, 447
11.13 Summary, 450
Reference Notes, 451
Exercises, 453
Contents vii
12 ABSIGNMENTSANDMATCHINGS, 481
12.1 Introduction, 461
12.2 Applications, 463
12.3 Bipartite Cardinality Matching Problem, 469
12.4 Bipartite Weighted Matching Problem, 470
12.S Stable Marriage Problem, 473
12.6 Nonbipartite Cardinality Matching Problem, 475
12.7 Matchings and Paths, 494
12.8 Summary, 498
Reference Notes, 499
Exercises, 501
13 MINIMUM SPANNING TREES, 1510
13.1 Introduction, 510
13.2 Applications, 512
13.3 Optimality Conditions, 516
13.4 Kruskal's Algorithm, 520
13.S Prim's Algorithm, 523
13.6 Sollin's Algorithm, 526
13.7 Minimum Spanning Trees and Matroids, 528
13.8 Minimum Spanning Trees and Linear Programming, 530
13.9 Summary, 533
Reference Notes, 535
Exercises, 536
14 CONVEX COST FLOWS, 1543
14.1 Introduction, 543
14.2 Applications, 546
14.3 Transformation to a Minimum Cost Flow Problem, 551
14.4 Pseudopolynomial-Time Algorithms, 554
14.S Polynomial-Time Algorithm, 556
14.6 Summary, 560
Reference Notes, 561
Exercises, 562
15 GENEBALIZED FLOWS, 1588
IS.1 Introduction, 566
IS.2 Applications, 568
15.3 Augmented Forest Structures, 572
IS.4 Determining Potentials and Flows for an Augmented Forest Structure, 577
IS.S Good Augmented Forests and Linear Programming Bases, 582
IS.6 Generalized Network Simplex Algorithm, 583
IS.7 Summary, 591
Reference Notes, 591
Exercises, 593
viii Contents
16 LAGRANGIAN RELAXATION AND NETWORK OPTIMIZATION, 698
16.1 Introduction, 598
16.2 Problem Relaxations and Branch and Bound, 602
16.3 Lagrangian Relaxation Technique, 605
16.4 Lagrangian Relaxation and Linear Programming, 615
16.5 Applications of Lagrangian Relaxation, 620
16.6 Summary, 635
Reference Notes, 637
Exercises, 638
17 MULTICOMMODITY FLOWS, 849
17.1 Introduction, 649
17.2 Applications, 653
17.3 Optimality Conditions, 657
17.4 Lagrangian Relaxation, 660
17.5 Column Generation Approach, 665
17.6 Dantzig-Wolfe Decomposition, 671
17.7 Resource-Directive Decomposition, 674
17.8 Basis Partitioning, 678
17.9 Summary, 682
Reference Notes, 684
Exercises, 686
18 COMPUTATIONAL TESTING OF ALGOlUTHMS, 896
18.1 Introduction, 695
18.2 Representative Operation Counts, 698
18.3 Application to Network Simplex Algorithm, 702
18.4 Summary, 713
Reference Notes, 713
Exercises, 715
19 ADDITIONAL APPLICATIONS, 717
19.1 Introduction, 717
19.2 Maximum Weight Closure of a Graph, 719
19.3 Data Scaling, 725
19.4 Science Applications, 728
19.5 Project Management, 732
19.6 Dynamic Flows, 737
19.7 Arc Routing Problems, 740
19.8 Facility Layout and Location, 744
19.9 Production and Inventory Planning, 748
19.10 Summary, 755
Reference Notes, 759
Exercises, 760
Contents Ix
APPENDIX A DATA STBUCTUBES, 78~
A.I Introduction, 765
A.2 Elementary Data Structures, 766
A.3 d-Heaps, 773
A.4 Fibonacci Heaps, 779
Reference Notes, 787
APPENDIX B Nf/I-COMPLETENESS, 788
B.I Introduction, 788
B.2 Problem Reductions and Transformations, 790
B.3 Problem Classes r;p, ,Nr;p, ,Nr;p-Complete, and ,Nr;p-Hard, 792
B.4 Proving ,Nr;p-Completeness Results, 796
B.5 Concluding Remarks, 800
Reference Notes, 801
APPENDIX C LINEAR PROGRAMMING, 802
C.I Introduction, 802
C.2 Graphical Solution Procedure, 804
C.3 Basic Feasible Solutions, 805
C.4 Simplex Method, 810
C.S Bounded Variable Simplex Method, 814
C.6 Linear Programming Duality, 816
Reference Notes, 820
BEFEBENCES, 821
INDEX, 840
· · · · · · (收起)
读后感
用户评价
《Network Flows》这本书，我拿到手的时候，就觉得它名字听起来有点学术，但又带着一丝神秘感。我一直对网络模型和数据流动的概念挺好奇的，总觉得里面藏着很多解决实际问题的智慧。我猜想，这本书应该会从最基础的图论概念讲起，比如节点、边，然后逐步深入到如何表示和分析一个网络。我尤其期待它能讲解一些经典的流动问题，比如最大流问题、最小割问题，看看这些抽象的概念是如何与交通、通信、物流等现实世界联系起来的。 想象一下，书中可能会用大量的图示来解释各种算法，比如 Ford-Fulkerson 算法或者 Edmonds-Karp 算法，让那些原本枯燥的数学公式变得生动易懂。我希望能看到书中给出一些实际应用的案例，比如如何优化城市的交通信号灯配时，如何设计高效的物流配送网络，或者如何在大规模数据传输中找到瓶颈。如果能有章节专门讨论一些更高级的主题，比如多商品流、动态网络流，那就更好了，毕竟现代社会的需求越来越复杂，一个简单的流动模型可能已经不够用了。 我甚至觉得，这本书可能会探讨网络流在机器学习和人工智能领域的应用。比如，在图像分割、物体识别等问题中，网络流的思想是否能发挥作用？又或者，在推荐系统中，用户之间的连接和兴趣可以被看作是一种“流”，这本书会不会提供一些理论上的指导，帮助我们理解和优化这些推荐机制？我期待它能提供一些启发性的思考，不仅仅是技术层面的讲解，更能引发对网络本质和信息流动的深刻理解。 这本书，我感觉它的受众可能很广泛，不仅仅是计算机科学专业的学生，也可能包括运筹学、工程学，甚至经济学领域的读者。毕竟，很多实际问题都可以抽象成网络流问题来解决。我希望书中能够循序渐进，即使是没有深厚数学背景的读者，也能通过阅读这本书，逐步掌握网络流的核心思想和解决问题的方法。对于那些有志于从事优化、算法设计、系统分析等工作的读者来说，这本书无疑是一本宝贵的参考书。 如果《Network Flows》这本书能做到图文并茂，并且深入浅出，那绝对是一本值得反复阅读的好书。我希望它不仅仅是一本理论的讲解，更能是一本实践的指导。它应该能教会我如何将书中的理论应用到实际问题中，如何分析和解决现实世界中遇到的各种网络流动难题。我设想，读完这本书，我应该能更清晰地理解“连接”和“流动”在各个领域的重要性，并能够运用所学的知识，为解决一些实际挑战提供新的视角和方法。
刚拿到《Network Flows》这本书，还没深入翻阅，但仅仅从书名就能感受到它蕴含的严谨和深度。我一直对如何理解和优化那些由无数个体连接而成的复杂系统很感兴趣，而“网络流”这个概念，听起来就像是打开这些系统运行机制的一把钥匙。我猜想，这本书的开头部分，应该会从最基础的图论概念讲起，比如如何定义一个网络，节点和边分别代表什么，以及“流”在这个网络中的意义。 我特别期待书中能对一些核心的网络流问题进行详细的阐述，例如最大流问题，它在很多实际场景中都有应用，还有最小割问题，它揭示了网络的瓶颈所在。我希望作者能够用清晰的语言，辅以大量的图示，来解释这些抽象的概念，让即使是没有深厚数学背景的读者也能有所领悟。如果书中能够结合一些现实世界的案例，比如在物流配送、通信网络优化，甚至是能源传输等领域的应用，那将大大增强其吸引力。 我设想，这本书的中间部分很可能会涉及各种求解网络流问题的算法，从经典的 Ford-Fulkerson 方法到更高效的 Edmonds-Karp 算法，甚至可能包括一些针对特定类型网络的算法。我希望作者能够深入讲解这些算法的原理、步骤，并且分析它们的计算复杂度。我也好奇，书中是否会涉及一些更复杂的问题，比如多商品流、动态网络流，或者是在不确定性条件下如何进行流的规划。 《Network Flows》这本书，在我看来，它更像是一本能够教会我如何“解决问题”的工具书。我期待读完后，我能够掌握将现实世界中的各种“连接”和“流动”现象，抽象成数学模型的能力，并且能够运用书中提供的算法来求解。我希望书中能有一些指导，说明如何在实际应用中选择最合适的模型和算法，以及如何解释和验证求解结果，从而真正地解决实际问题。 总而言之，我希望《Network Flows》这本书能够成为我理解和优化复杂网络系统的入门指南。它应该能让我明白，无论是信息、物质还是其他任何形式的“流”，在网络中的传递都有其内在的规律。我期待通过这本书，我能获得一种分析和解决网络相关问题的能力，并且能够将这些知识应用到我的研究和工作中，去提升效率，降低成本，或者找到更优的解决方案。
手里的《Network Flows》这本书，光听名字就感觉沉甸甸的，充满了一种探索未知领域的感觉。我一直对那些能够解释复杂系统背后运行机制的理论很着迷，而网络流似乎就是这样一种能够洞察事物如何连接和流动的强大工具。我猜测，这本书的开篇肯定会从最基础的图论概念讲起，比如节点、边、路径这些，然后逐步引入“流”的概念，解释它如何在网络中穿梭。 我特别期待看到书中对一些经典网络流问题的深入剖析，比如如何找到一个网络中源点到汇点的最大流量，以及如何确定限制这个最大流量的“最小割”。我希望作者能用清晰易懂的语言，配合丰富的图示，将那些看起来很抽象的数学概念形象化。如果书中能穿插一些实际的应用案例，比如在电信网络的流量分配、城市交通系统的优化，甚至是生物系统中物质的运输等方面的例子，那就太有意思了。 我设想，这本书的中间部分会着重讲解各种解决网络流问题的算法，比如 Ford-Fulkerson 算法、Edmonds-Karp 算法，甚至可能更高级的 ISAP 或 Dinic 算法。我希望作者不仅能介绍算法的步骤，还能解释其背后的数学原理，并分析算法的效率和复杂度。我特别想知道，当网络规模越来越大时，这些算法的表现如何，以及是否有更高效的近似算法或者启发式算法。 《Network Flows》这本书，我感觉它不仅仅是一本理论书籍，更可能是一本指导实践的宝典。我期望读完之后，我能够具备将现实世界中的各种“连接”和“流动”问题，抽象成网络流模型的能力，并能够运用书中学到的算法来求解。如果书中还能提供一些关于如何选择最适合的网络流模型，以及如何处理实际数据中可能出现的各种偏差和不完整性的建议，那就更具价值了。 总的来说，我期待《Network Flows》这本书能为我打开一扇理解复杂系统运作的窗户。它应该能让我明白，无论是信息、能源还是商品，它们在网络中的流动，都遵循着一些深刻的数学规律。我希望通过阅读这本书，我能获得一种分析和优化各种网络系统的能力，并且能够将这些知识应用到我的学习和工作中，去解决那些关于效率和容量的挑战。
最近在看一本叫做《Network Flows》的书，光听书名就感觉内容会很“硬核”，充满数学和算法的味道。我一直对如何高效地在各种系统中进行信息或资源的传递很感兴趣，所以这本书的主题正好戳中了我的好奇点。我猜想，这本书大概会从图论的基础讲起，什么是节点，什么是边，以及它们之间的关系如何构成一个网络。然后，它应该会引入“流”的概念，解释在这样的网络中，信息或者资源是如何移动的。 我非常期待书中能够详细介绍一些经典的流问题，比如如何在一个网络中找出从一个起点到另一个终点的最大流量，以及“最小割”问题，也就是找到最少需要移除多少条边才能将网络分割开。我希望这本书的讲解能够循序渐进，即使我对图论不是非常熟悉，也能通过书中的例子和图示，慢慢理解这些抽象的概念。如果书中能穿插一些实际应用的例子，比如在物流配送、通信带宽优化或者交通流量管理方面的应用，那就太棒了。 我感觉这本书可能会包含一些用来求解这些流问题的算法，比如 Ford-Fulkerson 算法或者 Edmonds-Karp 算法。我希望作者能够清晰地解释这些算法的工作原理，以及它们的优缺点。更进一步，我希望能看到书中对这些算法的复杂度进行分析，并且可能会介绍一些更高效的算法，特别是针对大规模网络的。我甚至猜想，书中会不会涉及一些更复杂的网络流问题，比如多商品流或者动态网络流，这些问题在现实世界中应该更加常见。 这本书，我感觉它不仅仅是提供理论知识，更可能是一本能够教会我如何解决实际问题的参考书。我希望读完之后，我能够清晰地理解如何将现实世界中的各种问题，比如如何优化管道系统的输水效率，或者如何设计一个高效的邮件分发网络，抽象成网络流模型，并运用书中学到的算法来求解。如果书中能提供一些编程的提示或者伪代码，那就更好了，这样我就可以尝试自己动手去实现这些算法。 总的来说，《Network Flows》这本书，我期待它能在我脑海中构建起一个关于网络和流动的清晰框架。它应该能让我明白，看似复杂的信息和资源传递问题，都可以通过严谨的数学模型和高效的算法来解决。我希望它能成为我解决实际问题的一个有力工具，并且能够激发我对这个领域的进一步探索。如果书中还能有一些关于未来网络流研究方向的展望，那就更具启发性了。
收到《Network Flows》这本书，第一印象是它封面设计得很专业，那种严谨而又不失现代感的风格，让我对书中的内容充满了期待。我一直对解决复杂系统中的优化问题很感兴趣，而网络流恰恰是解决这类问题的一种强大工具。我猜测这本书的开篇会从网络流的基本概念入手，比如如何用图来表示实体之间的连接，以及“流”在这些连接上的含义。我特别希望它能详细介绍一些核心的算法，比如如何在一个网络中找到从源点到汇点的最大流量，以及如何找出那个限制整个系统容量的“瓶颈”。 书里很可能包含丰富的数学公式和证明，但我相信作者会尽量以一种易于理解的方式呈现，或许会辅以大量的图例来辅助说明。我想象中，书中会针对不同的应用场景，给出具体的例子，例如在交通系统中，如何规划最优路线以减少拥堵；在通信网络中，如何高效地传输数据，避免信息丢失；甚至在资源分配问题上，网络流也能提供解决方案。我希望这本书能够拓展我的视野，让我看到网络流模型在不同学科领域的普适性，并且能启发我思考如何将这些思想应用到我自己的研究或工作中。 我脑海中浮现的，是书中可能会深入探讨一些更高级的流问题，比如如何在多个节点之间同时传输不同的“商品”，也就是多商品流问题，以及当网络的容量或需求随时间变化时的动态网络流问题。这些更复杂的模型，往往能更贴切地描述现实世界中的许多情况。我期待这本书能提供清晰的讲解和严谨的推导，帮助我理解这些高级概念背后的逻辑，并掌握相应的求解方法。如果书中能涉及一些与这些高级模型相关的实际案例，那就更完美了。 我个人觉得，《Network Flows》这本书的价值可能并不仅仅局限于理论层面，它更可能是一本实操性的指南。我期望它能引导读者如何将书中所学的理论知识转化为解决实际问题的能力。比如，在读完关于最大流算法的章节后，我希望能够通过书中的指导，尝试在一个实际的网络问题中应用这些算法，并对结果进行分析和评估。这样，学习过程就会变得更加生动和有效，而不仅仅是知识的堆砌。 这本书，如果能够提供一些关于如何选择合适网络流模型，以及如何处理实际数据中可能出现的噪声和不确定性等方面的讨论，那将极大地提升它的实用价值。我希望它能教会我如何将现实世界的问题抽象成数学模型，如何运用算法求解，并且最终如何解释和验证求解结果。读完这本书，我希望能对如何构建和分析各种类型的网络系统，以及如何利用网络流的原理来优化这些系统，有一个更深刻的理解和更强的实践能力。
从零开始，除了network flow 甚至连复杂度都讲了。 network simplex 的所有变种以及和线性代数的关联都有详细讲解，并有例子和习题。很古典也很经典的一本教科书。
网络流最经典的一本书了吧！OR，CS等专业课的必备书,作者来自印度最牛X的理工院校IITs。此书应该是88年那版的扩充，分类和内容都要比之前那版详尽
网络流最经典的一本书了吧！OR，CS等专业课的必备书,作者来自印度最牛X的理工院校IITs。此书应该是88年那版的扩充，分类和内容都要比之前那版详尽
考qual用的教材。
IEOR 266的参考书，其实跳过了不少部分
