网络最大流课件.ppt

《网络最大流课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章   网络最大流网络最大流问题50年代福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径，我们也可以将一个有向图看作一个流网络来解决另一类型的问题。流网络比较适合用来模拟液体流经管道、电流在电路网络中的运动、信息网络中信息的传递等等类似的过程。问题的提出在一个输油管网中，有生产石油的油井、储存石油的油库、转运石油的中间泵站，同时，还有各种口径不同的输油管。当一个输油管网给定后，单位时间内最

2、多可把多少石油从油井输送到油库？具体方案如何？分析：就输油管网络问题，可用顶点表示油井、油库和中间泵站，用有向边表示输油管，用有向边上的权表示单位时间沿相应的输油管可以输送石油的最大数量（容量）。如果我们把图看做输油管道网，为起点，为终点，为中转站，边上的数表示该管道的最大输油能力，问应该如何安排各管道输油量，才能使从到的总输油量最大？问题的提出管道网络中每边的最大通过能力即容量是有限的，实际流量也不一定等于容量，上述问题就是要讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题

3、。vsv1v3vtv2v48799562510容量发点（源）收点（汇）中间点容量网络网络有向图D=（V，A，C）网络上流的基本概念vsv1v3vtv2v48799562510流vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)运输问题中，每个运输方案就是一个流可行流网络最大流问题且满足此为一个特殊的线性规划问题，将会看到利用图的特点，解决这个问题的方法要比单纯形法较为直观方便。设是网络D=（V，A，C）的一个可行流（v1，v2）是饱和的2、如果0≤fij

4、，该弧是非饱和弧；（v1，v2）是不饱和的间隙为12=c12-f12=5-3=21、如果fij=cij，该弧是饱和弧；弧关于流的分类fij=5cij=5v1v2fij=3cij=5v1v2设是网络D=（V，A，C）的一个可行流（v1，v2）是0流弧4、如果fij>0，该弧是非0弧；（v1，v2）是非0弧3、如果fij=0，该弧是0流弧；弧关于流的分类fij=0cij=5v1v2fij>0cij=5v1v2链及可增广链链在最大流问题中，研究的是有向网络图。但是在求最大流的方法中，则要使用无向网络中的链。vsv

5、1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非0流弧可增广链vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)非饱和弧割集和割集的容量设有网络D={V，A，C}，点vs与点vt的是集合V中的任意两点，若点集V被剖分成两个非空集合，使，记以中的点为始点，的A中弧的集合记为则称这个弧的集合是分离点vs与点vt的割集（又称截集）。中的点为终点割集的容量是割集中各弧的容量之和，用表示。割集的容量为9+9=18割集KKvsv

6、1v3vtv2v48(8)7(5)9(4)5(5)6(1)2(0)5(4)10(8)9(9)考虑KK的不同画法vsv1v3vtv2v48(8)7(5)9(4)9(9)5(5)6(1)2(0)5(4)10(8)割集割集容量基本定理(可行流与割集的关系)由于有限网络的割集只有有限多个，则截集容量的集合是有限的实数集合，令称割集容量为C0的割集为D的最小割集。（瓶颈）§2割切-定理6.1证明－1[]wffSjSijiij=-åÎÎ,∵又∵0≤fij≤cij∴fij－fji≤fij≤cij因为割集是任意的，所以得证。

7、[]=≤-=ååÎÎÎÎSjSiijSjSijiijcffw,,C(S,)S∴证明增广路定理：证明：1必要性v(f)为最大流，则不存在可增广链；因为若存在增广链，则v(f)不为最大流。2充分性不存在可增广链，则v(f)为最大流；若网络流图G中不存在可增广路，则考察所有s到t的路径，将满足增广条件路径连接的节点并入集合S中，遇到不满足条件点时停止；T=V/S，[S,T]为s-t割集。这时，对于任意弧(i,j)，若是前向弧，fij=cij，若是逆向弧，fji=0,下式成立，v(f)为最大流,C[S,T]为最小割。

8、[]==-=ååÎÎÎÎTjSiijTjSijiijcffw,,C(S,)T∴最大流-最小割定理：v(fmax)=Cmin[S,T];这样就得到了一个寻求最大流的方法(算法思想)：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。沿着这条链从vs到vt输送流，还有潜力可挖，