本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议.

对于最大流最小割问题的总结, 如有错误, 欢迎指出.

#最大流(MaxFlow)问题

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

想象一条多条不同水流量的水管组成的网络, s为供水广, t为水用户, 最大流问题就是找到能够在s到t流通的最大水流量

一个流是最大流当且仅当其残存网络不包含任何增广路径(里面的名称在后面有详细解释)

#流(Flow)的基本性质

设$C{uv}$代表边u到v最大允许流量(Capacity), $f{uv}$代表u到v的当前流量, 那么有一下两个性质:

  • $(u, v)$为有向图边, $ 0<=f{uv}<=C{uv} $, 即对于所有的边, 当前流量不允许超过其Capacity
  • 除了$s, t$之外, 对所有节点有 $ \sum\limits{(v, u)}f{vu} = \sum\limits{(u, v)}f{uv} $, 即对于任何一点, 流入该点的流量等于留出该点的流量, 流量守恒原则(类似与能量守恒的概念).

非负数值$f(u, v)$为从节点u到节点v的流.一个流$|f|$的定义:

$$ |f| = \sum\limits{v \in V}f(s,v) - \sum\limits{v \in V}f(v, s) $$

最大流问题即要找到一个最大的流f

#Ford-Fulkerson方法

之所以称之为方法, 而不是算法, 因为FF(Ford-Fulkerson简称)包含不同运行时间的几种实现, 是一种迭代的方法.

该方法主要依赖于残存网络, 增广路径和割

1
2
3
4
5
//伪代码
初始化:所有流f = 0
while 在残存网络中存在增广路径p
增加流f的值
return f

残存网络

给定网络G和流量f, 残存网络$G_f$由那些仍有空间对流量进行调整的边构成.

残留网络 = 容量网络capacity - 流量网络flow

残存网络

增广路径

增广路径p是残存网络中一条从源节点s到汇点t的简单路径,在一条增广路径p上能够为每条边增加的流量的最大值为路径p的残存容量$c_f(p) = min \{c_f(u,v):(u,v) \in p \}$

在一条增广路径p上, 要增加整条增广路径的水流量, 则必须看最小能承受水流量的管道, 不然水管会爆掉, 这最小承受水流量就是残存容量

在有向图网络G中, 割(S, T)将V划分为S和T = V - S, 使得s属于S集合, t属于T集合. 割(S, T)的容量是指从集合S到集合T所有边的容量之和.

最大流

#最大流最小割理论

设$f$为流网络G = (V, E)中的一个流, 该流网络的源节点为s, 汇点为t, 则下面的条件是等价的:

  • f是G的一个最大流
  • 残存网络$G_f$不包含任何增广路径
  • $|f| = c(S, T)$, 其中(S, T)是流网络G的某个割

#Ford-Fulkerson算法Java实现

伪代码

1
2
3
4
5
6
7
8
9
10
for each edge(u, v)属于G.E(图G的边)
(u, v).f = 0 //所有边的流为0
//循环终止条件为残存我昂罗中不存在增广路径
while s到t的残存网络中存在增广路径p:
c(p) = 最小残存容量
for 增广路径的每条边
if 这条边属于E集合
(u, v).f = (u, v).f + c(p) //意思是在原有的流增加最小残存容量.
else
(u, v).f = (u, v).f - c(p)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//边的定义
public class FlowEdge {
private final int v, w; //边的起点和终点
private final double capacity; //流量
private double flow; //流
public FlowEdge(int v, int w, double capacity) {
this.v = v;
this.w = w;
this.capacity = capacity;
}
public int from() {
return v;
}
public int to() {
return w;
}
public double capacity() {
return capacity;
}
public double flow() {
return flow;
}
public int other(int vertex) {
if (vertex == v) {
return w;
} else if (vertex == w) {
return v;
} else {
throw new RuntimeException("Inconsistent edge");
}
}
//v中残留流量
public double residualCapacityTo(int vertex) {
if (vertex == v) { //反向边
return flow;
} else if (vertex == w) { //正向边
return capacity - flow;
} else {
throw new IllegalArgumentException();
}
}
//向v中增加delta
public void addResidualFlowTo(int vertex, double delta) {
if (vertex == v) {
flow -= delta;
} else if (vertex == w) {
flow += delta;
} else {
throw new IllegalArgumentException();
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//流图的定义
public class FlowNetwork {
private final int V; //顶点个数
private Bag<FlowEdge>[] adj;
public FlowNetwork(int V) {
this.V = V;
adj = (Bag<FlowEdge>[]) new Bag[V];
for (int v = 0; v < V; v++) {
adj[v] = new Bag<>();
}
}
//想流图中增加边
public void addEdge(FlowEdge e) {
int v = e.from();
int w = e.to();
adj[v].add(e); //正向边
adj[w].add(e); //反向边
}
public int V() {
return V;
}
public Iterable<FlowEdge> adj(int v) { //返回邻接边
return adj[v];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//FordFulkerson方法的实现
public class FordFulkerson {
private boolean[] marked; //如果残留网络中有s->v路径, 则为true
private FlowEdge[] edgeTo; //s->v路径的最后的边
private double value; //流
public FordFulkerson(FlowNetwork G, int s, int t) {
value = 0.0;
//当找不到增广路径时终止
while (hasAugmentingPaht(G, s, t)) { //判断是否还有增广路径
double bottle = Double.POSITIVE_INFINITY;
for (int v = t; v != s; v = edgeTo[v].other(v)) { //计算最大流量
bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
}
for (int v = t; v != s; v = edgeTo[v].other(v)) {
edgeTo[v].addResidualFlowTo(v, bottle);
}
value += bottle;
}
}
private boolean hasAugmentingPaht(FlowNetwork G, int s, int t) {
edgeTo = new FlowEdge[G.V()];
marked = new boolean[G.V()];
Queue<Integer> q = new Queue<>();
q.enqueue(s);
marked[s] = true;
while (!q.isEmpty()) {
int v = q.dequeue();
for (FlowEdge e : G.adj(v)) {
int w = e.other(v);
if (e.residualCapacityTo(w) > 0 && !marked[w]) {
edgeTo[w] = e;
marked[w] = true;
q.enqueue(w);
}
}
}
return marked[t];
}
public double value() {
return value;
}
public boolean intCut(int v) { //在残留网络中v->s是否可达
return marked[v];
}
}

#参考链接