本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循 署名-非商业用途-保持一致 的创作共用协议.
对于最大流最小割问题的总结, 如有错误, 欢迎指出.
最大流(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 {wu} = /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简称)包含不同运行时间的几种实现, 是一种迭代的方法.
该方法主要依赖于 残存网络, 增广路径和割
//伪代码
初始化:所有流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实现
伪代码
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)
//边的定义
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();
}
}
}
//流图的定义
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];
}
}
//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];
}
}
参考链接
-
<算法导论> -
<算法>(普林斯顿Algorithm II) - 网络流：最大流，最小割 基本概念及算法
- 最大流问题-Ford-Fulkerson算法
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
