用线性规划对偶性证明最大流最小割定理

发表于 分类于

最大流最小割的优化证明。

我们先写出线性规划形式的最大流：

在满足以下两组条件的前提下：

∀p∈P(S,T),∑e∈pfp≤ce∀p∈P(S,T),fp≥0\forall p\in P(S,T),\sum_{e\in p} f_p\le c_e\\ \forall p\in P(S,T),f_p\ge 0

最大化：

∑p∈P(S,T)fp\sum_{p\in P(S,T)}f_p

设这个流网络图为 G=⟨V,E⟩G=\langle V,E\rangle，而 S,TS,T 分别为 GG 的源汇点，P(S,T)P(S,T) 为 GG 中所有从 SS 到 TT 的简单路径集合，cec_e 表示边 ee 的容量，e∈pe\in p 表示路径 pp 包括 ee 这条边。

这个问题的对偶问题为：

在满足以下两组条件的前提下：

∀p∈P(S,T),∑e∈pxe≥1∀e∈E,xe≥0\forall p\in P(S,T),\sum_{e\in p} x_e\ge 1\\ \forall e\in E,x_e\ge 0

最小化：

∑e∈Exece\sum_{e\in E}x_ec_e

xex_e 为变量。

我们证明这个线性规划问题的最优解就是最小割的权值，那么运用对偶原理就可以证明最大流等于最小割。下文中记 OP\text{OP} 为上面线性规划问题的最优解，而 MC\text{MC} 为图 GG 最小割的权值。

  • 首先有 OP≤MC\text{OP}\le \text{MC}

    这是因为对于 GG 一个最小割 c(S,S‾)c(S,\overline{S})，我们让满足 u∈S,v∈S‾u\in S,v\in \overline{S} 的边 e=(u,v)e=(u,v) 的 xex_e 赋值为 11，剩下赋值为 00

    则此时有：∑e∈Exece=MC\sum\limits_{e\in E}x_ec_e=\text{MC}。

    又因为对于每个 p∈P(S,T)p\in P(S,T)，比然后有一个边 e∈pe\in p 满足 e∈S×S‾e\in S\times \overline{S}，所以条件「∑e∈pxe≥1\sum\limits_{e\in p} x_e\ge 1」满足，该赋值是一个可行解。故：OP≤∑e∈Exece=MC\text{OP}\le \sum\limits_{e\in E}x_ec_e=\text{MC}。

  • 再来有 OP≥MC\text{OP}\ge \text{MC}。

    我们考虑该线性规划的一个最优解，就用 {xe}\{x_e\} 表示，则此时有：∑e∈Exece=OP\sum\limits_{e\in E}x_ec_e=\text{OP}。

    这是我们突然让 GG 上的边带权重，边 ee 带权重 xex_e，并设 dv (v∈V)d_v\,(v\in V) 为这样赋权后从 SS 到 vv 的最短路径长度。

    再来一个参数 α∈[0,1)\alpha\in [0,1)，定义 SαS_\alpha 如下：

    Sα={v∈V∣dv≤α}S_\alpha=\{v\in V\mid d_v\le \alpha \}

    因为有条件「∑e∈pxe≥1\sum\limits_{e\in p} x_e\ge 1」，所以必有 dT≥1d_T\ge 1，则有 T∈SαT\in S_\alpha，故 SαS_\alpha 与其补 Sα‾:=V−Sα\overline{S_\alpha}:=V-S_\alpha 是原图的一个割。

    我们想要证明存在这样的一个 α∈[0,1)\alpha\in [0,1)，使得：

    c(Sα,Sα‾)≤∑e∈Exece=OPc(S_\alpha,\overline{S_\alpha})\le \sum_{e\in E}x_ec_e=\text{OP}

    而我们又发现这就等价于：

    ∫01c(Sα,Sα‾)dα≤∑e∈Exece=OP\int_0^1 c(S_\alpha,\overline{S_\alpha})\mathrm d \alpha\le \sum_{e\in E}x_ec_e=\text{OP}

    又注意到如果 α\alpha 的取值在 [0,1)[0,1) 上等概率分布，则这个积分表示一个期望：

    E(c(Sα,Sα‾))=∫01c(Sα,Sα‾)dα\mathbb E(c(S_\alpha,\overline{S_\alpha}))=\int_0^1 c(S_\alpha,\overline{S_\alpha})\mathrm d \alpha

    考虑每一条边 e=(u,v)∈Ee=(u,v)\in E 对期望的贡献。e∈Sα×Sα‾e\in S_\alpha\times \overline{S_\alpha} 等价于 du≤α<dvd_u\le \alpha<d_v。

    所以如果 dv≤dud_v\le d_u，则 ee 对期望的贡献为 00。

    若 dv>dud_v>d_u，由三角不等式又得到：du≤α<dv≤du+xed_u\le \alpha<d_v\le d_u+x_e。所以：Pr⁡[e∈Sα×Sα‾]≤Pr⁡[α∈[du,du+xe)]=xe\Pr[e\in S_\alpha\times \overline{S_\alpha}]\le \Pr[\alpha\in [d_u,d_u+x_e)]=x_e。则 ee 对期望的贡献不超过 xecex_ec_e。

    这样就可以得到：

    E(c(Sα,Sα‾))≤∑e∈Exece\mathbb E(c(S_\alpha,\overline{S_\alpha}))\le \sum_{e\in E}x_ec_e

那么就得出 OP=MC\text{OP}=\text{MC}，也就是说这个对偶线性规划问题得出的最优解的值就是最小割。

而原线性规划问题的最优解的值显然是最大流，故由线性规划对偶性可知：最大流等于最小割。