动机
一个网络即使从源点流出的总容量足够大,也可能无法把这么多流量送到汇点。在两者之间,总有一些弧构成瓶颈。找到一个较大的可行流,给出的是可运输量的下界;找到一个较小的分隔割,给出的是上界。当两个界相等时,最优性即得证。
真正的困难在于,早先的路径选择有时需要被撤销。残量网络既记录尚未使用的容量,也记录取消已送出流量的可能性。这是沿增广路反转匹配边这一做法在有向图中的类比。若忽略这些取消用的弧,算法可能停在一个远非最大的流上。
定义
定义 7.1.1
(流及其流值)
一个有限有向网络具有互不相同的源点与汇点 ,没有自环,并且每条弧 上有非负容量 。方向相反的弧允许同时存在,且彼此视为不同的弧。可行流为每条弧指定 ,并在除 以外的每个顶点处满足守恒:流入的总流量等于流出的总流量。其流值为
源–汇割是全体顶点的一个划分 ,满足 。其容量为 ;反方向的弧不计入此和。
定义 7.1.2
(残量弧保留其原始标签)
对每条原始弧 ,其正向残量弧方向为 ,容量为 ;其反向残量弧方向为 ,容量为 。搜索时只保留容量为正的残量弧。每条残量弧都记住对应的原始弧,以及应当增加还是减少其流量。因此不同的残量弧可能具有相同的端点,当原始网络含有方向相反的弧时尤其如此。
残量增广路是一条从 到 的简单有向路径。其瓶颈是路径上各弧残量容量的最小值。沿正向弧将原始流量增加该瓶颈值、沿反向弧将原始流量减少该瓶颈值,称为增广。原始容量与原始流量始终属于各自的原始有向弧;反向残量弧只是一条操作指令,并不是新装设的运输弧。
定理/命题
定理 7.1.3
(每个割都给每个可行流提供上界)
对每个可行流和每个源–汇割,
等号成立当且仅当从 到 的每条原始弧都已饱和,且从 到 的每条原始弧上的流量为零。
定理 7.1.4
(残量增广与割证书)
沿残量路径按其为正的瓶颈值增广,会保持可行性,并使流值恰好增加该数值。若不存在残量源–汇路径,则从 可达的顶点构成一个割,其容量等于当前流值。因此当前流是最大流,该割是最小割。
定理 7.1.5
(整数最大流最小割定理)
若所有容量均为非负整数,则存在各弧取值均为整数的最大流,且其流值等于最小割容量。从零流出发,沿任意残量源–汇路径反复增广,至多经过 次增广即终止。当 时,算法立即停止。
证明思路或证明
证明
(在源侧把守恒式加总)
对 中各顶点求“流出减流入”之和。内部弧各以相反符号出现一次而相互抵消。由守恒,除 以外各顶点的贡献均消失,剩下的恰是上式所示的穿过割的净流量。将割容量减去这个净流量,其差等于向外弧上未使用的容量加上向内弧上的流量之和。每一项都非负,由此得到上界及其取等条件。
证明
(增广保持可行性;搜索停顿时得到紧的割)
对于增广:瓶颈不超过路径上任何正向弧的剩余容量,也不超过任何反向弧上已有的流量。因此更新后的所有原始取值都仍介于零与容量之间。路径上每个内部顶点恰有一条残量弧进入、一条残量弧离开。无论某条指令是增加正向弧还是减少反向弧,它都沿残量方向改变该顶点的净流出量。两处改变在内部相互抵消,而源点增加瓶颈值,汇点减少瓶颈值。于是守恒性与流值的结论成立。路径的简单性避免了同一条原始弧在一条路径上被双向使用。
设不存在到 的残量路径,并令 为残量意义下可达的顶点集。汇点不在 中。每条向外的原始弧必须饱和:否则其容量为正的正向残量弧会通向 之外。每条向内的原始弧上的流量必须为零:否则其容量为正的反向残量弧同样会离开 。由第一个定理中的取等条件得 。再由对一切割成立的上界,两个最优性即同时得到证明。
证明透视
从失败的搜索中读出割
关键的一步是:割并非预先选定,而是从残量搜索中读出,即从 可达的顶点集 。两类残量弧各司其职。正向残量弧迫使从 到 的每条原始弧饱和;反向残量弧迫使从 到 的每条原始弧流量为零。两者缺一不可,因为割上界的取等情形有两个条件。
在第一个例题中,沿 送出一单位后,若搜索忽略反向弧,可达集恰为 。它的向外弧 与 都已饱和,所以这个割的容量为二,而流值只有一,因为向内弧 仍载有一单位。正是反向弧 让搜索得以继续。论证通过对一切割成立的上界完成:流值等于 的流不可能被超越,容量等于 的割也不可能更小,所以两者同时是最优的。整数性在此不起作用;它只出现在终止性的证明中,那里每次增广使整数流值至少增加一,而上限 是有限的。
证明
(在源点割的上限下作整数步增广)
最后,从零流和整数容量出发。所有残量容量与瓶颈始终是整数,所以每次增广使整数流值至少增加一。仅由源点构成的割把流值限制在 以内。因此至多发生 次增广,残量搜索终将失败。前面的割证书随即证明整数最优流的存在,以及两个最优值相等。这一论证证明了整数容量下的终止性;它并不能为不受限制的实数容量下任意选路的终止性提供依据。
例题详解
例题 7.1.6
(反向弧修正早先的路径选择)
令 的容量均为一,其中每个两字母标签表示由第一个顶点指向第二个顶点的弧。首先沿 送一单位流。仅用原始弧已找不到第二条路径,但残量路径 存在。其中的弧 取消了先前在 上的那一单位流。结果是一单位经 ,另一单位经 ,流值为二。源点割的容量为二,故最优性得证。
例题 7.1.7
(用割证明低于源点容量的流值是最优的)
取容量 。流 是可行的:顶点 流入三单位、流出三单位; 流入四单位、流出四单位。其流值为六。割 的向外容量为 ,故此流为最大流。源点的总容量为七,那只是一个上界,并未达到。
例题 7.1.8
(数值上的界不一定是输入长度的多项式)
令弧 的容量为 ,弧 的容量为一。反复选择残量路径 与 。第二条路径会取消第一条路径在 上的那一单位流。每一对增广使两条直接支路上的流量各增加一,并使 复原。要达到流值 需要 次增广,而 仅需 个二进制位。对于这些选路方式,终止界是成立的,但相对于编码后的输入长度可能是指数级的。
为什么反向残量容量等于已有流量
正向指令消耗尚未使用的容量,反向指令则撤回已经承诺的流量。人们取消的流量不可能超过先前送出的量,这正是反向容量恰好等于原始弧上已有流量的原因。取消之后,原始流量仍然非负;正向增加之后,它仍不超过原始容量。这两个界就是局部可行性的证明。
当原始网络中还存在反方向的弧时,它提供一个独立的可能操作。走该弧的正向残量弧,是沿那个方向送出新的流量;走相反原始弧的反向残量弧,则是取消旧的流量。两种操作可用的数量可能不同,并且改变的是不同的原始变量。带标签的残量表示能够无歧义地区分它们。在精心设计的实现中也可以合并它们的容量,但证明仍须说明究竟改变了哪些原始流量。
残量图在每次增广之后也会改变。先前不存在的反向弧可能变得可用,先前可用的正向弧也可能因饱和而消失。因此只在初始残量图中搜索,会漏掉合法的修正。搜索针对的是当前流状态的性质。
源点与汇点的记账
流值是源点的净流出量,而不仅仅是流出弧上的流量之和,因为允许有弧流入源点。割恒等式自动处理了这一点。取源侧为除汇点以外的全体顶点,还可说明流值等于汇点的净流入量。其他所有顶点上的守恒性,保证了这两种描述一致。
可行流中可能含有有向环流,它不带来额外的源–汇流值。这样的环流并不能证明存在更大的最优值;它的贡献在每个割上都相互抵消。反过来,最大流不必唯一,其具体的走法也不由最小割决定。该定理等同的是最优值,而不是各个具体的流配置,也不是唯一的瓶颈。
匹配作为单位容量的运输问题
对于二部部分为 的二部图,添加一个源点,向每个左顶点连一条容量为一的弧,并添加一个新汇点,由每个右顶点向它连一条容量为一的弧。把图的每条边从左向右定向,并赋予容量 。一个匹配可以产生一个整数流:沿其每条“源点—左—右—汇点”路径各送一单位流。
反过来,一个整数可行流从任一左顶点流出的至多为一单位,因为进入该顶点的唯一一条弧容量为一。出于类似的原因,进入任一右顶点的也至多为一单位。因此它的取正值的中间弧构成一个匹配,其条数等于流值。整数最大流的存在性由此建立了在所构造的网络中最大匹配大小与最大流值之间的相等关系。
中间弧取较大的有限容量,也使最小割描述出一个顶点覆盖。仅含源点的割容量为 ,所以最小割不可能穿过容量为 的中间弧。于是每条原始边的左端点在汇侧,或右端点在源侧。这些顶点构成一个覆盖,其大小恰好等于由单位边界弧给出的割容量。这给出匹配与覆盖相等的第二条证明路线,并说明有限的较大容量就已足够;不需要真正的无穷大。
概念视角结构
交错路径其实就是残量路径
被选中的匹配边在其中间弧上载有一单位流,所以它的反向残量方向允许撤销这一分配。未被选中的边则允许添加一条。因此一条源–汇残量路径恰好刻画了增广路的重新分配机制。更一般的流框架保留了同一思想,同时允许容量大于一。
初等算法的代价陈述意味着什么
利用邻接表,残量搜索可以在与顶点数加原始弧数成正比的时间内实现,因为每条原始弧至多贡献两条残量指令。将此与整数增广次数的界结合,这一初等方法需要 次运算。参数 是容量的数值,而不是它的二进制长度。
第三个例子表明,这一区别是实际操作层面的,而不只是一个宽松的界。不同的选路规则可以显著改善性能,但这些改进需要进一步的分析。本节的证明建立了正确性、依赖容量的终止界,以及整数最优流的存在性。它并未建立强多项式时间算法。
常见错误
常见错误
(原始路径没有剩余容量便停止)
一条已饱和的原始源–汇路径并不能证明最优。其他路径或残量反转仍可能改进该流:在第一个例题中,送出 后已没有原始路径可用,流值却仍可加倍。同样,一个匹配可能需要通过交换边来改进,而不是直接添加一条边;这两种失败都源于拒绝重新考虑先前的决定。
反例模式
整数容量并不迫使每个最优流都是整数流
令弧 的容量均为一。在 上送一单位流,并沿 与 各送半个单位。这个分数流的流值为一,等于源点割,因此是最大流。仅使用经过 的支路,同样存在整数最优流。整数性定理断言的是整数最优流的存在,而不是每个可行流或最优流都是整数流。
常见错误
(错误计算进入割的弧)
在割的上界中,不要把进入割的弧计为正的容量。它们的流量要从净流值中减去。同样,若向内的弧上仍有正流量,仅有向外弧饱和并不能证明取等;两个取等条件缺一不可。
总结
残量弧同时编码了剩余容量与可逆的决定。增广保持可行性,而一次失败的残量搜索会给出一个恰好等于所达流值的割。整数容量使任意选路的增广必然终止,并给出整数最优流。依赖容量的运行时间与二进制输入下的复杂度是两个不同的论断。
练习
快速检查
(对于容量 、、、、,求一个最大流并列出所有最小割。)
这个四顶点网络中,可能的源侧只有四种。
解答 · 答案
取流 。守恒成立,流值为五。源侧 、 与 的容量分别为五、五与五。其余的可能 的容量为六。对一切割成立的上界证明最大流值为五,枚举则恰好给出这三个最小割。
快速检查
(在匹配的归约中,解释为什么在中间弧上使用容量一仍然能表示匹配的大小,却可能使最小割不能直接给出所述的顶点覆盖。)
考虑只有一条边的图。
解答 · 答案
设只有一个左顶点 、一个右顶点 和边 ,则单位中间容量给出的网络,其最大流为一。源侧为 的割只穿过中间弧,并且是最小割。然而,由汇侧左顶点与源侧右顶点组成的所谓覆盖是空集,因此漏掉了 。取中间容量 即把这个割排除出最小割,从而使覆盖的论证得以恢复。
快速检查
(证明:若一个可行流的流值等于某个割的容量,则每条向外的弧都已饱和,且每条向内的弧上的流量为零。)
解释为什么误差项之间的抵消不会使结论失效。
解答 · 答案
用容量减去割恒等式:其差为 。由可行性,每一项都非负。取等使这个有限和为零,因此每一项分别为零。这里不可能有正项与负项之间的抵消,因为根本不存在负项。于是所述的两个条件成立。