《最大流标号法ppt课件》由会员分享，可在线阅读，更多相关《最大流标号法ppt课件（29页珍藏版）》请在金锄头文库上搜索。
1、最大流问题_2命给定一个有向图G一(V,5),其中仅有一个点的入次为零称为发广源F记义v|仅有一个点的出次为零称为收点汝丫记为vty-其余辰称为中间点。对于G中的每一个弧(viv),相应地给一个数cij(eij尹0),称为弧(vi,v)的容量。我们把这样的D称为网络(或容量网络,记为G一(y,B,C)。所谓网络上的流,是指定义在弧集上的函数f二f(vv),并称f(vuv)为弧(vi,v)上的流量,简记为fii。标示方式:每条边上标示两个数字,第一个是容量,第二是流量可行流、可行流的流量、最大流。可行流是指满足如下条件的流:(1容量限制条件:对G中每条边(vv),有0(2)平衡条件:切币门历仪人
2、朱一河林(即中间点vi的物质输入量等于输出量)寺收点与发点,有:一广=一厂=(即v:发出的物资总量等于b接收的物资总量),IW是网络的总流量。可行流总是行流。所谓最大流行流。一个流人仑,否则称最大流问题但利用它与解。存在的,例如(0就是一个流量为0的可问题就是在容量网络中寻找流量最大的可当jy=cy,则称/寺边(w是饱和的,(仁不饲和。炬际止患一尔线性规划问题J图的密切关系,可以利用图直观简便地求给定容量网络G一(V,A,E),若点躬V被动外为两个非空集合V,和V,使v三V,v.EVo,则把弧集(V,V2称为分离vs和vt的显然,若把某割闵集的弧从网络h去掉;则从v:到v便不存在路。所以,直观
3、上说,割注:有向边也称为弧。集是从vs:到v的必经之路。对教材P259定义21的解释v1V2边集(vsv13,(vV1Jv33,(V2,vV33,(V3,Vt),(v4,vt)是G的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边,则图不连通,去掉这五条边中的任意1-4条,图仍然连通。割集的容量(简称割量)最小智其绿,Va)中所有在V在V的边的容量的和称为割集容量。例如下图中所示割集的容量为517二口5一史4一5EnlOAJJF22v(史T在容量网络的所有割集中,割集容量最小的割集称为最小割集(最小割。对于可行流/仪,我们把网络中俭=c)的弧称为饱和弧,倬fy0的弧称为非雾2若y是联结发点r和收点乙的一条链,我们规定链的方向是从5到fy则链上的弧被分成两类,前向弧、后向弧。设/是一个可行流,L是从v:到v的一条链,若k满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称t是(可行流/李)一条增广链。对最大流问题有下列定理:定理1容量网络中任一可行流的流量不超过其任一割集的容量。定理2川最大流H智川e割宋理角佩什容量网络中,最大流的流量等于最小割集的割量。推论!可行流f*=ff是最大流,当且仅当G中不存在关于广的增广链。
