《算法设计》学习笔记-网络流

最大流问题

定义流网络是有向图G=(V,E)，具有以下特征：
1，每条边e关联一个容量，它是非负数，记为C_e
2，存在单个源(source)节点s∈V
3，存在单个汇(sink)节点t∈V
除了s和t以外的节点被称为内部节点

定义流，我们说s-t流是一个函数f，它把每条边e映射到一个非负实数，f: E->R⁺；f(e)直观地表示边e所承载的流量。流f必须满足下面两个条件：
1，（容量条件）对于每条边e∈E，有0≤f(e)≤C_e
2，（守恒条件）对于s和t以外的每个节点v，进入节点的所有流量等于流出节点的所有流量

定义v(f)是源点处产生的流量v(f)=f^out(s)

假设把图的节点分为两个集合A和B，使得s∈A和t∈B，从s到t的任何流都必须从A穿越到B，这表明每个这样的“割”都限制了最大可能的流量值。最大流量值等于每个这样的“割”的最小容量。

剩余图：给定流网络G和G上的流f，我们如下定义G相对于f的剩余图G_f
1，G_f的节点集与G的节点集相同
2，对于f(e)<c_e的G的每条边e=(u,v)，有c_e-f(e)个“剩余”容量单位，我们可以考虑尝试正向增加流量。因此，我们在G_f中包含边e=(u,v)，其容量为 c_e-f(e) 。我们将这种方式包含的边成为正向边（forward edge）。
3，对于f(e)>0的G的每条边e=(u,v)，有f(e)个流量单位，如果需要，可以通过反向增加流量来“撤销”。因此，我们在G_f中包含边e’=(v,u)，容量为f(e)。我们将这种方式包含的边称为反向边（backward edge）。

我们把bottleneck(P,f)定义为P上任何边相对于流量f的最小剩余价值。定义操作augment(f,P)，它在G中产生一个新的流f’

augment(f,P):
令b=bottleneck(P,f)
For 每条边(u,v)∈P
  If e=(u,v)是一头正向边 then
    在G中将f(e)增加b
  Else (u,v)是一条反向边，且令e=(v,u)
    在G中将f(e)减少b
  Endif
Endfor
Return(f)

Fold-Fulkerson算法：

Max-Flow
  对G中所有的e初始化f(e)=0
  While 在增广图Gf中存在一条s-t路径
    令P是Gf中的一条简单s-t路径
    f'=augment(f,P)
    将f更新为f'
    将剩余图Gf更新为Gf'
  Endwhile
  Return f

通过改进选择增广路径的方法，来减少迭代次数。定义G_f(Δ)为剩余图的子集，仅包含剩余容量至少为Δ的边。算法如下：

缩放最大流

  对G中所有的e初始化f(e)=0
  初始化设置Δ是2的最大幂，且不大于离开s的最大容量

  While Δ≥1
    While 在图Gf(Δ)中存在一条s-t路径
    令P是Gf(Δ)中的一条简单s-t路径
    f'=augment(f,P)
    将f更新为f'病更新Gf(Δ)
    Endwhile
    Δ=Δ/2
  Endwhile
  Return f