(算法) – 网络流

网络流问题与线性规划

网络流

假设一个最大流的图例:

设 G=(V,E) 是一个网络流,设 s 为源点,t 为汇点。G 的流的一个实值函数 f: VxV -> R,对所有点 v 和 u ,满足以下的性质:

  • 容量限制:f(u, v) <= c(u, v) 一条边的流不超过它的容量
  • 反对称性:f(u,v) = -f(v,u)。
  • 流量守恒:除非 u=s 或 u=t,否则从 u 流入流出的总和必须是 0。

f(u,v) 为从 u 发送到顶点 v 的流量(flow)。流的值定义为 |f|=从源点 s 到 t 的最大流。

满足流量网路的性质实际上定义了问题的限制

  • 经过边的流量不能超过流量
  • 除了源点 s 和汇点 t,对于其他的点,满足输入流量=输出流量

网络流可以简化为一下的模型:

st 网络模型

注意网络流的图本质上是一个无向图,但是实际上是一个有向图。无向是为了寻找增广路径的时候方便。所以定义一个 FlowNetwork 类,这个类继承自无向图的类。

最大 st- 流量

给定一个 st- 留恋不过网络,找出一个 st- 流量的配置,使得 s 到 t 的流量最大化。这类似于一个在给定的限制添加下找到一个最优解的问题。

Ford-Fulkerson 算法

这个算法的主要依赖于三种重要的思想:

  • 残留网路(Residual networks)
  • 增广路径(Augmenting paths)
  • 割(Cut)

依据网络对应的无向图中从起点到终点的路径,在路径中当沿着路径从起点向终点前进时,经过某条边时的方向可能和流量的方向相同(称对应的边为正向边)或相反(称为逆向边)。对于任何一个非饱和正向边和非空反向边,可以通过增加正向边的流量流量,降低逆向边的流量来增加网络中的总流量。流量的增量受到路径上的所有正向边未使用的容量的最小值和逆向边的流量控制。这样的一条路径称为增广路径。直到找不到增广路径,那么最大流的之就是所有增量的累加。

最大流-最小割定理

顾名思义,这个定理的基础就是网络流中流量和切分的定理。

最大流最小割定理提供了对于一个网络流,从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和。最大流最小割定理是线性规划中的对偶问题的一种特殊情况,并且可以用来推导Menger定理和König–Egerváry定理。

我们需要找到一个割边使得图的切分将所有的顶点分为两个不相交的集合,而一条横向的割边则是连接分别存在于两个集合中的两个顶点的一条边。定义 st-切分 为一个将顶点 s 和 t 分配于不同集合中的切分。

从图中可以看出来,从含有 s 的集合流入到含有 t 的集合的边(称为 st- 边,反之为 ts- 边)。一个 st- 边的集合称为一个切分集,一个 st- 切分的容量为该切分的容量之和。st- 切分的跨切分流量(flow across)是切分的所有的 st- 流量之和与 ts- 边流量之和的差。如果切断 st- 切分的所有的 st- 边,那么将会切断所有从 s 到 t 的路径。(类似于至少断开多少个网络连接可以切断某个局域网内的所有计算机的网络连接)。如果将切分的容量看作这么做的成本,把呢吧切断流量的最有效的办法是解决以下的问题 :最小 st- 切分,给定 st- 网络,找到容量最小的 st- 切分。

令 f 为一个 st- 流量网络,以下三种条件是等价的:

  1. 存在某个 st- 切分,其容量和 f 的流量相等
  2. f 达到了最大流量
  3. f 中已经不存在任何的增广路径

Ford-Fulkerson 算法是一种迭代的方法。有以下的步骤:

  1. 设当前的流为 0, 也就是对于 u,v 有 f(u, v) = 0
  2. 在当前的图中找到一条从 s 到 t 的路径。如果没有,则表示不存在增广路径了(没有更小的流量可以作为逆向边的增量),停止,最大流即是增量和
  3. 计算路径上所有的有向边的最小值,记为 bottle
  4. 对所有的路径中的每条有向边 <u,v> 更新当前的剩余流量 = 容量- bottle
  5. 让增量和累加上 bottle

剩余网络

剩余网络中的顶点和原网络相同,原网络中每条边对应着1~2条边。对于网络中的每条从 v 到 w 的边 e,令 fe 表示流量,ce 表示容量。如果 fe 为正,将边 w->v 加入剩余网络且容量为 fe(建立逆向边);如果 fe < ce,将 v->w 加入剩余网络且容量为 ce - fe (剩余的流量)。如果从 v 到 w 的边 e 为空,剩余网络就只有一条容量为 ce 的边 v->w 与之对应;如果该边饱和(即 fe 等于 ce),剩余网络就只有一条容量为 fe 的边 w->v 与之对应;如果它既不为空也不饱和,那么剩余网络将含有容量 v->w 和 w->v。这其实是一个建立剩余网络图 Gf。

运行示例的程序:

运行示例

这里假设 s,a,b,c,d,t 分别为 0,1,2,3,4,5。

可以看出第三列输出的就是逆向边,也就是流通的最小流。同时指向汇点的流量和和源点输出的流量和相同。

程序实现:

二分图匹配

匹配就是指任意两条边没有公共顶点。 例如学生就业的问题。图中所有的边均有学生指向公司,然后添加一个起点且对于每个学生都有一条从起点 s 指向的边,添加一个终点且对于每个公司都有一条从公司指出的边。(可以设置两个顶点集合分别存储学生和公司,这就构成了两个不相交的子集)。有几个特性:

  • 每个顶点都有输入和输出,总是会有一个合法的匹配
  • 每条边的权为 1,也就是每个顶点最多出现在一个匹配上。
  • 匹配不可能包含有更多的边,因为还有更多类似的匹配。工作分配

线性规划(待续)

可以考虑一下,网络流有若干个约束条件:

  • 0 <= x(s->a) <= 4 1
  • 0 <= x(s->b) <= 5 2
  • 0 <= x(a->b) <= 3 3
  • 0 <= x(a->c) <= 2 4
  • 0 <= x(b->c) <= 1 5
  • 0 <= x(b->d) <= 6 6
  • 0 <= x(c->t) <= 7 7
  • 0 <= x(d->c) <= 2 8
  • 0 <= x(d->t) <= 3 9
  • 守恒:x(s->a) = x(a->b) + x(a->c)
  • 守恒:x(s->b) + x(a->b) = x(b->d) + x(b->c)
  • 守恒:x(a->c) + x(b->c) + x(d->c) = x(c->t)
  • 守恒:x(b->d) = x(d->c) + x(d->t)

最终的根据约束条件求 x(c->t) + x(d->t) 最大化。

使用 Simplex 算法可以进行求值。(然而还是没懂)

参考

  1. (Cnblogs)Ford-Fulkerson 最大流算法
  2. (Wikipedia)最大流最小割定理
  3. (Wikipedia)Ford-Fulkerson 算法
  4. (Wikipedia)网络流
  5. Robert Sedgewick等,算法(第四版)[M]. 北京:人民邮电出版社,2012:580-597
  6. Frank R. Giordano 等,数学建模(第五版)[M]. 北京:机械工业出版社,2014:235-243
  7. (Renfei's blog)二分图的最大匹配