关于去除《算法导论》中介绍的前置重贴标签算法的反平行边限制的方法、实现细节与正确性证明

Piwry · 2025-10-22 18:31:18 · 算法·理论

前言

一直没自己实现过最大流，出于偏好写的第一个最大流算法选用了《算法导论》的“前置重贴标签算法”，并且也采用了《算法导论》给出的实现方式。但是《算法导论》中对流网络的定义要求不能有反平行边（即同时存在 (u, v), (v, u)）；虽然存在对复杂度影响为常数级别的转换为等价图的方法（把每个结点 u 复制一份 u'，然后每条边 (u, v) 转化成 (u, v'), (v', v) 两条边即可），可偏偏就是这个常数让我过不了最大流加强版的板子...

于是基于《算法导论》的原始算法和证明，自己又研究了一下，成功魔改出一个不增加常数直接兼容反平行边的做法，并且稍微整理了下实现细节和需要对《算法导论》原复杂度/正确性证明打补丁的地方，发布于此，希望能帮助同样照着《算法导论》写的有此疑惑的人 qaq。

可能思路会有些笨拙，也可能会有因疏忽而不严谨的地方，抛砖引玉，还望读者海涵 QAQ（叠甲）。

（另注：以下具体采用的参考书为《算法导论》第三版。本文非常需要配合原书籍阅读！本文完全采用原书记号；出于篇（省）幅（事）原因，原书已有的定义和引理会被直接略去。）

（注2：如果需要，可以从 这里（提取码 rdki；解压码 PiwryFlow）获取本文所涉及的原书章节。）

对定义的修改

列表中“（p...）”指的是该定义对应的原书页码。

注意到，核心在于对流 f 的容量限制的定义的修改，以及对流 f 添加的新限制 f(u, v)=-f(v, u)；这相当于将 v 到 u 的反向流直接“体现在” f(u, v) 中了。至于其余定义的修改只需基于此照葫芦画瓢地更改，使其含义（模型？）契合原定义即可。

1. （p414）我们允许流网络 G=(V, E) 出现反平行边，即 (u, v), (v, u) 可以同时被包含于 E 中；但是仍然不允许重边。
2. （p415）我们修改流 f:V\times V \rarr R 定义中的容量限制为：对于所有的结点 u, v\in V，要求 -c(v, u)\leq f(u, v)\leq c(u, v)。
3. （p415）我们为更改流 f 的一个限制，这个限制原本是：当 (u, v)\not\in E 时，f(u, v)=0。我们更改为：当 (u, v)\not\in E 且 (v, u)\not\in E 时，f(u, v)=0。
4. （p415）我们为流 f 另添加一个限制：对于所有的结点 u, v\in V，要求满足 f(u, v)=-f(v, u)。
5. （p415）我们修改流 f 定义中的流量守恒为：对于所有的结点 u\in V-\{s, t\}，要求 \sum\limits_{v\in V}f(u, v)=0=\sum\limits_{v\in V}f(v, u)。
6. （p415）我们修改流值 |f| 的定义为：\begin{aligned} &|f|=\sum\limits_{v\in V}f(s, v) &(26.1)\end{aligned}。
7. （p419）我们修改残存容量 c_f(u, v) 定义为：\begin{aligned} &c_f(u, v)=\left\{\begin{aligned}&c(u, v)-f(u, v) &\text{if } (u, v)\in E \text{, or } (v, u)\in E \\ &0 &\text{Otherwise} \end{aligned}\right. &(26.2)\end{aligned}（且可以注意到，如此修改后，对任意 u, v\in V，仍然满足 c_f(u, v)\geq 0）。
8. （p419）我们修改流 f' 对流 f 的递增 f \uarr f' 的定义为：\begin{aligned} &(f\uarr f')(u, v)=\left\{\begin{aligned}&f(u, v)+f'(u, v) &\text{if } (u, v)\in E \text{, or } (v, u)\in E \\ &0 &\text{Otherwise} \end{aligned}\right. &(26.4)\end{aligned} 。
9. （p422）我们修改横跨切割 S, T 的净流量 f(S, T) 的定义为：\begin{aligned}&f(S, T) =\sum\limits_{u\in S}\sum\limits_{v\in T}f(u, v) &(26.9)\end{aligned}。
10. （p431）我们修改预流 f 的（弱化了的）流量守恒性质的定义为：对于所有的结点 u\in V-\{s\}，\sum\limits_{v\in V}f(v, u)\geq 0。
11. （p431）我们修改超额流 e 的定义为：\begin{aligned} &e(u)=\sum\limits_{v\in V}f(v, u) &(26.14) \end{aligned}。
12. （p432）PUSH(u, v) 的伪代码需要修改，具体见本节后文的“对 PUSH(u, v) 的修改”。可以注意到如此修改后，PUSH(u, v) 同样能保证 f 的容量限制，并且也能保证 f(u, v)=-f(v, u) 的性质。
13. （p433）INITIALIZE-PREFLOW(G, s) 的伪代码需要修改，具体见本节后文的“对 INITIALIZE-PREFLOW(G,s) 的修改”。
14. （p434）我们对由 INITIALIZE-PREFLOW(G,s) 创建的初始预流 f 的定义公式需要修改，修改为：\begin{aligned} &(u, v).f=\left\{\begin{aligned}&c(u, v) &\text{If } u=s \\ &-c(v, u) &\text{If } v=s \\ &0 &\text{Otherwise} \end{aligned}\right. &(26.15)\end{aligned} 。

对 PUSH(u, v) 的修改：

PUSH(u,v){
    // Applies when: u is overflowing,c_f(u,v)>O, and u.h=v.h+l.
    // Action: Push delta_f(u,v)=min(u.e,c_f(u,v))units of flow from u to v.
    delta_f(u,v)=min(u.e,c_f(u,v))
    (u,v).f=(u,v).f+delta_f(u,v)
    (v,u).f=(v,u).f-delta_f(u,v) 
    u.e=u.e-delta_f(u,v)
    v.e=v.e+delta_f(u,v) 
}

对 INITIALIZE-PREFLOW(G,s) 的修改

INITIALIZE-PREFLOW(G,s){
    for each vertex v belongs to G.V
        v.h=0
        v.e=0
    for each edge (u,v) belongs to G.E
        (u,v).f=0
    s.h=|G.V|
    for each vertex v belongs to s.Adj
        (s,v).f=c(s,v)
        (v,s).f=-c(s,v) // here added one line
        v.e=c(s,v)
        s.e=s.e-c(s,v)
}

正确性证明（证明重写）

大部分原来的证明是兼容我们修改后的定义的。这里只对不兼容的证明进行重写。

对 引理 26.1 的重新证明

引理 26.1 设 G=(V,E) 为一个流网络，源结点为 s，汇点为 t，设 f 为 G 中的一个流。设 G_f 为由流 f 所诱导的 G 的残存网络，设 f' 为 G_f 中的一个流。那么 式 (26.4) 所定义的函数 f\uarr f' 是G的一个流，其值为 |f\uarr f'|=|f|+|f'|。

容量限制部分：

对于容量限制，注意到，对于下界：

此外，对于上界：

流量守恒限制部分：

对于所有的结点 u\in V-\{s, t\}，我们有：

值计算部分（直接展开项，甚至比原证明更简单了）：

对 引理 26.4 的重新证明

引理 26.4 设 f 为流网络 G 的一个流，该流网络的源结点为 s，汇点为 t，设 (S,T) 为流网络 G 的任意切割，则横跨切割 (S,T) 的净流量为 f(S,T)=|f|。

对于任意结点 u\in V-\{s, t\}，重写流量守恒性质如下：

类似原证明，根据式 (26.11) 对 |f| 的定义，并将式 (26.11) 左面的项加进来，针对所有结点 S-\{s\} 进行求和，并将右面的求和项展开并重新组合，我们得到：

因为 V=S\cup T 且 S\cap T=0，我们可以将上述表达式中针对集合 V 的求和分解为针对 S 和 T 的求和，得到：

对 推论 26.5 的重新证明

推论 26.5 流网络 G 中任意流 f 的值不能超过 G 的任意切割的容量。

设 (S,T) 为流网络 G 的任意切割，设 f 为 G 中的任意流。根据 引理 26.4 和容量限制性质，我们有：

对 定理 26.6 的重新证明

定理 26.6（最大流最小切割定理） 设 f 为流网络 G=(V,E) 中的一个流，该流网络的源结点为 s，汇点为 t，则下面的条件是等价的：

2. 残存网络 G_f 不包括任何增广路径。