动机
当残量网络中不再存在增广路径时,残量网络方法给出一个最大流。在容量均为整数的情形下,任意选取增广路径的算法会在不超过容量之和这一数值上界的步数内终止。该上界相对于容量的二进制编码位数可能是指数级的。若每次选取一条最短残量路径,则可得到更强的保证,且与容量的大小无关。
该算法通常称为 Edmonds–Karp 算法。它的进展度量并不是流值(当容量为实数时,流值每次可能只增加任意小的量),而是各顶点在残量网络中的广度优先距离。
定义
定义 3.9.1
(有容量的网络与残量弧)
设 为有限有向图,其源点 与汇点 互异,各边容量非负。可行流及其流值的定义与配套的最大流单元相同。每条原图边在其残量容量为正时,分别对应一条正向残量弧和一条反向残量弧。即使相反方向的两条原图边产生了平行的残量弧,也须保留各弧自身的标识。
定义 3.9.2
(最短增广路径、距离与关键弧)
从零流开始。在每一轮迭代中,在当前残量网络上运行广度优先搜索(BFS),并沿一条最短的 – 路径按其正的瓶颈值进行增广。当不存在这样的路径时停止。设 为流 的残量网络中从 到 的 BFS 距离,对不可达顶点取 。若某条弧的残量容量等于路径的瓶颈值,从而在增广后变为零,则称该弧对此次增广而言是关键弧。
定理
定理 3.9.3
(残量距离不会减小)
沿一条最短残量 – 路径增广之后,从 出发到每个顶点的残量距离都不小于其先前的值,其中 规定大于所有有限值。
定理 3.9.4
(多项式增广次数上界)
最短增广路径算法执行 次增广。若采用邻接表,并且先删去原图中从 不可达的顶点,则对于边集非空的情形,在单位代价的精确算术模型下,总时间为 。
证明思路或证明
证明
(残量距离不会减小)
假设某次增广之后有某个距离减小了。在距离减小的顶点中,取新距离最小的顶点 ,并设 为一条新最短路径的最后一条弧。则 ,并且由 的选取可知 的距离没有减小。若弧 在增广之前就已是残量弧,则由旧的最短路径不等式得
与假设矛盾。因此该弧是新出现的残量弧,它是增广所用路径上某条弧 的反向弧。沿旧的最短路径有 。由于 的距离没有减小,故 ,再次产生矛盾。这同时也排除了原先不可达的顶点变为可达的可能。
证明
(每条弧只会成为线性多次关键弧)
固定一条带标识的残量弧 。若它是关键弧,则它被饱和并消失。在这条弧再次成为关键弧之前,某次后续增广必须使用与之配对的反向弧 ,使 重新变为正。在后一次使用该反向弧时,最短路径距离满足 。距离从不减小,而在先前那次作为关键弧被使用时 。因此在这两个事件之间, 至少增加了 。有限的 BFS 距离至多为 ,所以每条带标识的残量弧至多只能 次成为关键弧。每次增广至少含有一条关键弧,而带标识的残量弧至多有 条,由此得到增广次数的上界。
证明透视
关键弧不能很快再次出现
主要的一步是用 BFS 距离而不是流值来衡量进展。距离的单调性依赖一个观察:沿最短路径增广只会产生沿该路径向后指的反向弧,即从距离 指向距离 ,这样的弧不会提供捷径。关键弧的计数还加上第二个要素:当一条被饱和的弧 之后恢复时,它的反向弧 曾在一条最短路径上被使用,所以当时 ;而在饱和之时 。由于 不会减小, 至少上升了二。有限距离至多为 ,所以一条弧至多成为关键弧 次。若没有最短路径的规则,这两个关系都不可用,常见错误一节中的反例显示,增广次数此时可以依赖于容量。
证明
(算法的代价与终止证书)
在原图中从 不可达的顶点,不可能通过残量更新而变为可达:新产生的反向弧连接的是已经位于某条增广路径上的两个顶点。只需一次性删去这些顶点,耗时 。剩下的相关图至多有 个顶点,因此一次 BFS 加一次增广的代价为 。把它与 次增广相结合,即得所述的时间上界。若 被删去,则零流已经是最大流。
终止时不存在增广路径,由配套的最大流最小割定理的证明,可得到一个容量等于流值的割。因此所返回的流是最大流。该论证作为精确算术下的数学算法,适用于实数容量;二进制位复杂度与数值容差则是另外的问题。
例题详解
例题 3.9.5
(一条最短增广路径)
若残量路径 与 同时存在,则 BFS 会先选两条边的路径,而不选三条边的路径。只有当两条路径的边数相等时,它才可能选择其中任一条;容量并不决定 BFS 距离。
例题 3.9.6
(一个关键瓶颈)
若一条残量路径上各弧的容量为 ,则其瓶颈值为 。沿该路径增广 个单位会使中间一条弧饱和,这条弧即成为关键弧。若其他弧的残量容量也等于该最小值,则它们同样是关键弧。
例题 3.9.7
(反向弧可能出现)
沿一条原图边 发送一个单位的流,若该边原本没有反向残量,就会产生一个单位的反向残量容量 。之后使用这条反向弧,相当于抵消原有流的一部分;它并不是一条新的原图边。
常见错误
常见错误
(“最短”指弧数最少,而非瓶颈值最大)
BFS 在度量路径长度时忽略残量容量的大小。一条含两条弧、瓶颈值为 的路径,比一条含三条弧、瓶颈值为 的路径更短。因瓶颈值较大而选择后者,并不是此处所分析的算法。
反例模式
任意的增广路径可能需要很多步
增广次数的界不能去掉最短路径这一规则。设 为正整数。取边 、、、,容量均为 ,再取边 ,容量为 。假设算法交替地沿 增广,以及利用 的反向弧沿 增广。每条这样的路径瓶颈值恰好为一:第一条是因为 ,第二条是因为第一次增广之后反向弧 的残量容量为一。每次增广加一个单位,边 交替地载有一个单位和零个单位,而四条外侧的边各被使用 次。经过 次增广之后流值为 ,这是最大的,因为离开 的边容量总和为 。步数随 增长,对 的比特数而言是指数级的。广度优先搜索则选取 与 ,瓶颈值各为 ,只需两次增广。修正后的说法保留最短路径的规则,这样得到的界与 无关。
常见错误
(流值并不是进展的度量)
对于任意实数容量,流值的严格增加本身并不能限制增广的次数。多项式时间的证明转而追踪关键弧与 BFS 距离。在应用反向弧论证时,必须依据原图边的标识来区分平行的残量弧。
为什么距离不会减小
距离性质的证明比较增广前后两个残量图。仍保持为正的弧原本就已存在;一条弧只有在与之配对的反向弧被增广所用时才会出现。容量可以增大或减小而不改变图中弧的有无,但 BFS 距离只取决于弧是否存在,而不取决于其数值容量。
若存在新的更短路径,取新距离最小的距离减小顶点 。它在某条新最短路径上的前驱 的新距离更小,因而不是距离减小的顶点。若该前驱弧先前已存在,则先沿旧最短路径到达 、再经过该弧,会与 处假设的距离减小相矛盾。若该弧是新出现的,则增广使用了从 到 的相反弧。由于增广路径是最短路径,沿该路径的这条边,旧距离恰好上升 。于是两个不等式迫使 的新距离至少比旧距离大 ,这与“减小”相反。
最短增广路径不含重复顶点:删去含重复顶点的一段会得到更短的路径。最短路径的每个前缀也是到其终点的最短路径,这就说明了沿其各弧的距离关系。当存在多条最短路径时,BFS 的实现可以选择其中任一条;证明并不要求特定的择取顺序。
例题 3.9.8
(残量距离而非容量)
设 BFS 给出距离 、、,所选路径为 。发送流量之后,可能出现一条反向残量弧 。这条新弧由距离 指回距离 ;它本身并不会产生从 到 的更短路线。一般性的证明同时处理所有新的反向弧,而不只是这一条。
仔细计数关键弧
当一条带标识的弧的残量容量变为零时,只有在某次增广使用了与之配对的反向残量弧之后,它才能重新获得容量。若原图在两个方向上各有一条边,它们仍然是两条不同的原图边,各自拥有自己配对的残量弧。属于另一条原图边的、从 到 的弧,并不自动是被饱和弧的配对反向弧。保持这些标识,可以避免把容量的增加归因于错误的边。
设在某次迭代中 是关键弧。沿该次迭代的最短路径,旧距离满足 。当其配对反向弧 之后被使用时,当时的最短路径距离满足 。距离的单调性说明 的后来距离不小于其先前距离。因此 的后来距离至少是其先前距离加 。若此后 再次成为关键弧,单调性保证这一增量得以保持。
增广路径上的顶点是可达的,其距离至多为 。因此,一条带标识的弧的起点距离至多只能增加 次 ,此后该弧就不可能再成为关键弧。对每次增广选取一条关键弧,即把每次增广记在某条弧名下,而每条弧至多被记 次。一条路径上可能有若干个并列的瓶颈,但任取其中一个来记账就已足够。
从路径搜索到总代价
在邻接表形式的残量表示中,每条原图边至多贡献两条带标识的残量弧。BFS 对每条当前可用的弧至多检查一次,并通过前驱指针恢复一条最短路径。增广过程更新该路径上每条弧及其配对反向弧的容量。实现时必须一致地保存这些配对链接,使得抵消流量时修改的是正确的原图边。
若某顶点在原有向图中从 不可达,则从原本可达的顶点集合到它没有原图边。起初它在残量图中不可达。每次增广只使用当前可达的顶点,因此它所产生的任何反向弧也只连接当前可达的顶点。由归纳法,被排除的顶点不会变为可达。删去它们不会消除任何增广路径。若剩余集合含 个顶点,则除 外每个顶点至少由一条原图边到达,故 。
经此预处理后,每次 BFS 与路径更新耗时 。乘以增广次数再加上预处理时间,对非空边集得到 。若不做预处理的改进,则直接得到较宽松的界 。这些界计算的是精确算术与图操作的次数,而不是任意实数的二进制位复杂度。
流值、终止性与证书
每次增广都保持容量约束与流量守恒,因为它沿残量方向加上瓶颈值,并在被反向的原图边上减去瓶颈值。其流值严格增加,但多项式时间的终止性证明并不依赖于存在一个最小的正增量。这正是该结构性论证在数学模型中适用于实数容量的原因,而基于单位增量的整数容量证明则带有对容量的数值上界。
当 BFS 无法到达 时,从 可达的残量顶点构成割的一侧。离开该侧的每条原图边都已饱和;进入该侧的每条原图边上的流为零,否则其反向弧将成为离开该侧的残量弧。该割的容量等于流值。这一对对象是可检验的最优性证书,与增广了多少次无关。
选择最短路径对于距离单调性的证明是必要的。任意的增广路径在终止时可能同样有用且正确,但若不证明相同的距离关系,上述关键弧计数便不能应用于它们。该界也并不意味着瓶颈值最大的路径就是最短的;BFS 所用的是残量弧的条数。
总结
最短残量路径使 BFS 距离非减。在同一条带标识的弧两次饱和之间,必须使用其反向弧,从而迫使其起点距离上升。对由此得到的关键弧上界求和,即证明增广次数为多项式,并结合割证书,得到一个最大流。
练习
快速检查
(不论容量如何,对 BFS 来说,含两条残量弧的路径与含三条残量弧的路径,哪一条更短?)
BFS 数的是弧的条数,而不是容量。
解答 · 答案
含两条弧的路径更短。
快速检查
(增广之后,关键弧的残量容量会怎样?)
把它的容量与瓶颈值比较。
解答 · 答案
它的残量容量变为零,因此会从残量网络中消失,直到它的反向弧被使用而恢复容量。
快速检查
(为什么每次增广都至少有一条关键弧?)
看一看取得最小值的那条弧。
解答 · 答案
一条有限的非空路径中,至少有一条弧的残量容量等于该路径上的正最小值,这条弧会被饱和。
快速检查
(当不再存在增广路径时,用什么证明当前的流为最大流?)
考虑从 可达的顶点。
解答 · 答案
从源点可达的集合定义一个割,它的容量等于可行流的值。由弱对偶性,流是最大的,割是最小的。
练习 3.9.9
(在容量为 、、、、 的网络上运行 Edmonds–Karp 算法。给出每次增广时 的 BFS 距离,并证明最大流的值。)
核心
其余各对顶点之间都没有边。
解答(3)
- 1
沿两条含两弧的路径增广
此时 的距离为 。瓶颈值分别为 与 ,所以这两次增广之后流值为 。残量容量变为: 为 , 为 , 为 , 为 。
依据: 与 都含两条弧,可以先取其中任何一条。
- 2
再次搜索
关键一步
的距离升为 ,这与定理相符。路径 的瓶颈值为 ,所以流值成为 。
依据: 从 出发唯一的残量路线经过 与弧 。
- 3
证明最优性
此时 与 都已饱和,BFS 只能到达 。割 的容量为 ,等于流值,所以最大流的值为 。 的距离依次为 ,没有减小。