动机
一个网络即使从源点流出的容量十分充裕,最终送达终点的流量仍可能很少:下游某处的瓶颈可能限制了每一条路线。流为各条边分配相互兼容的流量,而割则给出对所有可能的流的一个上界。残量网络把这两种观点联系起来:它既告诉我们如何改进一个候选流,也告诉我们为什么不再有可改进之处。
定义
定义 3.1.1
(流、流值与割)
设 为有限有向图, 与 为互不相同的源点和汇点,容量 。为简单起见,每个有序点对只使用一条有向边;允许存在方向相反的有向边。流为每条边指定 ,并在 以外的每个顶点满足守恒:流入量等于流出量。流的值是 处的净流出量。– 割是满足 、 的划分 ;其容量是原图中从 指向 的各条边的容量之和。
定义 3.1.2
(残量网络与增广路径)
对于原图中的每条边 ,残量网络含有一条容量为 的正向弧和一条容量为 的反向弧,并且只保留容量为正的弧。反向弧表示可以抵消先前已送出的流,并不是额外的原始容量。若方向相反的原始边产生了平行的残量弧,须保留它们各自的身份:沿其中一条弧增广,修改的是它自己对应的原始边。增广路径是残量网络中的一条有向 – 路径;其瓶颈是该路径上残量容量的最小值。
定理
定理 3.1.3
(流–割等式与最优性)
对每个可行流 和每个 – 割 ,都有 。一个可行流是最大流,当且仅当其残量网络中没有增广路径。此时,残量网络中从 可达的顶点给出一个容量为 的割。
定理 3.1.4
(整数增广)
若所有容量均为非负整数,则从零流出发,沿任意残量路径按其瓶颈反复增广,必在有限步后终止,并得到一个整数最大流。若 为离开 的各边容量之和,则增广至多进行 次。这个界取决于 的数值大小,不一定是其二进制编码长度的多项式。
证明思路或证明
证明
(弱对偶性:每个割都是每个流的上界)
对 中除 以外的所有顶点求守恒式之和。内部的边相互抵消,得到 。这就证明了弱对偶性:任何割都是任何流的上界。
证明
(沿残量路径增广)
沿残量路径,使用正向弧时增加相应原始边的流量,使用反向弧时则减少。瓶颈保证每条被修改的边的流量仍在其界限之内。路径上每个内部顶点接收与送出的增量相同(包括某条弧抵消一条原始边的情形),所以守恒依然成立,而流的净值恰好增加瓶颈的大小。因此,存在增广路径的流不是最大流。
证明
(没有增广路径便得到容量相等的割)
若不存在这样的路径,令 为可达顶点的集合, 为其余顶点。每条从 指向 的原始边都是饱和的,否则其正向残量弧会到达 。每条从 指向 的原始边流量为零,否则其反向残量弧会到达 。于是割的恒等式化为 。由弱对偶性可知, 是最大流,而这个割是最小割。这同时也证明了逆命题:最大流没有增广路径。
证明透视
一份证书,而非猜测
最优性的证明把失败的搜索转化为一个割。从 可达的顶点集合 按构造对残量弧封闭,而唯一用到的就是这个封闭性:没有正容量的残量弧离开 。逐条边展开它,便得到所需的两个等式。若原图中从 到 的边还有剩余容量,就会有一条正容量的正向弧离开 ,所以每条这样的边都是饱和的。若从 到 的边带有正流量,就会有一条正容量的反向弧离开 ,所以每条这样的边流量为零。恒等式 于是成为 。由守恒证明的弱对偶性完成论证:没有流可以超过这个割,也没有割可以低于这个流。若没有反向弧,第二个等式就会失去,搜索可能停在并非最大的流上,这就是为什么抵消例子中的早期选择必须可以撤销。
证明
(整数容量保证终止)
对于整数容量,初始的零流是整数流,且所有残量容量始终保持为整数。每次增广的瓶颈为正整数,使流的值至少增加一。割 把流的值限制在 以内,所以该过程至多经 次迭代就会停止,最优性随之成立。若以广度优先方式选取最短增广路径,则存在与容量数值无关的多项式界,但这一单独的界在此不予证明。
例题详解
例题 3.1.5
(两条路线与一个瓶颈)
设容量为 、、、、。沿 送出 ,沿 送出 ;再沿 送出 。该流的值为 。割 的容量为 ,由此证明该流是最优的。
例题 3.1.6
(抵消早先的选择)
设 、、、、 的容量均为 。若第一条路径取 ,则从 经 的直接正向路线已经饱和。残量路径 使用了 的反向弧。增广时抵消该边上的流,最终在 与 上各留下一个单位的流。所得的值 等于以源点为界的割的容量。
例题 3.1.7
(含有反向边的割的界)
设某个割的正向容量为 ,当前正向流为 ,同时还有 个单位的原始流从 流回 。它对流的值的净贡献是 ,而不是 。若只累加正向流,就会高估流的值。即使最优流恰好在其证明用的割上没有反向流,这个恒等式仍然同时包含两个方向。
常见错误
常见错误
(残量容量不等于原始容量)
即使原图在某个方向上没有边,也可能出现容量为一的反向弧。它允许抵消先前送出的一个单位流,却不允许在并不存在的边上送出无限的新流。
反例模式
任意增广路径可以用尽整个界
考虑这样的说法:沿任意残量路径增广,所需步数对输入的大小而言只是多项式的。设 为正整数。取边 、、、,容量均为 ,再取边 ,容量为 ,于是 。交替地沿 与沿 增广,后一条路径使用 的反向弧。每条路径的瓶颈值都是一,每次增广恰使流值增加一,而流值 要经过 次增广才能达到。界 被达到了,步数随 增长,对 的比特数而言是指数级的。修正后的说法限制路径的选择,例如只取广度优先的最短路径,其多项式界是另一个结果。
常见错误
(所选路径被堵住并不表示没有路径)
仅因目前所选的路径被堵塞就停止是不够的:另一条残量路径可能会重新安排先前的选择。算法必须搜索整个残量网络。对于实数容量,弱对偶性和“无路径”证书仍然有效,但整数情形的终止性证明不适用于任意的路径选择。
从过程到证书
残量搜索不仅应记录某个顶点已被到达,还应记录到达它所经的前驱弧。若到达了 ,从 沿前驱回溯至 即可得到一条路径及其瓶颈。若搜索结束时仍未到达 ,则其访问过的集合恰好是最优性证书中的 一侧。无论哪种情形,同一次搜索都给出证明所需的下一个对象。须小心保留每条残量弧的身份与方向,尤其是在原图中两个方向都有边的时候:从 到 的一条弧,既可能增加 的流,也可能抵消某条 上的流。
例如,若 、、、,则从 到 有两种残量机会:把第一条边的流最多增加 ,或把第二条边的流最多抵消 。它们端点相同,但更新方式不同。只有当实现在更新原始边时同时选取了一种合法的分解,才可以把它们的数值容量合并。保留带标记的平行弧可以避免这项额外的记账工作。
割的恒等式也说明了等式成立需要什么条件。在
中,正向求和里的每个差 以及每个反向流都是非负的。等式成立当且仅当所有正向割边都饱和,且所有反向割边的流为零。这个条件可以对任意给定的可行流和割证明最优性,而无须假定该流是如何构造出来的。它也解释了可达性割为何有效:若有一条容量为正的残量弧从 跨向 ,就会与 的定义相矛盾。
例题 3.1.8
(流与割作为相互独立的证书)
考虑容量 、、、、。依次指定流量 。在 处,所设的流入量为 ,而流出量为 ,所以这一指派根本不是流。将 增加到 即可修正。此时流的值为 ,且守恒成立:在 处 ,在 处 。割 的容量为 ,所以修正后的流是最大流。若先检验割而不检验守恒,原先的错误就会被掩盖。
建模的限制
容量是上界,并不是要求每条边都必须被使用。守恒只适用于中间顶点,源点和汇点可以既有入边又有出边;这正是把流的值定义为“净”流出量的原因。沿有向圈的一个正环流会改变各条边的流量,却不改变流的值。因此,即使最大值是唯一的,最大流也不一定唯一。最优解也不必用到每一条可用的边。
定理允许容量为零,也允许零流。若不存在容量为正的从 到 的有向路径,则初始的残量搜索会得到容量为零的割,而零已经是最优值。反过来,即使存在路径,流的值也可能很小:路径存在只保证有某个正的增广量,并不限制总量。对于整数数据,界 在最坏情形下计数增广的次数;若容量以二进制编码, 位的数可以大到 。因此,仅凭这个界不能确立关于输入长度的多项式运行时间。
应用:二分图匹配
对于左顶点集为 、右顶点集为 的二分图,构造如下网络:从 到每个左顶点连一条单位边;对图中的每条边,从 到 连一条有向单位边;从每个右顶点到 连一条单位边。这里的整数流可以分解为被选中的左–右边:由守恒以及源点、汇点处的单位边可知,没有任何顶点被使用超过一次。反之,对匹配中的每条边,沿 送出一个单位的流。因此最大流的值等于最大匹配的大小。整数性定理对于把边上的流解读为真正的“选或不选”的匹配决定至关重要;一般的分数可行流不能直接称为匹配。
例如,取 、,边为 –、–、–。若先选 –,可能会堵住 的直接选择。残量路径 抵消先前的 – 选择,改为 – 与 –。这就是匹配版本的流重新安排。仅含 的割容量为二,这证明所得大小为二的匹配是最优的。
检验一个给定的解
一种实用的检验顺序是:先检查边的界限,再检查守恒,再检查所声称的值,最后才与割比较。这四个步骤缺一不可。若某个流的值大于所给出的割,那它不可能是弱对偶性的反例:这几项检查中至少有一项失败了。对于数值证书,应写出每条边上的流(包括为零的),并列出割上所有按正向穿越的原始边。反向穿越的边进入流的恒等式,却不计入割容量的定义。要成为值相等的证书,它们的流实际上必须为零。
残量路径是由残量弧组成的序列,不一定是由正向原始边组成的序列。只要有任一残量游走到达汇点,就能找到一条简单路径,因为游走中重复的顶点可以去掉。如果某条路径使用了一条对应于已载有三个单位流的边的反向弧,增广就不能抵消超过这三个单位。若同一路径上其余各弧的残量容量最小为二,则瓶颈为二,所以算法使每条弧改变二,被抵消的边仍留下一个单位。选取更大的增量会违反至少一个容量或非负性约束。
整数增广的界并不要求每条边的流各自单调增加。反向残量弧可以减少先前指派的流,如匹配例子所示。单调增加的是整个流的“净值”。由于该值是整数,而固定的割给它设了上界,这个单调的量就足以证明终止性。这是算法中常见的证明模式:确立进展的势函数,可以不同于每一步所修改的局部变量。
最后,最小割命题还提供灵敏度信息。如果某个割的容量为六,那么给不穿越该割的边增加容量,其本身不可能使最大值超过六,因为同一个割仍然是上界。增加穿越某个最小割的边的容量可能会提高这个界,但并不保证最大值上升:另一个最小割可能保持不变。在断言有所改进之前,应重新计算,或给出新的值相等的流–割证书。
总结
流的守恒使每个割都成为上界。残量路径改进可行流,而这类路径的不存在则构造出容量相等的割。整数容量保证整数流以及有限的增广过程,其迭代次数的界可能是伪多项式的。
练习
快速检查
(在第一个例子中,验证三次增广全部完成后 与 处的守恒。)
把进出每个顶点的边上的流量分别相加。
解答 · 答案
在 处,流入量 等于流出量 。在 处,流入量 等于流出量 。所有使用到的边上的流量都符合各自的容量。
快速检查
(某可行流的值为 ,某个割的容量为 。可以得出什么结论?为什么?)
分别与弱对偶性比较。
解答 · 答案
由弱对偶性,每个流都以 为上界,每个割的容量都不小于 ,所以所给的流是最大流,所给的割是最小割。
快速检查
(容量均为整数且 时,沿任意路径增广的算法至多能执行多少次增广?)
每次增广使整数流值至少增加一。
解答 · 答案
至多 次:每次增广使整数流的值至少增加一,而源点割把流的值限制在 以内。
快速检查
(某网络中 的容量为 , 的容量为 ,没有其他边。求一个最大流和一个最小割。)
找出唯一路径上的瓶颈。
解答 · 答案
沿该路径送出 个单位的流。割 的容量为 ,证明了最优性。源点边未使用的 个单位容量无法穿过瓶颈。