计算机科学

首页 > 计算机科学

网络流

2018-08-28 09:36:34     所属分类:图算法

在图论中,网络流英语:Network flow)是指在一个每条边都有容量(capacity)的有向图分配,使一条边的流量不会超过它的容量。通常在运筹学中,有向图称为网络。顶点称为节点(node)而边称为(arc)。一道流必须匹配一个结点的进出的流量相同的限制,除非这是一个源点(source)──有较多向外的流,或是一个汇点(sink)──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。

目录

  • 1 定义
  • 2 例子
  • 3 应用
    • 3.1 普遍化及专门化
  • 4 参见
  • 5 参考文献
  • 6 延伸阅读
  • 7 外部链接

定义

假设 是一个有限的有向图,它的每条边 都有一个非负值实数的容量。如果,我们假设 。我们区别两个顶点:一个源点 和一个汇点 。一道网络流是一个对于所有结点 都有以下特性的实数函数

容量限制(Capacity Constraints) 一条边的流不能超过它的容量。
反对称(Skew Symmetry) 的净流必须是由的净流的相反(参考例子)。
流守恒(Flow Conservation) 除非,否则一结点的净流是零,除了“制造”流的源点和“消耗”流的汇点。

流守恒意味着: ,对每个顶点

注意 是由 流。如果该图代表一个实质的网络,由 有4单位的实际流及由 有3单位的实际流,那么

基本上,我们可以说,物理网络的网络流是从 s = 出发的流

边的剩余容量(residual capacity)是 。这定义了以 表示的剩余网络(residual network),它显示可用的容量的多少。留意就算在原网络中由 没有边,在剩余网络仍可能有由 的边。因为相反方向的流抵消,减少 的流等于增加 的流。增广路(augmenting path)是一条路径 ,而 ,这表示沿这条路径发送更多流是可能的。当且仅当剩余网络 没有增广路时处于最大流。

因此如下使用图 G 创建

  1. = 的顶点
  1. 定义如下的 = 的边

对每条边

  1. ,创建容量的前向边
  2. ,创建容量的后向边

这个概念用在计算流量网的最大流的Ford–Fulkerson算法中。

有时需要对有多于一个源点的网络,于是就引入了图的超源点[1] 这包含了一个与无限容量的边连接的每个源点,以作为一个整体源点。汇点也有类似的构造称作超汇点[2]

例子

一个显示了流及容量的流网络。

在右边可以看到一个有以标示的源点、以标示的汇点及4个额外结点的流网络。流及容量以显示。注意网络怎样保证斜对称、容量限制及流守恒。由的总流量为5,由此可简单地观察到源于的所有向外流是5,也就是汇于的向内流。我们知道在其它结点中没有任何流出现或消失。

上面的流网络的剩余网络,显示了剩余容量。

在下面你可以看到对既定的流的剩余网络。注意某些边的剩余容量是正数而原来的容量是零,如边。这道流不是一道最大流。沿路径还有可用的容量,也就是扩张路径。第一条路径的剩余容量是。注意扩张路径在原来的网络中并不存在,但你可以沿它发送流,因此仍是一道正当的流。

假如这是一个真实的网络,由的2单位的流及由的1单位的流事实上可能存在,但我们只维持流。

应用

将一连串的水管绘画成一个网络。每条水管有一特定的阔度,因此只可以保持一特定的水流量。当任何水管汇合,流入汇流点的总水量必须等于流出的水量,否则我们会很快地缺水,或者我们会团积水。我们有一个作为源点的入水口,和一个作为汇点的出水口。一道流便是一条由源点到汇点而使从出水口流出的总水量一致的可能路径。直观地,一个网络的总流量是水从出口流出的速率。

流可以适用于交通网络上的人或材料,或配电系统上的电力。对于任何这样的实物网络,进入任何中途结点的流需要等于离开那个结点的流。这个守恒限制相当于基尔霍夫电流定律。

在生态学中也可找到网络流的应用:当考虑在食物网中不同组织之间养料及能量的流,网络流便自然地产生。与这些网络有联系的数学问题和那些液体流或交通流网络中所产生的难题有很大分别。由Robert Ulanowicz及其他人发展的生态系统网络分析领域包含使用信息论及热力学的概念去研究这些网络随时间的演变。

普遍化及专门化

利用网络流去找出最大流是最简单及最普通的问题,它提供了在一指定的图中由源点到汇点的最大可能总流量。还有很多其它问题可以利用最大流算法去解决,假设它们可以适当地塑造成流网络的模样,例如二部图匹配(Bipartite Matching)、任务分配问题(Assignment Problem)和运输问题(Transportation Problem)。

在多物网络流问题(Multi-commodity Flow Problem)中,可以有多个源点和汇点,和各种各样的由指定源点发送到指定汇点的“物品(Commodities)”。例如这可能是不同的工厂生产的各种各样的货物经由“同一”运输网络运送到不同的消费者手上。

在最小费用最大流问题(Minimum Cost Flow Problem)中,每条边都有特定费用。沿这条边发送的费用是。目标是要用最低的成本由源点发送一特定数量的流到汇点。

在环流问题(Circulation Problem)中,每条边除了有上限外,还有下限。每条边亦有一个费用。很多时,流守恒适用于环流问题中所有结点,由汇点到源点亦有一条链接。这样便能利用支配总流量。这问题因流环绕网络流动而得名。

有增益网络普遍化网络中,每条边都有增益,一个实数(非零)使如果这条边有一增益g而有一流量x的流在尾部流入,便有一流量gx的流从头部流出。

参见

  • 布雷斯悖论
  • 中心性英语Centrality
  • 构形理论英语Constructal theory
  • Ford–Fulkerson算法
  • Dinic算法
  • 流量 (计算机联网)英语Flow (computer networking)
  • 有根图英语Rooted graph
  • 最大流最小割定理
  • 定向拟阵英语Oriented matroid
  • 最短路问题

参考文献

  1. ^  本条目引用的公有领域材料。材料来自NIST的文档:Black, Paul E. Supersource. 算法与数据结构辞典英语Dictionary of Algorithms and Data Structures. 
  2. ^  本条目引用的公有领域材料。材料来自NIST的文档:Black, Paul E. Supersink. 算法与数据结构辞典英语Dictionary of Algorithms and Data Structures. 

延伸阅读

  • George T. Heineman, Gary Pollice, and Stanley Selkow. Chapter 8:Network Flow Algorithms. Algorithms in a Nutshell. Oreilly Media. 2008: 226–250. ISBN 978-0-596-51624-6. 
  • Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall. 1993. ISBN 0-13-617549-X. 
  • Bollobás, Béla. Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag. 1979. ISBN 3-540-90399-2. 
  • Chartrand, Gary & Oellermann, Ortrud R. Applied and Algorithmic Graph Theory. New York: McGraw-Hill. 1993. ISBN 0-07-557101-3. 
  • Even, Shimon. Graph Algorithms. Rockville, Maryland: Computer Science Press. 1979. ISBN 0-914894-21-8. 
  • Gibbons, Alan. Algorithmic Graph Theory. Cambridge: Cambridge University Press. 1985. ISBN 0-521-28881-9. 
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 26. Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001: 696–697 1990. ISBN 0-262-03293-7. 

外部链接

  • Maximum Flow Problem
  • Real graph instances
  • Lemon C++ library with several maximum flow and minimum cost circulation algorithms
  • QuickGraph, graph data structures and algorithms for .Net

相关推荐