Code

最大流（一）

简述最大流问题，给出一种解决最大流的最简单方法，及在二分图匹配中的应用。

流网络

  • 流网络G=（V，E）是一个有向图，E中的每条边（u，v）均有一个非负容量c（u，v）>=0，对于不属于E中的边（u，v），则c（u，v）=0。流网络中有源点s和汇点t，方便起见假设每个顶点都处在从源点s到汇点t的某条路径上，也就是说对每个V中的顶点v，都有s～>v~>t的路径存在。因此，图G为连通图，并且|E|>=|V|-1。流网络具备三个基本性质。
    • 容量限制：对于所有V中的顶点u,v，都有f(u,v) <= c(u,v)。
    • 反对称性：对于所有V中的顶点u,v，都有f(u,v) = -f(v,u)。
    • 流守恒性：对所有V中的非s、t顶点u，都有Sum{ f(u,v)，v为V中全部顶点 }= 0。
      f(u,v)称为从顶点u到顶点v的流，它可以为正、负或零。流f的值的定义为|f| = Sum{ f(s,v)，v为V中所有顶点 }，也就是从源点s出发的总流量，|f|表示流的值，而不是绝对值。
  • 流网络性质的解释：容量限制说明从一个顶点到另一个顶点的网络流不能超过设定的容量。反对称性说明从顶点u到顶点v的流是其反向流的负值。流守恒性说明从非源点或非汇点的顶点出发的总网络流为0，也可以说，除s和t外，进入一个顶点的总流为0，可以阐述为流进等于流出。
  • 最大流问题：给出一个具有源点s和汇点t的流网络G，找出从s到t的最大流值。举个例子说明，下图是一个简单的流网络，从源点s到汇点t的最大流为5，将有向边想象成城市间的公路，该流网络就转化为城市间的物流问题。另外，图中不存在双向边，假如为图中权值为6的有向边配备一条“反向通道”，该反向通道的权值为3，也就是城市间可以相互运输，则可以利用抵消处理将反向通道剔除。因为运输同一种物品，从u到v运送6个，从v到u运送3个，实质相当于从u到v运送6-3=3个，因此任意顶点间流传输问题都可以通过抵消转化为单向传输问题：只沿正向流的方向传输。
  • 多个源点或多个汇点：考虑上一篇差分约束系统，我们通过构造了一个额外的源点s0得到了差分约束系统的最短路模型。在最大流问题中，如果出现多个源点或者多个汇点，可以为其增加一个超级源点s0或超级汇点t0,并将s0和所有源点si相连，权值为正无穷，将所有汇点ti和超级汇点t0相连，权值为正无穷。问题就转化为从超级源点s0到超级汇点t0的最大流问题。
  • 隐含求和记号简化流网络的表达：使用函数f，f的任意自变量都可以是顶点的集合，表示的值为自变量代表的元素所有可能求和情况，例如f(X,Y) = Sum{ f(x,y) ，x in X and y in Y }。因此流守恒可以表示为f(u,V) = 0，流的值|f| = f(s,V) = f(V,t)。对于下面几个恒等式，建议参考基尔霍夫第一第二定律证明。（1）对于所有的X包含于V，f(X, X) = 0，（2）对所有X，Y包含于V，f(X, Y) = -f(Y,X)，（3）对所有X,Y,Z包含于V，其中X and Y = None，有f(X or Y, Z) = f(X, Z)+f(Y, Z)，f(Z, X or Y) = f(Z, X)+f(Z, Y)。

Ford-Fulkerson方法

方法解释和定理

  • 最大流问题的Ford-Fulkerson方法包含多种不同运行时间的实现，其依赖于三种流网络中常见的思想：残留网络（residual network），增广路径（augmenting path）和割（cut）。Ford-Fulkerson方法是一种迭代方法，开始时对所有V中的u，v有f(u,v)=0，即初始状态时流的值为0。每次迭代可以通过寻找一条“增广路径”来增加流值。增广路径时从源点s到汇点t的一条路径，沿着该路径可以向现有流量压入更多流值。反复进行该过程，直到所有增广路径都被寻找出。后面将证明算法的正确性。
1
2
3
4
5
FORD-FULKERSON-METHORD(G, s, t)
	initialize flow f to 0
	while there exists an augmenting path p
		do augment flow f along p
	return f
  • 残留网络：给定一个流网络G和一个流f，该流网络在此流基础上的残留网络Gf由可以容纳更多网络流的边组成。举例来说，有一个流网络G=（V,E），源点s汇点t，设f是G中的一个流，考察V中一对顶点u，v，在不超过容量c(u,v)的条件下，从u到v可以压入额外的网络流量，就是(u,v)的残留容量，即cf(u,v) = c(u,v) - f(u,v)。在残留网络Gf中，每条残留边都能容纳一个严格为正的网络流。定义Ef为残留网络的边集，Ef中的边既可以是E中的边，也可以是它们的反向边。如果E中存在边（u，v）并且f(u,v) 0，并且若f(u,v)>0，则f(v,u)<0，此时cf(v,u) =="" c(v,u)="" -="" f(v,u)="">0，因此(u,v)的反向边(v,u)也存在于Ef中。对于一对顶点(u,v)，只有在初始网络中存在连接两个顶点的边，则残留网络中才能出现连接这两点的边，因此|Ef| <= 2|E|。残留网络中的流和初始网络中的流的关系为|f+f’| = |f|+|f’|。
  • 增广路径：增广路径p是残留网络Gf中从s到t的一条简单路径，增广路径上的每条边(u, v)可以容纳从u到v的某额外正网络流。称能够沿一条增广路径p的每条边传输的网络流的最大量为p的残留容量，cf(p) = min{ cf(u,v), (u,v) in p }。在已有流f的基础上加上fp，则可以得到G的另一个流，且新流的流值更接近最大值，因为|fp|为正，|f| + |fp|>|f|。
  • 流网络的割：Ford-Fulkerson方法沿增广路径反复增加流，直到找到最大流。流网络G=(V,E)的割（S，T）将V划分为S和T=V-S两部分，这里的划分类似于最小生成树中的点集划分，但此处针对的是有向图而非无向图。对于一个流f，穿过割（S，T）的净流量被定义为f(S,T)，割(S,T)的容量为c(S, T)，一个网络的最小割是网络中所有割中具有最小容量的割。对于最大流问题介绍中的图片，假如将左侧的s和距离其最近的顶点划分为S，剩下的两个顶点（含t）划分为T，则通过该割的净流量为2+3=5，2是图中最顶部顶点向t提供的流，3是s向图中最底部顶点提供的流。该割的容量为3+1+6=10。通过割的净流量可能包括顶点间的负网络流，但割的容量完全由非负值组成，即通过割（S，T）的净流由双向的正网络流组成，用从S到T的正网络流减去从T到S的正网络流；而割（S，T）的容量仅由从S到T的边计算而得，从T到S的边在计算c（S，T）时不包含在内。可以证明，流经任意割的净流都是相同的，且f(S,T) = |f|。证明如下：根据流守恒性，f(S-s,V) = 0，因此f(S,T) = f(S,V)-f(S,S) = f(S,V) = f(s,V)+f(S-s,V) = f(s,V) = |f|。还可以证明，对一个流网络G中任意流f来说，其值的上界为G的任意割的容量，即|f|=f(S, T) = Sum{ f(u, v), u in S, v in T } <= Sum{ c(u, v), u in S, v in T } = c(S，T)。从该式可以直接得出一个结论，网络的最大流必定不超过此网络最小割的容量。
  • 最大流最小割定理：如果f是具有源点s和汇点t的流网络G=（V，E）中的一个流，则下列条件等价：（1）f是G的一个最大流，（2）残留网络Gf不包含增广路径，（3）对G的某个割（S，T），有|f|=c（S，T）。结合上面提到的网络的最大流不超过此网络最小割的容量，可以得出网络的最大流等于某一最小割的容量。证明如下。
    • (1)->(2)：假设f是G的最大流，而Gf包含一条增广路径p，因此流的和f+fp是G的一个流，并且由增广路径的定义，f+fp的流值严格大于|f|，这与假设矛盾。
    • (2)->(3)：假设Gf不包含增广路径，即Gf不包含从s到v的路径。定义S={ v in V且Gf中从s到v存在路径 }，T=V-S。对于这样的割（S，T），s在S中，t在T中，并且对每对顶点(u, v)，都有f(u,v) = c(u,v)，否则(u,v)属于Ef，v就属于了集合S，这和前提矛盾。因此|f| = f(S, T) = c(S, T)。
    • (3)->(1)：对所有割（S，T），都有f<=c(S,T)，因此条件|f| = c(S, T)说明此时f是一个最大流。

基本的Ford-Fulkerson算法实现

  • 在Ford-Fulkerson方法的每次迭代中，找出任意增广路径p，并把沿p每条边的流f加上其残留容量cf（p）。下面的实现中，通过更新有边相连的每对顶点间的网络流来计算最大流。如果一对顶点间在任意方向都没有边相连，则隐含假设该对顶点间的f = 0。
1
2
3
4
5
6
7
8
9
FORD-FULKERSON(G, s, t)
	for each edge(u, v) in E(G):
		f[u][v] <- 0
		f[v][u] <- 0
	while there exists a path p from s to t in the residual network Gf:
		cf(p) <- min{ cf(u, v): (u, v) is in p }
		for each edge(u, v) in p:
			f[u][v] <- f[u][v] + cf(p)
			f[v][u] <- -f[u][v]
  • 上述基本实现方法，运行时间取决于如何确定第四行中的增广路径，如果选择不好，在边权有无理数的情况下算法可能不会终止：流的值随着求和运算不断增加，但始终无法收敛到流的最大值。若采用广度优先搜索来选择增广路径，则算法运行时间为多项式复杂度。通常情况下算法处理的问题中权值都为整数，如果是有理数可以按照一定比例转化为整数。在整数条件下，该种实现Ford-Fulkerson算法的运行时间为O(E|f|)，其中f是算法求出的最大流，原因在于第7行的循环为E次，寻找一条增广路径需要的深度优先搜索为E复杂度，而while最多执行f次，每次至少增加流值1个单位。在f较小时可以取得不错的运行效果，但当流网络中的最大流f*很大，例如我们将上面示例图中除了中间那条权值为1的边之外的其他边，权值都设为1000000，显然最大流为2000000,但增广路径会在权值为1的边上往返出现，因此一共要运行2000000×5次。

Edmonds-Karp算法

  • 如果在第四行用BFS实现对增广路径p的计算，即若增广路径时残留网络中从s到t的最短路径（每条边设为单位距离），则能改进Ford-Fulkerson的界，该种实现方法为Edmonds-Karp算法，运行时间为O(VE^2)。令R（u，v）表示每条边为单位长度的图Gf中，从u到v的最短路径长度。下证时间复杂度。
  • 对具有源点s和汇点t的流网络G=（V，E）运行Edmonds-Karp算法，对所有非源非汇点顶点v，残留网络Gf中的最短路径长度R（u，v）随着每个流的增加而单调递增。假设这个顶点v的流增加引起了从s到v的最短路径的减少，下面会推出矛盾。假设f是第一次流增加之前的流，该增加导致了某个最短路径距离的减小；设f’时增加以后的流。设v是在流增加时最小距离Rf’（u，v）被减小的顶点，因此Rf’（s，v）< Rf（s，v）。设p=s～>u->v是Gf’中从s到v的最短路径，因此（u，v）在Ef’中，且Rf’（s，u）=Rf’（s，v）-1。顶点u到s的距离不会因为v的流增加而减小，因此Rf’（s，u）>=Rf（s，u）。可以断言（u，v）不属于Ef，否则根据三角不等式有Rf（s，v）<=Rf（s，u）+1 <= Rf’（s，u）+1 = Rf’（s，v），这和假设Rf’（s，v）<Rf(s,v)矛盾。因此，如果有（u，v）不在Ef中而在Ef’中，只有流从v向u增加。Edmonds-Karp算法总是沿着最短路径增加流，因此Gf中从s到u的最短路径以（v，u）作为最后一条边。因此Rf（s，v）=Rf（s，u）-1<=Rf’（s，u）-1=Rf’（s，v）-2。因为开始假设Rf’（s，v）<Rf（s，v），因此假设矛盾。
  • 对具有源点s和汇点t的一个流网络G=（V，E）运行Edmonds-Karp算法，对流进行增加的全部次数为O(VE)。在一个残留网络Gf中，如果其增广路径p的残留容量是边（u，v）的残留容量，即cf（p）=cf（u，v），称此边（u，v）对增广路径p关键。在沿增广路径p增流后，路径p上的任何关键边都从残留网络中消失。此外，任何增广路径上都至少有一条关键边。下证|E|条边中每一条都可以至多|V|/2-1次成为关键边。设u，v为V中顶点，且它们之间由E中的一条边相连，由于增广路径为最短路径，因此（u，v）第一次作为关键边时，有Rf（s，v）=f（s，u）+1。一旦对流增加，边（u，v）立刻从残留网络中消失，直到从v到u的边出现增流，才会使（u，v）再次出现在增广路径上。假设此时G的流为f’，则Rf’（s，u）=Rf’（s，v）+1，又Rf（s，v）<=Rf’（s，v），得Rf’（s，u）=Rf’（s，v）+1>=Rf（s，v）+1=Rf（s，u）+2。因此对于边（u，v），从其成为关键边到再次成为关键边，源点到u的最短距离至少增加2，初始时从源点到u的距离至少为0。因此在u变为从s不可达之前，距离至多为|V|-2（排除s和t），因此在（u，v）第一次成为关键边后，至多还能成为关键边(|V|-2)/2次，总计至多|V|/2次。在残留网络中可能有O（E）对顶点间有边相连，因此全部关键边的数目规模为O（VE）。

Edmonds-Karp邻接表实现

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define INF 0x7fffffff
#define N 101

int map[N][N];
int visited[N], pre[N];
int V, E, s, t;

void init(){
	scanf("%d %d", &V, &E);
	int i, j, u, v, w;
	memset(map, 0, sizeof(map));
	for ( i = 0 ; i < E; i++ ){
		scanf("%d %d %d", &u, &v, &w );
		if ( map[v][u] != 0 )
			map[v][u] -= w;
		else 
			map[u][v] = w;
	}
	scanf("%d %d",&s, &t);
}

int cf( int source, int end ){
	int p = end, min = INF;
	while ( p != source ){
		min = ( min > map[pre[p]][p] ? map[pre[p]][p] : min );
		p = pre[p];
	}
	return min;
}

int  BFS( int source, int end ){
	int * stack = ( int * ) malloc ( sizeof( int ) * V ), i;
	memset(visited, 0, sizeof(visited));
	int front = 0, rear = 0;
	stack[rear++] = source;
	visited[source] = 1;
	pre[source] = source;
	while ( front != rear ){
		int s = stack[front++];
		for ( i = 0 ; i < V ; i++ ){
			if ( !visited[i] && map[s][i] ){
				stack[rear++] = i;
				visited[i] = 1;
				pre[i] = s;
				if ( i == end){
					free(stack);
					return 1;
				}
			}
		}
	}
	free(stack);
	return 0;
}

int maxFlow( int source, int end ){
	int flow = 0;
	while ( BFS( source, end ) ){
		int cfp = cf( source, end );
		flow += cfp;
		int p = end;
		while ( p != source ){
			map[pre[p]][p] = map[pre[p]][p] - cfp;
			map[p][pre[p]] += cfp;
			p = pre[p];
		}
	}
	return flow;
}

int main(){
	init();
	printf("maxFlow:%d\n", maxFlow(s,t));
	return 0;
}

转化为最大流问题的最大无向二分图匹配问题

  • 最大无向二分图匹配问题：给定一个无向图G=（V，E），一个匹配是边集E的子集，令匹配为M，满足对所有V中顶点v，M中至多有一条边和v相关联。若M中有边和v关联，则称v被匹配，否则v是无匹配的。最大匹配是求解最大势的匹配，即让|M|最大。假定顶点集合V可以被划分为L和R两部分，L和R不相交，且E中的所有边均为一个顶点在L中，另一个顶点在R中，则该图为二分图。方便起见假设该图每个顶点都至少有一条关联的边。
  • 为该无向二分图建立流网络，其中最大流对应最大匹配的数量。二分图G对应的流网络G’=（V’，E’）定义如下：设源点s和汇点t不属于V，在V’中向V加入超级源点s和超级汇点t，从s引出|L|条有向边，分别指向L中的每个顶点，R中的每个顶点也均引出一条指向t的有向边。此外在G中，L和R之间的|E|条边，均在G’中成为自L指向R的|E|条有向边。所有边均赋予单位容量。因为V中每个顶点都至少有一条关联边，因此|E|>=|V|/2，所以|E|<=|E’|=|E|+|V|<=3|E|，因此|E’|的规模为O(E)。

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2015/12/25/Graph-Algorithms7-flow/) 、作者信息（Forec）和本声明。

分享到