网路的最大流和最小截

《网路的最大流和最小截》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.4网路的最大流和最小截6.4.1网路的最大流的概念网路流一般在有向图上讨论定义网路上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0fijcij平衡条件：满足上述条件的网路流称为可行流，总存在最大可行流当支路上fij=cij，称为饱和弧最大流问题也是一个线性规划问题viA(vi)B(vi)16.4.2截集与截集容量定义：把网路分割为两个成分的弧的最小集合，其中一个成分包含s点，另一个包含t点。一般包含s点的成分中的节点集合用V表示，包含t点的成分中的节

2、点集合用V表示截集容量是指截集中正向弧的容量之和福特-富克森定理：网路的最大流等于最小截集容量26.4.3确定网路最大流的标号法从任一个初始可行流出发，如0流基本算法：找一条从s到t点的增广链(augmentingpath)若在当前可行流下找不到增广链，则已得到最大流增广链中与s到t方向一致的弧称为前向弧，反之后向弧增广过程：前向弧fij=fij+q,后向弧fij=fijq增广后仍是可行流3最大流最小截的标号法步骤第一步：标号过程，找一条增广链1、给源点s标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i相邻的所有未标号节点j

3、，若(1)(i,j)是前向弧且饱和，则节点j不标号；(2)(i,j)是前向弧且未饱和，则节点j标号为[i+,q(j)]，表示从节点i正向流出，可增广q(j)=min[q(i),cijfij]；(3)(j,i)是后向弧，若fji=0，则节点j不标号；(4)(j,i)是后向弧，若fji>0，则节点j标号为[i,q(j)]，表示从节点j流向i，可增广q(j)=min[q(i),fji]；3、重复步骤2，可能出现两种情况：(1)节点t尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V中，未获标号节点在V中，V与V

4、间的弧即为最小截集；算法结束(2)节点t获得标号，找到一条增广链，由节点t标号回溯可找出该增广链；到第二步4最大流最小截的标号法步骤第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t的标记值2、对增广链中的后向弧，令f=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集5最大流最小截集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+

5、,)(s+,5)(2+,2)(5,2)(4+,2)6最大流最小截集的标号法举例(s+,)(s+,3)(2,3)最小截集7最大流标号法的复杂度讨论找一条增广链的计算量是容易估计的，不会超过O(n2)但是最多迭代多少次(即增广的次数)就很难估计，在最坏情况下，与边的容量有关；如上图：先增广suvt,然后增广svut，每次只能增广1个单位，故要增广4000次才能结束克服这种缺点的经验方法：尽量先用段数少的增广链尽量不重复前面出现过的增广链86.4.4多端网路问题96.4.5最小费用最大流双权网路：每条弧不但有容量，还有单位流量的通过费用两种解

6、法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧基于可行弧集的最大流算法：从0费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这种方法的还有运输问题、匹配问题106.4.5以最短路为基础汇总网路上的流在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到这条传

7、输路径上去：设a25=10是节点2和5之间的电路需求，节点2和5之间的最短传输路径为2135，则加载过程为:T21=T21+10,T13=T13+10,T35=T35+10；Tij是传输链路ij上加载的电路数；当所有点间电路都加载完则算法结束11