正如可以通过将道路交通图模型化为有向图来找到从一个城市到另一个城市之间的最短路径，我们也可以将一个有向图看做是一个“流网络”并使用它来回答关于物料流动方面的问题。设想一种物料从产生它的源结点经过一个系统，流向消耗该物料的汇点这样一个过程。源结点以某种稳定的速率生成物料，汇点则以同样的速率消耗物料。从直观上看，物料在系统中任何一个点上的“流量”就是物料移动的速率。这种流网络可以用来建模很多实际问题，包括液体在管道中的流动、装配线上部件的流动、电网中电流的流动和通信网络中信息的流动。

我们可以把流网络中每条有向边看做是物料的一个流通通道。每条通道有限定的容量，是物料流经该通道时的最大速率，如一条管道每小时可以流过200加仑的液体或一根电线可以经受20安培的电流。流网络中的结点则是通道的连接点。除了源结点和终结点外，物料在其他结点上只是流过，并不积累或聚集。换句话说，物料进入一个结点的速率必须与其离开该结点的速率相等。这个性质称为“流量守恒”，这里的流量守恒与Kirchhoff电流定律等价。

在最大流问题中，我们希望在不违反任何容量限制的情况下，计算出从源结点运送物料到汇点的最大速率。这是与流网络有关的所有问题中最简单的问题之一。我们在本章将会看到，这个问题可以由高效的算法解决。而且，最大流算法中的一些基本技巧可以用来解决其他网络流问题。

本章介绍两种解决最大流问题的一般方法。

• 26.1节给出流网络和流概念以及最大流问题的形式化定义。
• 26.2节描述Ford和 Fulkerson提出的解决最大流问题的经典方法。
• 26.3节给出该方法的一种实际应用:在无向二分图(二分图)中找出最大匹配。
• 26.4节阐述重要的“推送-重贴标签”方法，该方法是许多网络流问题的快速算法的基石。
• 26.5节则讨论推送-重贴标签方法的一种具体实现—“前置重贴标签”算法，该算法的运行时间为O(V^3)。虽然该算法并不是已知算法中最快的，但它演示了渐近最快算法中用到的某些技巧，并且在实际应用中也是非常有效的。

26.1 流网络

给出流网络和流概念以及最大流问题的形式化定义。

在本节中，我们将给出流网络的图论定义，讨论其性质，并精确地定义最大流问题。我们同时还引入一些有用的记号。

流网络和流

流网络G=(V,E) 容量值c(u,v) 源节点s 汇点 t

图 26-1 Lucky 冰球公司货运问题的流网络G=(V,E)。

流f

容量限制

流量守恒

最大流问题

在查看任何网络流问题的例子前，我们简略地对流的定义和流的两种性质进行探讨。容量限制性质说明，从一个结点到另一个结点之间的流必须为非负值且不能超过给定的容量限额。流量守恒性质说明，流入一个结点(指非源结点和非汇点)的总流量必须等于流出该结点的总流量，非形式化地称为“流入等于流出”。

流的一个例子

用流网络把图26-1(a)所示的货运问题模型化。Lucky冰球公司在温哥华有一家制造冰球的工厂(源结点s)，在温尼伯有一个存储产品的仓库(汇点t)。Lucky冰球公司从另一家公司租用货车来将冰球从工厂运送到仓库。因为货车按指定路线(边)在城市(结点)间行驶且其容量有限，Lucky冰球公司在图26-1(a)所示的每对城市u和v之间每天至多运送c(u，v)箱产品。Lucky冰球公司无权控制运输路线和货车的运输能力，因此无法改变图26-1(a)所示的流网络。他们所能做的事情是，判断每天可以运送的最大货箱数p，并按这一数量进行生产，因为生产出来的产品多于其运输能力没有什么意义。Lucky冰球公司并不关心一个给定的小球需安多长时间才能从工厂运送到仓库﹔他们关心的只是每天可以有p箱货物离开工)，母大可以有P相货物到达仓库。

由于从一个城市运送到另一个城市的货箱数量每天都有容量限制，因此可以在这个网络中用流来模拟这种运输“流”。此外，我们的模型必须遵守流量守恒性质，因为在一种稳定的状态下，冰球进入一个中间城市的速率必须等于冰球离开该城市的速率。否则，货箱将在中间城市堆积起来。

使用反平行边来模拟问题

图 26-2 将一个包含反平行边的网络转换为一个等价的但不包括反平行边的网络

反平行

从上面的讨论可以看到，实际生活中的流问题可以自然地表示为一个带反平行边的网络。但如果不允许反平行边则将更为方便。幸运的是，我们有一个非常直接的办法将一个带有反平行边的网络转换为不带反平行边的网络。

26.1-1

Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network GG contains edge (u,v), and we create a new flow network G' by creating a new vertex xx and replacing (u,v) by new edges (u,x) and (x,v) with c(u,x)=c(x,v)=c(u,v). Show that a maximum flow in G' has the same value as a maximum flow in G.

证明:在一个流网络中，将一条边分解为两条边所得到的是一个等价的网络。更形式化地说，假定流网络G包含边(u，v)，我们以如下方式创建一个新的流网络G':创建一个新结点x，用新的边(u，x)和(z，v)来替换原来的边(u，v)，并设置c(u，x)=c(x，v)=c(u，v)。证明:G'中的一个最大流与G中的一个最大流具有相同的值。

Solution

具有多个源结点和多个汇点的网络

图 26-3 将一个多源结点多汇点的最大流问题转换为单源结点单汇点的最大流问题

超级源节点s 超级汇点t

26.1-2

Extend the flow properties and definitions to the multiple-source, multiple-sink problem. Show that any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in the single-source, single-sink network obtained by adding a supersource and a supersink, and vice versa.

将流的性质和定义推广到多个源结点和多个汇点的流问题上。证明:在多源结点多汇点流网络中，任意流均对应于通过增加一个超级源结点和超级汇点所形成的具有相同值的一个单源结点单汇点流中,反之亦然。

Solution

容量限制：对于所有u,v∈V,我们需要0≤f(u,v)≤c(u,v)

流量守恒：对于所u∈V−S−T,我们需要

练习

26.1-4

Let f be a flow in a network, and let α be a real number. The scalar flow product, denoted αf, is a function from V×V to R defined by (αf)(u,v)=α⋅f(u,v). Prove that the flows in a network form a convex set. That is, show that if f1 and f2 are flows, then so is αf1 +(1−α)f2 for all α in the range 0≤α≤1.