资源描述：
《最大流 最小费用流》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、4-6最大流一、几个概念定义（前向弧和背向弧）在任意一顶点之处，凡离开vi的有向弧称为vi的前向弧，凡进入vi的有向弧称为vi的背向弧。vivja称有向弧a为vi点的前向弧，vj点的背(后)向弧。定义（道路或通路）在任意一网络中，凡从始点v0（发点）开始到终点vn（收点）结束的一系列前向弧集合称为道路。记为P。v0vnv2v1v0vnv2v1V0——V1——Vnv0vnv2v1v0vnv2v1V0——V1——Vnv0vnv2v1V0——Vnv0vnv2v1v0vnv2v1v0vnv2v1V0——V1——V2——Vnv0vnv2v1v0vnv2v1V0——V
2、2——Vnv0vnv2v1v0vnv2v1v0vnv2v1V0——V2——V1——Vn定义：（截集或割集）如果N表示某网络中所有点的集合，将N分成两个子集S与S，使得发点v0在S内，收点vn在S内，则称（S，S）为分离发点与收点的截集。显然，SS=N，SS=，V0S，VnS注：N分为发点集S、中转点集R和收点集T。v0vnv2v1a截集a：v0v1，v0v2，v0vnv0vnv2v1b截集b：v1vn，v2vn，v0vnv0vnv2v1c截集c：v1vn，v1v2，v2v1，v0v2，v0vnv0vnv2v1d截集d：v0v1，v1v2，v2v1
3、，v2vn，v0vn定义（截集的容量）从S中各顶点到S中各顶点全部容量之和称为截集的容量（截量），用（S，S）表示。截集a:Ca=C01+C02+C0n截集b:Cb=C1n+C2n+C0n截集c:Cc=C1n+C12+C02+C0n截集d:Cd=C01+C21+C2n+C0nv0vnv2v1cSS在截集c中边v2v1是反向的，其容量视为零。v0vnv2v1dSS在截集d中边v1v2是反向的，其容量视为零。定义（最小截量）一个网络中，各种截集中容量最小的称为最小截量，用minC(S,S)表示。现在我们把一个网络看成是一个自来水管网络，煤气管网络，电力线网络或
4、公路网络，铁路网络，水运交通网络等，都可以归纳成一个运输问题，称为网络流，值得关心问题是在这样一个网络中最大流为多少？如果在一个网络中，有多个发点或收点，则我们可以将其变为只有一个发点和收点的网络。这只需增加一个新的总发点和一个新的总收点。从总发点到各个发点分别连接一条容量为+∞的弧，从各个收点到总收点分别连接一条容量为+∞的弧。这样就可将问题变为单发点和单收点的网络流问题。所以，以后我们只讨论一个发点和一个收点的网络流问题。在网络中，将通过弧（vi,vj）的运量记作fij，并称之为弧（vi,vj）上的流量。可行流：对于容量网络D=（V，A，C），每条弧（
5、vi,vj）都给定一个流量fij，当｛fij｝满足下列条件时，称为可行流。1°容量限制：对每条弧（vi,vj）∈A，有0≤fij≤cij2°平衡条件：对于中间点vi∈V，流入量等于流出量，即∑fji=∑fij对于发点vs和收点vt，则有vs发出总量等于vt收到总量，即∑fsj-∑fjs=∑fjt-∑ftj=v(f)称v(f)为可行流｛fij｝的流量。jjjjjj定义（最大流）可行流f=（），使得达到最大值截量C与流f的关系任一有向网络流，如果f是从发点到收点的流量，C(S,S)是任一个截集，则fC(S,S)。等号什么时候成立？定理（最小截量最大流）任一有
6、向网络流，从发点到收点的最大流量Maxf等于最小截量MinC(S,S)。即：Maxf=MinC(S,S)最大流算法设P=v0v1v2….vn为网络中的一条通路，记E(P)=(所有P中的前向弧和背向弧)令(P)=min(i,j)其中(i,j)=Cij-fij(vi,vj)是前向弧u+fij(vi,vj)是背向弧u-其中Cij是边容量，fij是流过边（vi，vj）的可行流，（0fijCij）定义：若(P)=0称P为f的饱和的；若(P)>0称P为f的不饱和的。定义：一条从发点到收点的f不饱和通路u称为f的增长道路（增流路或增广路），即满足：1.u+
7、(与u方向相同的弧)上：0fij0在一个网络中，f的增长道路的存在表示f不是最大流。所以。沿着P增加一个值为(P)的附加流，得到一个新流：f(i,j)+(P)(vi,vj)是前向弧u+f(i,j）=f(i,j)-(P)(vi,vj)是背向弧u-f(i,j）其他新流f(i,j)的流值为：f=f+(P)称f为基于P的修改流；显然f>f定理：当且仅当N中不包含f增长道路时，N中的流f是最大流。算法的基本思想：1从任一已知流(如零流)开始，递推地构造一个其值不断增加的流的序列。2在每一个新流构成之后，如果N
8、有f的可增长道路，则f不是最大流。3可得基于P的修改流f，并作为递
