英语原文共 114 页，剩余内容已隐藏，支付完成后下载完整资料

---

附录X 译文

网络流

在这一章我们专注于一组丰富的算法问题，这些问题在某种意义上起源于我们在这门课开始时的一个形式化表示问题：二分匹配。

回顾二分匹配问题的提出。一个二部图是一个无向图。它的结点集合可以划分成 ，具有下述性质：每条边有一个端点在X中且另一个端点在Y中。我们常常把二部图画成如图1的样子，X中的结点在左边一列，Y中的结点在右边一列，每条边从左边跨到右列。

现在，我们已经在课程的几个地方看到了匹配的概念: 我们已经用这个概念描述集合上的一组对，这些对具有下述性质：这个集合中没有一个元素出现在两个以上的对中。（想想在稳定匹配问题中与女士（Y）匹配的男士（X），或者在序列比对问题中的字符）。在图的情况下边构成结点

图1 一个二部图 的对，因此我们说在图 中的一个匹配是边的集合，且具有每个结点至多出现在M中的一条边上的性质。如果每个结点恰好出现在M的一条边上，就说边集M是一个完美匹配。

对某些物体分配给其他物体的情况可以用二部图中的匹配建模。我们在前面对图与二部图的讨论中已经看到一些这样的情况。一个自然的例子是：当X中的结点表示工作，Y中的结点代表机器，一条边指出机器能处理工作，那么，一个完美匹配是一种分配方式，它把每项工作分配到一台能处理它的机器上，且具有每台机器恰好分配一件工作的性质。二部图可以表示在两个不同对象之间出现的许多其他关系，例如在顾客和商店之间的关系；或者房屋与附近消防队的关系等等。

组合算法中最古老的问题之一是确定二部图G中最大匹配的大小（作为一个特例，注意到G有一个完美匹当且仅当且它有大小的匹配）。这个问题被证明可以用一个多项式时间运行的算法求解，但是这个算法的开发需要一些与我们至今所看到的技术根本不同的想法。

我们先不直接开发这个算法，而是开始先把某一类一般化的问题——网络流问题形式化，这类问题包括了二分匹配问题作为它的特例。然后，我们对一个一般性的问题，即最大流问题开发一个多项式时间的算法，并且证明它怎样也对二分匹配提供一个有效的算法，而研究网络流问题的初始动力来源于网络的交通问题，我们将看到它们已经被用到各种不同的领域中，不仅对二分匹配，而且对许多其它问题都得到了有效算法。

1 最大流问题与Ford Fulkerson算法

1.1 问题

人们常常用图对交通网络进行建模，交通网络的边输送某一类的交通量且结点起着在不同边之间通过交通的“开关”作用。例如，考虑一个公路系统，其中一边是公路，结点是交叉路口；或者一个计算机网络，其中一边是以发送数据包的链接线且结点是开关；或者一个管网，其中一边是输送液体的管道，而结点是管道被连到一起的接点。这种类型的网络模型有着几个要素：边上的容量，指出它们可以运送多少量；图中的源点，产生交通量；图中的汇点(或者終点），它可以“吸收”到达的交通量；最后，交通量自身要通过边来输送。

流网络 我们将考虑这种形式的图，我们宁愿把交通看做流 ，一种抽象的实体，在源点产生，通过边输送，并且在汇点被吸收。形式上，我们说一个流网络是具有下述特征的有向图

bull; 每条边e关联一个容量，它是一个非负的数，我们把它记作。

bull; 存在单一源点。

bull; 存在单一汇点。

除了s与t之外的其他结点叫做内部结点。

我们将对所处理的流网络提出几点假设：首先

，没有边进人源点s且没有边离开汇点t;

第二，对每个结点至少存在一条边与之连接；

第三，所有的容量都是整数。这些假设使得 图2 一个具有点和汇点

问题考虑起来更淸晰一些，并R忽略了一些 的流网络.边旁边的数是流量

反常的悄况，它们基本上保留了所有我们所考虑的东西。

图2说明了具有四个结点和五条边的流网络容量值在边的旁边。

定义流 下面定义对于我们的网络运送交通或者流的含义是什么。我们说一个s-t流是一个函数f, 它把每条边e映射到一个非负实数；直观上表示由边e携带的流量。一个流必须满足下面两个性质.

(i）（容量条件）对每个，我们有。

(ii)（守恒条件）除了s与t之外，对每个结点v，我们有

这里对进入结点v的所有边上的流值求和，而对离开结点的v所有边上的流值求和。

于是，一条边上的流不能超过这条边的容量。除了源点和汇点以外，对每个其他结点，进入的流量必须等于离开的流量。源点没有进入边（根据我们的假设），但是允许流出来；换句话说，它可以产生流，对称地，汇点允许有流进入，尽管没有边离开它，一个流的值，记作，定义成在源点产生的流量：

为了使得这些记号更为简洁，我们定义与。我们可以把它推广到结点的集合。定义与。按照这个术语，对于结点，t的守恒条件变成，并且我们可以写。

最大流问题 给定一个流网络，一个自然的目标就是安排交通以使得有效容量尽可能得到有效的作用。于是，我们将在下面考虑的基本算法问题是：给定一个流网络，找出一个具有最大值的流。

在我们考虑对这个问题设计算法时，考虑这个流网络的结构怎样限制了s -t流的最大值是有益的。这里对于最大流的存在有一个基本的“障碍”：假设我们把这个图的结点划分成两个子集，A与B，使得且。那么从s到t的任何流直观上必须在某个点从A穿到B，因此用完了从A到B的某些边的容量。这提醒我们，这个图的每个这样的“割”对最大流值设立了一个界，我们这里开发的最大流算法将与证明最大流值等于称之为最小割的任何这种划分的最小容量交织在一起，作为额外的收获，我们的算法也将计算最小割。我们将看到与找最大流的算法一样，从应用的观点看，再一个流网络中找最小容量割的问题原来一样是有价值的。

1.2 设计算法

假设我们想找流网络中的最大流。我们应该怎样着手做这件事？人们做了充分考察断定一种方法，比如动态规划似乎没有效——至少，对于最大流问题还没有已知的算法能够真正被看做天然属于动态规划的典范。由于缺少其他思路，我们可以回过去考虑简单的贪心方法，看看它们的问题出在哪里。

假设我们从零开始：对所有的e，很清楚这不妨碍容量与守恒条件；问题是它的值是0。我们现在试图沿着一条从s到t的路径通过“推”这个流来增加的值，最大到边容量强制的限度。于是，在图3，我们可能选择由边组成的路径，把其中每条边上的流增加到20，并且对其他两条边，保留。以这种方式，我们仍旧遵从容量条件，因为我们只是把流设成边容量允许的那样高。我们也遵从守恒条件，因为当我们增加进入一个内点的边上的流时，我们也增加离开这个结点的边上的流。现在我们的流值是20,我们可以问：这是这个图中最大可能的流吗？如果我们想一想就会看到答案是 “不”，因为可能构造一个值30的流。问题是我们现在被困住了——不存在这样的路径使得我们可以在上面直接推这个流而不超过某个容量——而我们还没有得到一个最大流。我们需要的是从s到t推这个流的更一般化的方法，以使得在类似这样的情况下，我们有一种手段来增加当前流的值。

本质上，我们想要执行由图3中的虚线表示的下述操作。我们沿推10个单位的流；这就导致太多的流进入。因此我们在上“撤销”10个单位的流；这恢复了在的守恒条件，但是导致离开u的流太小。最后，于是我们沿（u,t)推10个单位的流，恢复了在 u的守恒条件。现在我们有了一个有效的流，它的值是30。看图3,那里的粗边输送这个操作之前的流，并且虚线边构成了这类新的增广。

图3 （a）图2中的网络 （b）沿着路径s,u,v,t 推20个单位的流

（c）向后使用边（u,v）的新类型的增广路径

这是一般的推动流的方法：我们可以在边上用剰余的容量向前推，并且我们可以在已经有流的边上向后推，使它转向一个不同的方向。我们现在定义剩余图，它提供一种系统的方法来研究像这样的前后向操作。

剩余图 给定流网络G以及G上的流，我们如下定义G关于的剩余图G (见图4,这是在沿着路径s,u,v,t推20个单位的流以后，关于图3的流的剩余图）

图4 (a) 图G具有来推(a)图G具有用来推第一个20单位流的路s,u,v,t。

(b)结果流f的剩余图，毎条边的旁边是剩余容量。虚线是新的增广路径s,u,v,t。

(c)在沿着新的增广路径推另一个10个单位的流以后的剩余图

bull; 的结点集与G的结点集相同。

• 对G的每条边，其中，那么存在的剰余的容量单位,我们可以尝试在这个容量上向前推流。因此我们在中包含这条边，其容量是。我们将把所包含的这种形式的边叫做前向边。
• 对G的每条边，其中,那么在上面还存在单位的流，我 们只要想做，就可以通过向后推这个流来“撤销”它。因此我们在中包含边，其容量是。注意和有同样的端点，但是它的方向是相反的；我们将把所包含的这种形式的边叫做后向边。

这就完成了剩余图的定义。注意G中的每条边e可以在中产生一条或两条边：如果,它导致一条前向边和一条后向边被包含在中。于是至多有着G的两倍的边。有时候我们将把剩余图中的一条边的容量看做刺余容量，以助于把它与初始流网络 G中对应边的容量加以区分。

在剩余图中的增广路径 现在我们想把在,中从s到t推流的这个方式精确化。令P是中一条简单的路径——即P对任何结点访问不多于一次。我们定义是 P上任何边关于流的最小剩余容M。我们现在定义下面的操作，它在G中产生一个新的流。

我们定义剩余图的操作是完全能执行的；为反映增广（augment)的重要性，人们常常把剩余图中的任何一条s t路径认为是一条增广路径。augment(f，P)的结果是G中的一个新的流这个流是由增加和减少P的边上的流值而得到的。让我们首先验证的确是一个流。

命题1 是G中的一个流。

证：我们必须验证容量条件与守恒条件。

因为与f只在P的边上不一样，我们只需要检査这些边上的容量条件。于是，令（u,v）是P的一条边。通俗地说，容量条件继续保持，因为如果是一条前向边，我们明确地避免把e上的流增加到以上；如果（u,v）是边：产生的一条后向边，我们也明确地避免把e的流减少到0以下。更具体地说，注意到不大于 的剩余容量。如果是

一条前向边，那么它的剩余容量是;于是我们有：

因此容量函数保持。如果是边生的一条后向边，那么它的剩余容量是 ，因此我们有：

容量函数也保持。

我们需要检査在路径P上每个内结点的守恒条件。令v是这样一个结点；我们可以验证进入v的流量改变与流出u的流量改变是相同的；由于f在v满足守恒条件，因此一定满足。从技术上说要检査四种情况，这依赖于P上进人v的边是前向边还是后向边，以及 P上从v出来的边是前向边还是后向边。但是，其中每种情况都是容易处理的，因此我们把它们留给读者。

这个增广操作抓住了我们前面讨论的向前和向后推流的类型。现在让我们考虑下面计算G中一个s-t流的算法。

我们将把它称做算法，它以在1956年两个开发它的研究人员命名。关于这个算法的运行请看图4。的算法实际上相当简单。根本不清楚的是它的核心While循环是否终止，返回的流是否是一个最大流。对这两个问题的回答原来不是那么显而易见的。

1.3 分析算法：终止与运行时间

首先，我们通过在While循环迭代次数上的归纳考虑算法所维持的某些性质，这些依赖于我们关于所有的容量都是整数的假设。

命题2 在算法的每个中间步，流值和中的剩余容量是整数。

证：在While循环的任何迭代之前，这个论断显然是真的。现在假设它在j次迭代后为真。那么，因为在中的所有剰余容量都是整数，对于在j 1次迭代中找到的增广路径，的值将是整数。于是流将有整数值，因此新的剩余图的容量将是整数。

我们可以使用这个性质来证明算法終止。与本书前面的建议一样，我们将寻找一个有关进展的量度，用它来推出终止。

首先证明当我们施用一个增广操作时流值将严格增加。

命题3 令f是G中的流，且令P是中的一条简单的s t路径。那么，；并且由于，我们有。

证 P的第一条边e—定是在剩余中从 s出来的边；由于这条路径是简单的，它不会再次访问s。因为G没有进人s的边，边e一定是前向边。我们通过增加在这条边上的流，并且我们不改变其他关联S的边上的流。因此的值比的值超出 。

为证明终止我们还需要另一个观察：我们要能够界定最大可能的流值。这里是一个上界：如果从s出来的所有的边能够完全用这个流充满，那么这个流值将是令C表示这个和。于是对所有的s-t流，我们有能

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[613619]，资料为PDF文档或Word文档，PDF文档可免费转换为Word