流量算法改变各条弧的流量时,必须维持每个节点的平衡。生成树提供清晰的记账方法:固定非树弧流量后,树弧流量便被唯一决定。加入一条非树弧恰好产生一个环,因此只需追踪一条路径,就能找到整个可行方向。本节在连通有限网络上推导精确算术的主元规则。
树表示
设 是有限连通有向多重图,没有自环;平行弧和相反方向的弧各有独立标签。节点—弧关联矩阵 在弧的起点记 、终点记 。可行流满足 及有限界限 ,其中 。因此 是流出量减流入量,必有 ;成本是 。
定义 26.1.1
(树解)
选底层无向图的一棵生成树 。 的树解把每条非树弧固定在一个界限( 或 ),再由节点平衡 求出树弧流量。所得树弧流量均在界限内时,称此树解为可行。
树弧本身可以在界限上:这是退化树解,并非丢弃该树的理由。上下界相等的非树弧已固定,不能进入基底。
定理 26.1.2
(树上平衡唯一决定流量)
对任意已选的非树弧流量及总和为零的 ,恰有一组实数树弧流量满足 。
证明
(逐一消去叶节点)
从 减去非树弧的贡献,得到总和仍为零的剩余平衡。在树的叶节点,唯一相接的树弧流量由该节点平衡唯一决定,符号视弧方向而定。移除叶及其弧,并按该流量的贡献更新相邻节点的剩余平衡。更新后剩余平衡总和仍为零。重复至只剩一点,其平衡自动成立。这构造出一组解;每次叶节点方程都迫使所选值唯一,故解唯一。只有所求值均落在各自区间内,此解才可行。
概念视角代数
生成树就是关联矩阵的基
的每一列恰有一个 和一个 ,所以 各行之和为零,每一列都位于维数为 的子空间 内。上述定理说: 条树弧对应的列把系数双射地映到 ,即它们构成 的一组基,因而 正是 的列空间。反之,含无向环的弧集合,其列线性相关,因为沿环带符号相加的列之和为零。所以 的基恰好是生成树的弧集合,而树解正是有界线性规划的基本解:树弧是基变量,非树弧是停在界限上的非基变量。
价格、方向与比值测试
选节点价格 ,使每条树弧 都满足 。可任选一个价格,沿树推算其余价格。每条弧的约化成本记作 。处于下界的非树弧只能先向前增加,其成本斜率为 ;处于上界的则只能先向后减少,斜率为 。因此候选改善弧是在下界而 ,或在上界而 的非树弧。
常见错误
(判断改善符号时忽略界限状态)
常见做法是只让 的弧进入。这条规则只适用于处于下界的非树弧。处于上界的弧只能减少,斜率是 ,所以 时才是改善。下面第二个例题中, 为正,但 正是应进入的弧。
要找配合它的树弧变动,先把进入弧加入 ,得到唯一无向环。若进入弧由下界增加,令其系数 ;若由上界减少,令 。为环上树弧指定 或 ,使 ,其他系数为零。等价地,沿进入弧选定方向前进,再沿唯一树路径返回:行进方向与原弧方向相同记 ,相反记 。
命题 26.1.3
(环方向的斜率等于进入弧的约化成本)
设价格 使每条树弧 都有 ;设 是非树弧, 是它的环方向:、,且环外每条弧 都有 。则
证明
(把成本写成约化成本减去价格差)
由 的定义,每条弧 都有 ,而 是 的第 个分量。因此
因为 。余下的和中,环外 ,环上树弧 ,只剩进入弧一项,故 。
证明用了两种不同的抵消,值得分开来看。
证明透视
为何整个斜率由约化成本决定
假设在哪里用上:条件 消去价格项,树价格消去环上其余的弧。第一种抵消完全不用到树:对任何循环方向及任何价格,都有 ,因为循环流看不见价格差。树只用来令这个环上其他弧的约化成本为零。
关键一步:以 取代 ;这改变每条弧的成本,却不改变任何环的成本。
缺了什么会出错:沿用旧树的价格,在当前树弧上未必为零,单一弧的测试便会报错斜率。例如第一个例题主元之后,旧价格 给新树弧 的约化成本是 。
如何收尾:命题只给出斜率的符号,并未保证成本下降。若下面的步长为零,成本根本不变。
最大可行步长 是所有 的环弧之 ,与所有 的环弧之 的最小值。进入弧也要纳入最小值。令 。若某树弧到达界限,它可以离开;以进入弧代替它后仍是生成树,因为移去的边位于新环上。其他同时到界的树弧可留在树内。若只有进入弧到达另一界限,保留原树,让该弧在另一界限继续作非树弧;这称为界限翻转。若两类弧同时到界,可选合适的树交换或界限翻转。
常见错误
(把所有同时到界的树弧都移走)
若几条树弧同时到界,只能有一条离开。 个节点的生成树有 条弧,而只有一条弧进入;移走两条便不足以连通所有节点。第一个例题中两条树弧都降到零,若全部移走,三个节点上只剩 一条弧。其余同时到界的弧以界限值留在树内,这正是退化树解。
瓶颈为零时,基底改变但流量及成本不变。所以单凭负斜率,不能断言当前流量不是最优。实际有限算法需要明确的平手处理或防循环规则;以上局部步骤本身不证明终止。这里的成本及界限均按精确数值处理,不涉及浮点容差。
树主元与证书
例题 26.1.4
(负约化成本令一条树弧离开)
节点 间有弧 、、,成本 ,下界均为零、上界均为三;平衡为 。以前两条弧为树,取 ,成本 。令 ,树方程给出 、。非树弧约化成本为 。
增加 并沿树路径 返回,得 ,故 。新流量 的成本为 ,下降 。两条树弧都到零;移去 ,把零流量的 留在树中。新树价格为 ,唯一非树弧约化成本是 。
对任意可行 ,。树弧约化成本为零,而 且 ,所以 。新流量达到此下界,故最优。保留零流量树弧是维持这个树表示所必需的。
例题 26.1.5
(上界弧可反向进入并翻转界限)
保持上述平衡及树,但用成本 、上界 ,由 开始,成本为 。树价格 给出 。因 位于上界,减少它:,成本斜率是 。容量最小值为 。只有进入弧到界,所以树不变, 翻转至下界。结果 成本为 ;不变的价格证明最优,因为下界处的 。
例题 26.1.6
(步长为零的退化主元)
沿用第一个例题的网络(成本 、界限 ),但所有平衡为零,即求最便宜的循环流。取树 及 ;两条树弧都在下界。价格仍是 ,而下界处 ,所以方向 的斜率为 。
比值测试给出 :树弧不能再减少。让 离开, 以零流量进入。流量和成本 都不变。新树 的价格是 ,下界处 ,所以新的表示证明了最优性。
直接看,节点 的平衡是 ,而 ,所以唯一可行流是零。第一棵树表示的流量本已最优,却通不过符号测试:证书失败只说明需要换基,并不表示流量可以改善。
反例模式
比值测试不能遗漏进入弧
第二个例子若只看树弧,会得到步长 ,但这会使 由 降至 ,违反下界。进入弧本身的剩余区间把合法步长限制为 。
每个例题最后得到的符号模式,是一个一般的证书。
定理 26.1.7
(约化成本最优性证书)
设 是生成树 的可行树解,价格 使每条树弧都有 。若每条 的非树弧,在 时有 ,在 时有 ,则 在所有可行流中使 最小。
证明
(逐条弧与任意可行流比较)
设 可行。与斜率命题一样,,而 。因此
树弧项为零。下界处的非树弧有 及 ;上界处的有 及 。固定弧有 ,不论约化成本如何都贡献零。每一项均非负,故 。
这些符号是当前可行流的证书;对固定的树,定理没有逆命题:退化例题正好给出一个最优流,其树表示却通不过测试。
练习与解答
快速检查
(在第一例改为移去 (而非 )。求新价格并检查最优性。)
新树由 和 组成。
解答 · 答案
树弧是 和 。令 ,则 、。非树弧在下界且 ,原成本 仍是最优。
快速检查
(在第二例把直达弧上界由 改为 ,但保留流量 。同一棵树下它仍是树解吗?)
比较非树弧流量与其界限。
解答 · 答案
不是。直达非树弧流量 严格位于新界限 和 之间。流量虽仍可行,却不符合此树及界限状态的树解定义。
快速检查
(某环方向系数为 ,当前流量为 ,界限为 。求步长及所有到界的弧。)
在 处用 ,在 处用 。
解答 · 答案
三个允许改变量为 、、,所以 ;只有第三条弧到达其上界。
快速检查
(非树弧有 和约化成本 。这会令价格证书失效吗?)
想想这条弧在可行流中可以取什么值。
解答 · 答案
不会。每个可行流在该固定弧上的值相同,因此它对成本差贡献零,也没有可行的进入方向。