网路的最大流和最小截.ppt

《网路的最大流和最小截.ppt》由会员分享，可在线阅读，更多相关《网路的最大流和最小截.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.4 网路的最大流和最小截网路的最大流和最小截 6.4.1 网路的最大流的概念网路的最大流的概念网路流一般在有向图上讨论网路流一般在有向图上讨论定义网路上支路的定义网路上支路的容量容量为其最大通过能力，记为为其最大通过能力，记为 cij，支路上的实际支路上的实际流量流量记为记为 fij 图中规定一个发点图中规定一个发点s s，一个收点，一个收点t t节点没有容量限制，流在节点不会存储节点没有容量限制，流在节点不会存储容量限制条件容量限制条件：0 fij cij 平衡条件平衡条件：满足上述条件的网路流称为满足上述条件的网路流称为可行流可行流，总存在，总存在最大可行流最大可行流 当支路上当支路上

2、 fij=cij ，称为称为饱和弧饱和弧 最大流问题也是一个线性规划问题最大流问题也是一个线性规划问题viA(vi)B(vi)1 6.4.2 截集与截集容量截集与截集容量定义定义：把网路分割为两个成分的弧的最小集合，其中一：把网路分割为两个成分的弧的最小集合，其中一 个成分包含个成分包含 s 点，另一个包含点，另一个包含 t 点点。一般包含一般包含 s 点的成分中的节点集合用点的成分中的节点集合用V表示，包含表示，包含 t 点点的成分中的节点集合用的成分中的节点集合用V表示表示截集容量截集容量是指截集中正向弧的容量之和是指截集中正向弧的容量之和 福特福特-富克森定理富克森定理：网路的最大流等于

3、最小截集容量：网路的最大流等于最小截集容量2 6.4.3 确定网路最大流的标号法确定网路最大流的标号法从任一个初始可行流出发，如从任一个初始可行流出发，如 0 流流基本算法：找一条从基本算法：找一条从 s 到到 t 点的点的增广链增广链(augmenting path)若在当前可行流下找不到增广链，则已得到最大流若在当前可行流下找不到增广链，则已得到最大流增广链中与增广链中与 s 到到 t 方向一致的弧称为方向一致的弧称为前向弧前向弧，反之，反之后向弧后向弧 增广过程：前向弧增广过程：前向弧 f ij=fij+q q,后向弧后向弧 f ij=fij q q 增广后仍是可行流增广后仍是可行流 3

4、 最大流最小截的标号法步骤最大流最小截的标号法步骤第一步：标号过程，找一条增广链第一步：标号过程，找一条增广链1、给源点给源点 s 标号标号s+,q q(s)=，表示从，表示从 s 点有无限流出潜力点有无限流出潜力2、找出与已标号节点找出与已标号节点 i 相邻的所有未标号节点相邻的所有未标号节点 j，若，若(1)(i,j)是前向弧且饱和，则节点是前向弧且饱和，则节点 j 不标号；不标号；(2)(i,j)是前向弧且未饱和，则节点是前向弧且未饱和，则节点 j 标号为标号为i+,q q(j)，表示从节点，表示从节点 i 正向正向流出，可增广流出，可增广 q q(j)=minq q(i),cij fi

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

6、点在在 V 中，中，V 与与 V 间的弧即为最小截集；算法结束间的弧即为最小截集；算法结束(2)节点节点 t 获得标号，找到一条增广链，由节点获得标号，找到一条增广链，由节点 t 标号回溯可找出该增标号回溯可找出该增广链；到第二步广链；到第二步4 最大流最小截的标号法步骤最大流最小截的标号法步骤第二步：增广过程第二步：增广过程1、对、对增广链中的前向弧，令增广链中的前向弧，令 f=f+q q(t)，q q(t)为节点为节点 t 的标记的标记值值2、对对增广链中的后向弧，令增广链中的后向弧，令 f=f q q(t)3、非增广链上的所有支路流量保持不变、非增广链上的所有支路流量保持不变第三步：抹除

7、图上所有标号，回到第一步第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷探法进行更快捷一次只找一条增广链，增广一次换一张图一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集最后一次用广探法，以便找出最小截集5最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)6最大流最小截集的标号法举例最大流最小截集的标号法举例(s+,)(s+,3)(2,3)最小截集最小截集7

8、最大流标号法的复杂度讨论最大流标号法的复杂度讨论找一条增广链的计算量是容易估计的，不会超过找一条增广链的计算量是容易估计的，不会超过O(n2)但是最多迭代多少次但是最多迭代多少次(即增广的次数即增广的次数)就很难估计，在最坏就很难估计，在最坏情况下，与边的容量有关；如上图：先增广情况下，与边的容量有关；如上图：先增广 s u v t,然后增广然后增广 s v u t，每次只能增广，每次只能增广 1 个单位，故要增个单位，故要增广广4000次才能结束次才能结束克服这种缺点的经验方法：克服这种缺点的经验方法：尽量先用段数少的增广链尽量先用段数少的增广链尽量不重复前面出现过的增广链尽量不重复前面出现

9、过的增广链8 6.4.4 多端网路问题多端网路问题9 最小费用最大流最小费用最大流双权网路双权网路：每条弧不但有容量，还有单位流量的通过费用：每条弧不但有容量，还有单位流量的通过费用两种解法：一种基于最小费用路径算法；一种基于可行弧集两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法的最大流算法基于最小费用路径算法基于最小费用路径算法：总是在当前找到的最小费用的路径：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧值费用的弧基于可行弧集的最大流算法基于可行弧集的最大流算法：从：从 0

10、费用弧集开始应用最大流费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界算法，然后根据计算信息提高费用的限界P，使可行弧集增，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主算法是一种主-对偶规划的解法。使用这种方法的还有运输对偶规划的解法。使用这种方法的还有运输问题、匹配问题问题、匹配问题10 以最短路为基础汇总网路上的流以最短路为基础汇总网路上的流在电路网中每两点之间都有中继电路群需求，但并不是任在电路网中每两点之间都有中继电路群需求，但并不是任两点都有物理传输链路两点都有物理传输链路根据两点间最短传输路径将该两点间的电路需求量加载到根据两点间最短传输路径将该两点间的电路需求量加载到这条传输路径上去：设这条传输路径上去：设 a25=10 是节点是节点2 和和 5 之间的电路需求，之间的电路需求，节点节点2 和和 5 之间的最短传输路径为之间的最短传输路径为 2 1 3 5，则加载过，则加载过程为程为:T21=T21+10,T13=T13+10,T35=T35+10；Tij 是传输链路是传输链路 i j 上加载的电路数；当所有点间电路都加载完则算法结上加载的电路数；当所有点间电路都加载完则算法结束束11