网络流

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

定义[编辑]

网络流图[编辑]

如果带权有限的有向图 $G=(V,\,E)$ 满足如下条件，则称之为网络流图(或容量网络):

有且仅有一个结点 $s\in V$ 入度为0.称为源点。
有且仅有一个结点 $t\in V$ 出度为0.称为汇点。
$\forall (u,v)\in E\quad \exists c(u,v)\in R^{+}$ , 称为这条弧的容量。特别地，如果 $(u,v)\not \in E$ ，可以假定 $c(u,v)=0$ .

净流[编辑]

通过容量网络中的一条弧 $(u,v)$ 的流量(或净流)记为 $f(u,v)$ .

弧[编辑]

弧是网络流图中的一条带权边 $(u,v)\in E$ .

特殊的弧有：

零流弧满足 $f(u,v)=0$ .
非零流弧满足 $f(u,v)\not =0$ .
饱和弧满足 $f(u,v)=c(u,v)$ .
非饱和弧满足 $f(u,v)<c(u,v)$ .

网络流[编辑]

一个流量的集合 $F=\{f(u,v)\}$ 包含所有弧上的流，则称为这个容量网络的一个网络流。

可行流[编辑]

在容量网络中满足以下条件的网络流称为可行流:

容量限制（Capacity Constraints）: $f(u,v)\leq c(u,v)$ .
流守恒（Flow Conservation）: 除非 $u=s$ 或 $u=t$ ，否则 $\sum _{w\in V}f(u,w)=0$ 一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。

伪流[编辑]

伪流是一种与可行流相对的概念，如果一个网络流只满足容量限制条件，不满足流守恒条件，那么这个网络流就是一个伪流。

剩馀容量[编辑]

边的剩馀容量（Residual Capacity）简称为残量,是 $c_{f}(u,v)=c(u,v)-f(u,v)$ .

残量网络[编辑]

由所有边均为其残量的 $G_{f}(V,E_{f})$ 称为残量网络（Residual Network）或剩余网络.它显示可用的容量的多少。留意就算在原网络中由 $u$ 到 $v$ 没有边，在剩余网络仍可能有由 $u$ 到 $v$ 的边。因为相反方向的流抵消，减少由 $v$ 到 $u$ 的流等于增加由 $u$ 到 $v$ 的流。

最大流[编辑]

对于一个网络流图，它最大的可行流即为它的最大流。

增广路[编辑]

增广路（Augmenting Path）是一条路径 $(u_{1},u_{2},\cdots ,u_{k})$ ，而 $u_{1}=s$ 、 $u_{k}=t$ 及 $c_{f}(u_{i},u_{i+1})>0$ ，这表示沿这条路径传送更多流是可能的。当且仅当剩余网络 $G_{f}$ 没有增广路时处于最大流。

性质[编辑]

在任意时刻， $G$ 的网络流都满足如下性质。

容量限制[编辑]

通过一条弧的流量不能超过这条弧的容量上限。

$\forall u,v\in V,\;f(u,v)\leq c(u,v)$

反对称性[编辑]

从一个结点 $u$ 到另一个结点 $v$ 的净流量一定是从 $v$ 到 $u$ 净流量的相反数。

$\forall u,v\in V,\;f(u,v)=-f(v,u)$

流守恒[编辑]

对于 $G$ 中任意一个结点 $u$ ,如果它既不是源点也不是汇点，那么它到相邻结点的所有流量之和为0.

$\forall u\in V-\{s,t\},\;\sum _{w\in V}f(u,w)\,=0$

例子[编辑]

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

在下面你可以看到对既定的流的剩馀网络。注意某些边的剩馀容量是正数而原来的容量是零，如边 $(d,c)$ 。这道流不是一道最大流。沿路径 $(s,a,c,t)$ 、 $(s,a,b,d,t)$ 及 $(s,a,b,d,c,t)$ 还有可用的容量，也就是扩张路径。第一条路径的剩馀容量是 $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))=\min(5-3,3-2,2-1)=\min(2,1,1)=1$ 。注意扩张路径 $(s,a,b,d,c,t)$ 在原来的网络中并不存在，但你可以沿它传送流，因此仍是一道正当的流。

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

应用[编辑]

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

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

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

普遍化及专门化[编辑]

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

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

在最小费用最大流问题（Minimum Cost Flow Problem）中，每条边 $u,v$ 都有特定费用 $k(u,v)$ 。沿这条边传送 $f(u,v)$ 的费用是 $f(u,v)\cdot k(u,v)$ 。目标是要用最低的成本由源点传送一特定数量的流到汇点。

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