最大流最小割定理

《最大流最小割定理》由会员分享，可在线阅读，更多相关《最大流最小割定理（6页珍藏版）》请在装配图网上搜索。

1、最大流最小割默认分类2010-06-20 15:39:10阅读293评论0 字号：大中小订阅最大流问题最大流问题是一类极为广泛的问题。不仅在交通运输网络中有人流、车流、货物流、供水网络中有 水流、金融系统中有现金流、通讯网络中信息流.等。五十年代，Ford(福特)、Fulkerson(富克逊)建立 的“网络流理论”，是网络应用的重要组成部分。网络与流的概念对于有向图D=(V,A)，如果V中有一发点vs (亦称源还有一收点(亦称为汇)记为vt其余均为中间 点，且对A中的每条弧均有权W(vi,vj)?0 (简记为Wij，并称为弧容量)，则称这样的赋权有向图D为容 量网络，记为D=(V,A,W)。通

2、过D中弧(vi,vj)的物流量fij，称为弧(vi,vj)的流量。所有弧上流量的集合f=(fij 称为该网络D的一个流。最大流最小截量定理：任一网络D中，最大流的流量=最小截集的截量。最大流算法的邻接阵实现1. 最大流最小割定理介绍：把一个流网络的顶点集划分成两个集合S和T，使得源点s GS且汇点t UT，割(S,T)的容量C(S,T) =ZCuv,其中 UGS 且 veTo从直观上看，截集(S,T)是从源点s到汇点t的必经之路，如果该路堵塞则流从s无法到达to于是我 们可以得到下面的定理：最大流最小割定理：任意一个流网络的最大流量等于该网络的最小的割的容量。这个定理的证明这里就不给出了，可以

3、参考图论方面的资料。2. 求最大流的Edmonds-Karp算法简介：若给定一个可行流F=(Fij)，我们把网络中使Fij=Cij的弧称为饱和弧，FijCij的弧称为未饱和弧。如 果流网络中从i到没有弧，我们添加一条从i到且容量Cij=0的弧，这样整个流网络变成一个完全图。 如果从i到有流量Fij，则从j到i的流量定义为Fji = -Fij o考虑一条从源点s出发到汇点t的路径p，如 果对于每一段弧(i,j)属于p都有Fij Cij，即每一条属于p的弧都是未饱和弧，则我们可以向这条路径上压 入更多的流，使得其中的一条弧达到饱和。这样的路径p叫做可改进路，可压入的流量叫做该可改进路的 可改进流量

4、。重复这个过程，直到整个网络找不到一条可改进路，显然这时候网络的流量达到最大。 Edmonds-Karp算法就是利用宽度优先不断地找一条从s到t的可改进路，然后改进流量，一直到找不到 可改进路为止。由于用宽度优先，每次找到的可改进路是最短的可改进路，通过分析可以知道其复杂度为 O(VE2)oEdmonds-Karp算法的伪代码如下：设队列Q-存储当前未检查的标号点，队首节点出队后，成为已检查的标点；path -存储当前已标号可改进路经;repeatpath置空；源点s标号并进入path和Q;while Q非空and汇点t未标号dobegin移出Q的队首顶点u;for每一条从u出发的弧(u,v)

5、 doif v未标号and弧(u,v)的流量可改进then v进入队列Q和path;end whileif汇点已标号then从汇点出发沿着path修正可改进路的流量；until 汇点未标号;Edmonds-Karp算法有一个很重要的性质：当汇点未标号而导致算法结束的时候，那些已经标号的节 点构成集合S，未标号的节点构成集合T，割(S,T)恰好是该流网络的最小割；且这样求出的最小割(S,T)中 集合S的元素数目一定是最少的。寻找最大流的基本方法是Ford-Fulkerson方法，该方法有多种实现，其基本思想是从某个可行流F 出发，找到关于这个流的一个可改进路经P，然后沿着P调整F，对新的可行流试

6、图寻找关于他的可改进 路经，如此反复直至求得最大流。现在要找最小费用的最大流，可以证明，若F是流量为V(F)的流中费用 最小者，而P是关于F的所有可改进路中费用最小的可改进路，则沿着P去调整F,得到的可行流F一定是 流量为V(F)的所有可行流中的最小费用流。这样，当F是最大流时候，他就是所要求的最小费用最大流。注意到每条边的单位流量费用B(i,j)0，所以F=0必是流量为0的最小费用流，这样总可以从F=0 出发求出最小费用最大流。一般的，设已知F是流量V(F)的最小费用流，余下的问题就是如何去寻找关于 F的最小费用可改进路。为此我们将原网络中的每条弧u,v变成两条方向相反的弧：1。前向弧u,v

7、，容量C和费用B不变，流量F为0；2。后向弧v,u，容量C为0，费用为-B，流量F为0；每一个顶点上设置一个参数CT，表示源点至该顶点的通路上的费用和。如果我们得出一条关于F的 最小费用可改进路时，则该路上的每一个顶点的CT值相对于其它可改进路来说是最小的。每一次寻找最 小费用可改进路时前，源点的CT为0,其它顶点的CT为+8。设cost为流的运输费用，初始时由于F=0,则cost=0,我们每求出一条关于F的最小费用可改进路， 则通过cost cost + ZB(e)*d,(其中eP,d为P的可改进量)来累积流的运输费用的增加量。显然，当求出最小费用最大流时，cost便成为最大流的运输费用了。

8、另外设置布尔变量break为最小费用可改进路的延伸标志，在搜索了网络中的每一个顶点后，若 break=true表示可改进路还可以延伸，还需要重新搜索网络中的顶点；否则说明最小费用的可改进路已经 找到或者最大流已经求出。这个模版的代码完全按照BFS从源点逐个遍历增广路径，得到最大增广容量，通过不断调整，最后求得 最大流量,值得注意的是，最后一次BFS后所标的路线即为最小截集，即所谓的瓶颈，据此很容易求出最小截 集的容量。#include #include using namespace std;邻接阵实现const long MAXN=1000;const long lmax=0x7FFFFFF

9、F;long NetMAXNMAXN;/残 余网络long PathMAXN;/ 增广路径long LvMAXN;/增广路径通过容量queue q;long m,n;/ 点，边long Start,End;void init()while (!q.empty()q.pop();memset(Path,-1,sizeof(Path);Lg M. ,long b)return ab?a:b;L W)init();PathStart=0;LvStart=lmax;q.push(Start);while (!q.empty()long t=q.front();q.pop();if (t=End)(br

10、eak;long i;for (i=1；i=m;+i)(if (i!=Start&Pathi=-1&Netti)(Lvi=Min(Lvt,Netti);q.push(i);Pathi=t;if (PathEnd=-1)(return -1;return Lvm;void print(long n)(printf(%ldn,n);void Ford_Fulkerson()(long i;long Max_Flow=0;for (i=0;in;+i)(long from,to,cost;scanf(%ld %ld %ld”,&from,&to,&cost);Netfromto=cost;/cost

11、 为剩余量如果在现有网络上扩展剩余量为容量-已占用量最大流结果要加上已流入的量scanf(%ld %ld”,&Start,&End);long step;while (step=bfs()!=-1)/反搜增广路径并调整流量(Max_Flow+=step;long now=End;while (now!=Start)(long pre=Pathnow;Netprenow-=step;Netnowpre+=step;now=pre;print(Max_Flow);int main()(while (scanf(%ld %ld,&m,&n)!=EOF)(Ford_Fulkerson();return

12、 0;经常看见论文里面提到max flow/min cut theory，总是不太明白，今天花了点时间好好学习了一下， 发现其实也就挺简单的两概念。首先说说什么是流(flow)在一个有向图中，只有出去的边没有进来的边的节点叫做源(source)，只有进来的边没有出去的边的节 点叫做汇(sink)，其它的节点进来的边和出去的边应该是平衡的。边上可以加权值，假设对于一个交通图来说，可以认为边上的权重为一条道路上的最大流量。那么对于 图中任意两个节点来说，他们之间可以存在多条路径，每条路径上可以负载的最大流量应该是这条路径上 权重最小的那条边所能承载的流量(联想一下“瓶颈”这个词，或者木桶理论)。那

13、么所有的路径上所负载 流量之和也就是这两个节点之间所能通过的最大流了(max flow)。Ford和Fulkerson的算法很简单，把两个节点之间所有路径找到，然后.很直观，很简单。不知 道这么简单的算法怎么就用他们的名字命名了，明显谁都想得到的。此外，介绍一下什么是割。对于一个图中的两个节点来说，如果把图中的一些边去掉，刚好让他们之 间无法连通的话，这些被去掉的边组成的集合就叫做割了。最小割就是指所有割中权重之和最小的一个割。OK，现在开始进入正题，其实很easy。最大流-最小割定理(max flow/min cut theory):对于任意一个只有一个源和一个汇的图来说，从源到 汇的最大流等于对于最小割。英文版的是： For any network having a single origin and single destination node, the maximum possible flow from origin to destination equals the minimum cut value for all cuts in the network.