本节讨论网络优化中最大流及最短路径两个核心问题的模型与证书。证明直接使用图论推理;线性规划的界与证书观念有助理解两者的联系。
动机
通讯网络有两个不同问题:每条连线容量有限时,每单位时间最多可传多少数据?每条连线有延迟时,哪条路线总延迟最小?前者容许多条路线同时分流,后者找一条最短路线。快速但狭窄的连线仍可能限制总流量,大容量连线也未必在最短路上。目标不同,便不能沿用同一个直觉答案。
一次贪心选择可能堵塞日后的两条路线。残量网络把已做决策可增加或可撤回的幅度记录下来,修正旧选择便转化成另一个路径搜索,不必全部推倒重来。尤其反向残量弧不是物理上逆向传送,而是账目上取消先前流量。
两种问题都有短证书。流与割的值相等,证明吞吐量最大;路径长度等于可行势能的下界,证明路径最短。检查证书不必重演找出答案的全部步骤,这对大型计算尤其有用。
定义
定义 2.1.1
(有向流、流值及割)
设 是有限有向图,源点 与汇点 不同。每条有标签弧 的容量 有限且非负。可行流满足 ,并在源点、汇点以外每个顶点保持流入总量等于流出总量。流值是源点的净流出量:
割是包含 而不包含 的顶点集 。割容量只加总从 指向补集的弧容量。
原图容许相反方向的两条不同弧,必须保留标签。每条原弧 产生正向残量容量 ,以及从 到 的反向残量容量 ;只有正容量方向才放入残量网络。多条残量弧即使起点终点相同,也可能代表不同原变量的改动,不能不加分辨地合并。
残量网络中由源至汇的路径称为增广路径,其瓶颈是沿路最小残量容量。增广时对正向弧增加这个量,对反向弧所属原流量减去这个量。这个定义把修正方向与原图方向清楚分开。
最短路径问题另给每条弧实数长度 。游走可以重复顶点及弧,长度按使用次数累加;路径不重复顶点。距离势能是一组实数 ,满足 及每条弧上的 。它描述到达顶点的下界,本身还不是一条被选中的路径。
定理/命题
定理 2.1.2
(最大流等于最小割)
有限网络配有限非负容量时,最大可行流存在,其值等于最小割容量。一个可行流最优,当且仅当残量网络没有增广路径。若全部容量是整数,则存在整数最大流。
实数容量也有最大流,但任意选路的增广算法对无理数容量未必有限步终止。下面整数终止论证只直接适用于整数容量;有理容量可先统一缩放。证书成立的条件与某一算法终止的条件要分开。
命题 2.1.3
(最短路径的势能证书)
若 是距离势能,则每个由 到 的有向游走长度至少为 。若一条源汇路径上全部弧都紧,即 ,则该路径长度恰为 ,在所有源汇游走中最短。
全图可行势能排除了任何负长度有向环,因为环上不等式相加会导出零不大于负数。不相关的不可达分量若有负环,也会妨碍全图势能存在。计算源点距离时可先限制于可达顶点;对特定汇点,负环只有在源点能到达它、且它能到达汇点时,才令源汇游走长度向下无界。
证明思路
证明
(割限制流,而可达割取得此界)
把割集 内的守恒方程相加,内部弧互相抵消,得到
故任何割都限制任何流。实际流值要扣除进入割集的流;割容量却只计外向容量,两者不能混淆。
若有增广路径,按瓶颈改动保留每条原弧的容量界。内部顶点的净流出改变量为零,即使使用反向残量弧也一样;源点净流出则严格增加。因此最优流不能有增广路径。
反过来,若无增广路径,取 为残量网络内源点可达的顶点。汇点不在其中。每条离开 的原弧必饱和,否则还有正向残量弧可到达新顶点;每条进入 的原弧必为零流,否则其反向残量弧会离开 。割恒等式遂成等号,流与割同值,证明最优。
存在性也须交代。零流可行,每个流量坐标都被有限容量夹住,而守恒及容量条件形成闭集,所以可行集非空且紧致。连续流值取得最大值,再套用前面的残量网络论证便得到等值割,无须假设算法终止。
整数容量时从零开始,每次增广保持流量及残量容量整数,瓶颈至少一。流值有源点外向容量总和这个有限上界,因此有限步后终止,产生整数最大流。
证明透视
两个剩余事实补上差距
这个证明有四项独立工作:割恒等式对每个流和每个割给出上界;增广说明最大流没有增广路径;可达割给出逆命题;紧致性与整数步长给出存在性及整数性。
关键一步:取 为残量网络中一切可达顶点。 没有向外的正向残量容量,表示外向弧饱和;没有向外的反向残量容量,表示内向弧零流。这正是令割不等式成为严格不等式的两类项。
缺了反向弧会怎样:在第一个例题中,沿 送流后,只用正向弧的可达集是 。它的外向弧 与 都饱和,但内向弧 带一单位,所以流值 严格小于割容量 。这什么也证明不了,而该流确实不是最大。
有限性在哪里用上:存在性用有限多条弧及有限容量令可行集紧致;整数性用有限上界及每步至少增加一。二者都不依赖算法选哪条增广路径。
最短路径证书只需一次伸缩求和。
证明
(把势能不等式伸缩相加)
势能定理把路径各弧不等式相加,中间项抵消,留下 ;全为紧弧时取等号。
这部分不要求弧长非负;非负性只在 Dijkstra 这个特定贪心算法的正确性证明中才需要。回到流的问题,割恒等式也有代数的读法。
概念视角代数
割证书是一组非负误差之和
割容量减净流值,等于外向弧未用容量之和,加上内向弧已有流量之和,每项皆非负。残量可达集令两类误差都为零:外向弧饱和,内向弧零流。这与线性规划对偶差距的模式相同。图论找到令全部误差消失的割,代数则说明局部核验何以保证全局最大。
如何找出距离标签
Dijkstra 方法把源点标签设为零,其他设为无限。每次固定未固定顶点中标签最小者,用其标签加弧长更新相邻顶点,同时记录前驱。
命题 2.1.4
(弧长非负时已固定标签是精确距离)
若每条弧长都非负,则 Dijkstra 方法固定顶点 时,其标签等于由 到 的有向游走的最短长度。
证明
(更短路线上第一个未固定顶点)
已固定顶点的标签是前驱所记录的一条实际游走的长度,所以不会低于真实距离。考虑一条据称更短的路线及其第一个未固定顶点。它的前驱已固定,故松弛操作曾给它不大于该路线前缀的标签。非负弧长保证前缀不长于整条路线,与本次选取最小标签矛盾。
无限标签表示不可达,并非实数势能值。
反例模式
一条负弧就能击败只固定一次的标签法
改用弧长 。Dijkstra 固定 ,给 标签 和 ;固定 后把 设为 。因为 ,它在检查 之前就把 固定为 。但路径 的长度是 。图虽没有有向环,负弧仍破坏非负前缀论证。弧长非负的假设不能删去;相反,势能证书对负弧长依然成立。
有负弧时可用 Bellman–Ford 的分阶段推理:第 阶段记录最多使用 条弧的最佳游走,从上一阶段所有入弧更新。没有可达负环时,删去环不增加长度,所以最多 条弧已足够;再一阶段仍可改善便揭示可达负环。这不是永久固定顶点的贪心证明。
例题详解
例题 2.1.5
(反向弧修正第一次选路)
原弧 容量全为一。先沿 传一单位,若只看未用正向弧,似乎再无可行路线。
残量网络却有 ,其中 是原弧 的反向残量弧。沿此路增广一单位, 的流从一降至零,其余四条原弧各流一。最后是两条普通正向路线 与 ,流值二。割 容量二,证明最优;逆向步骤修正的是旧分配。
例题 2.1.6
(完整核验流与割)
容量依次为 。沿 传二,沿 传二,再沿 传一,得流量向量 。
的流入三等于流出一加二; 的流入二加一等于流出三。源流值五,源点割容量 ,汇点前的割容量也为 ,任一个都证明最大性。
但割 的外向流是 ,还有原弧 进入此集合并带一单位。净跨割流是 。这说明为什么流值公式不能漏掉反向穿越割的流。
例题 2.1.7
(路线与势能给出同一答案)
设弧长 。固定 后, 标签为二、五;固定 后,把 降至三, 设为八;固定 后,把 降至五。
最后势能 在五条弧的差依次为 ,都不超过弧长。前驱路径 全为紧弧,长度五恰等于下界。
常见错误
守恒表示顶点局部收支平衡,不表示每条弧流量相同。流可分合,也可带有不影响源流值的循环。因此即使在同一个图上,最短路线与最大流也需要不同的核验。距离标签同样要逐弧核验,并有路径达到下界;算法中途的暂定值不自动是证书。
常见错误
(把饱和弧永久删除)
残量容量是对现有决策容许的改动,增广后必须重新计算。饱和的正向弧仍可能有正的反向残量弧,日后的增广也可能令正向重新可用。把饱和弧当作永久删除,会失去有效的改进。
常见错误
(指出瓶颈却没有列明顶点集)
看似狭窄的一组弧不一定是割。先列明包含源而不含汇的顶点集 ,再加总所有外向容量。割单独只给上界,还要同值可行流才证明最大。
常见错误
(把整数性误读为唯一性)
整数容量只保证存在整数最优流,并不表示每个最优流都是整数。取单位容量弧 、、、,按此次序记录。整数流 与 都取得最大值 。二者的平均 可行,值也为 ,所以是带分数坐标的最优流。
总结
残量网络记录可逆决策,没有增广路便暴露饱和割;势能记录路径下界,紧弧路径则取得下界。两种证书都由可行对象及相等目标值组成。整数容量、非负长度等算法假设,须与较一般的证书结论分开。
练习
快速检查
(第一例按 顺序列出修正前后原流量,核验两个内部顶点守恒。)
解答 · 答案
修正前是 , 各流入一、流出一。修正后是 ,两个顶点各直接由源接收一,再直接送往汇。反向剩余步骤减少旧 流,不是新增原图弧。
快速检查
(第二例只把 容量改为一,求最大流及最小割。)
解答 · 答案
取流 ,值四。 把流入二分成一加一, 把总流入三送往汇。割 的外向弧是 ,容量总和 。汇点前的割容量也是四。可行流配合任一个同值割,便证明最优。
快速检查
(最短路例提出势能 ,找出失败的弧不等式,给出正确势能及达界路径。)
解答 · 答案
弧 的势能差 大于长度一。弧 的差二是容许的,所以只检查最后一条弧会漏掉错误。正确势能 ,路径 长度 达到下界。
快速检查
(弧长 ,证明源汇游走长度向下无界。若删去 后再无弧到达 ,结论如何?)
解答 · 答案
环 长度负一。先从 到 ,绕环 次,再沿 到汇,总长 ,趋向负无限。删去唯一入汇弧后,汇不可达,根本没有源汇游走。可达负环不能凭空创造到汇的路线。
快速检查
(证明可行势能也是任何非负单位源汇流的成本下界,即使该流分散于多条路线。)
解答 · 答案
把每条 乘以非负流量后相加。内部势能系数因守恒抵消,源的单位净流出及汇的单位净流入留下 。故总成本至少为 ;不用先把流分解成路径,这已展示最短路线性规划对偶的核心。