算法设计与分析.07.网络流 (1)

网络流

  • Network Flow

max-flow and min-cut problems

  • 最大流、最小割问题

图模型

  • 有向图:\(G(V,E,s,t,c)\)
  • 源 source:\(s\in V\)
    • 假设所有点都是 \(s\) 可达的
  • 汇 sink:\(t\in V\)
  • 容量:\(c(e)\ge0,\forall e\in E\)

最小割

  • s-t cut:\((A,B)\)\(V\) 的一个划分,满足 \(s\in A,t\in B\)
  • 容量(capacity)
    • 只包含 \(A\to B\) 的边,不包含 \(B\to A\) 的边

\[ cap(A,B)=\sum_{e=(a,b),a\in A,b\in B}c(e) \]

  • 最小割:找到一个划分,使得容量最小

最大流

  • s-t flow:满足如下的函数 \(f\)
  • 容量限制(capacity):\(0\le f(e)\le c(e),\forall e\in E\)
    • 所有边
  • 流守恒(flow reservation):\(\sum_{e\text{ in to }v}f(e)=\sum_{e\text{ out of }v}f(e),\forall v\in V-\{s,t\}\)
    • 中间节点
  • 流量

\[ val(f)=\sum_{e\text{ out of }s}f(e)-\sum_{e\text{ in to }s}f(e) \]

  • 最大流:找到一个 \(f\),使得流量最大

Ford–Fulkerson algorithm

贪心算法

  • 不一定能找到最大流
    • 因为每次增流只考虑了 \(s\to t\) 的路径(还可能有反向增流)
    • 一旦一条边上进行增流之后,就不会再进行减流
  • 例子
    • 贪心算法如果找到 \(s\to v\to w\to t\),则不可能找到最大流 \(4\)

残差网络

  • Residual network
  • 原图上加上一条反向边
  • 容量

  • 残差网络
    • 边:按照上述定义下,\(c_f(e)>0\) 的边

  • \(f'\)\(G_f\) 中的流 \(\Leftrightarrow\) \(f+f'\)\(G\) 中的流
    • 反向边的的流在 \(G\) 的正向边中减去
    • \(G_f\) 上的正向边和反向边合并即证
  • 残差网络的好处:能够减流

增流路径

  • augmenting path
  • \(G_f\) 中的 \(s\to t\) 路径
  • 瓶颈容量(bottleneck capacity)\(\delta\)
    • 增流路径中的最小边权值
    • 用于增流
  • 增流路径 \(P\)

  • 增流之后

\[ val(f')=val(f)+bottleneck(G_f,P) \]

FF 算法

  • \(G_f\) 中不断增流

max-flow min-cut theorem

  • 最大流=最小割

流定理

  • \((A,B)\) 是一个 cut,那么就有如下式子

\[ val(f)=\sum_{e\text{ out of }A}f(e)-\sum_{e\text{ in to }A}f(e) \]

  • 证明:加上 \(A-s\) 所有点的流守恒公式即证

流小于割

  • 对于任意流 \(f\),任意割 \((A,B)\),都有 \(val(f)\ge cap(A,B)\)
  • 应用流定理即可

极值

  • 如果存在流 \(f\),割 \((A,B)\),满足 \(val(f)=cap(A,B)\)
  • \(val(f)\) 为最大流,\(cap(A,B)\) 为最小割
  • 证明是显然的

最大流最小割定理

  • 最大流=最小割
    • 能取到等号
  • 增流路径定理
    • \(f\) 是最大流 \(\Leftrightarrow\) 不存在增流路径
  • 等价描述

证明

  • \(\text{i}\to \text{ii}\):上面的极值定理
  • \(\text{ii}\to \text{iii}\):反证法
  • \(\text{iii}\to \text{i}\):构造
    • 按照 \(G_f\)\(s\) 的可达性,将顶点划分为 \(A,B\)
    • 看原图 \(G\),此时
      • \(A\to B\) 的边必然是满的 \(f(e)=c(e)\),否则 \(G_f\) 中存在一条 \(A\to B\) 的边,\(c_f(e)=f(e)-c(e)\)
      • \(B\to A\) 的边必然是空的 \(f(e)=0\),否则 \(G_f\) 中存在一条 \(A\to B\) 的边,\(c_f(e^{\text{reverse}})=f(e)\)
    • 这种构造满足 \(cap(A,B)=val(f)\)

最大流算最小割

  • 时间复杂度:\(O(m)\)
  • 根据上面的构造方法,找到 \(s\) 可达的点,形成 \(A\)\(B=V-A\)

Capacity-scaling algorithm

FF 分析

  • 假定图 \(G\) 中,\(c(e)\) 都是 \([1,C]\) 之间的整数
  • \(G_f\) 也满足
    • 归纳法,增流路径前后都满足即可
  • FF 算法找增流路径最多执行 \(val(f^{\ast})\le nC\) 次(\(f^{\ast}\) 是最大流)
    • 每次增流至少增加 1
    • \(s\) 出去最多 \(nC\)
  • FF 时间复杂度:\(O(mnC)\)
    • \(O(m)\) 时间找到增流路径
    • BFS/DFS 都可以
  • 存在整数最大流
    • 每一增流的流量都是整数

复杂度

  • 输入规模:\(m,n,\log C\)
  • \(C=\max_e c(e)\),迭代次数可能也大于 \(C\)
    • 反复横跳,迭代 \(2C\)
1
2
3
4
s -> v -> w -> t
s -> w -> v -> t
s -> v -> w -> t
s -> w -> v -> t

扩展

  • 如果 \(c(e)\) 是有理数,FF 可行
    • 乘上分母之积,化为整数
  • \(c'(e)=k\cdot c(e)\),最小割的划分不变
    • 每一个割集的容量都变为原来的 \(k\)
  • \(c(e)\) 是实数,则不能保证

FF 问题分析

  • 如何找到更好的增流路径

Capacity-scaling algorithm

  • 限定每次增流路径的增流量必须大于 \(\Delta\)

  • 假定:\(c(e)\in [1,C]\)
  • \(\Delta\) 是 2 的整数次幂
    • 易证
  • \(c_f(e),f(e)\) 都是整数
  • 正确性:最后面 \(\Delta=1\),和原始算法一样了

复杂度

  • scaling phase:\(1+\lfloor{\log_2C}\rfloor\)
  • 算法执行到 \(\Delta\)-scaling phase 结束时,最大流小于等于 \(val(f)+m\Delta\)
    • 同样的划分方式,s 点 \(\Delta\) 可达的点集合 \(A\)

  • 每个 scaling phase,最多增流 \(2m\)
    • \(m\Delta\div\dfrac{\Delta}{2}=2m\)
  • 找增流路径:\(O(m)\)
  • 时间复杂度:\(O(m^2\log C)\)