6图与网络的分析2.pptVIP

6.4 网络的最大流 6.4.1 网络最大流的有关概念 网络流一般在有向图上讨论 定义网络上每条弧的容量为其最大通过能力，记为 cij ，弧上的实际流量记为 fij 图中规定一个发点s，一个收点t 节点没有容量限制，流在节点不会存储 容量限制条件：0? fij ? cij 平衡条件： 6.4.2 割和割的容量 定义：所谓割是指将容量网络中的发点（ s ）和收点（ t ）分割开，并使 s t 的流中断的一组弧的集合。 一般包含 s 点的成分中的节点集合用V表示，包含 t 点的成分中的节点集合用V表示 割的容量是指割中各弧的容量之和 6.4.4 求网络最大流的标号算法 从任一个初始可行流出发，如 0 流 基本算法：找一条从 s 到 t 点的增广链(augmenting path) 若在当前可行流下找不到增广链，则已得到最大流 增广链中与 s 到 t 方向一致的弧称为前向弧，反之后向弧 最大流最小割的标号法步骤 第一步：标号过程，找一条增广链 1、给源点 s 标号[s+,q(s)=?]，表示从 s 点有无限流出潜力 2、找出与已标号节点 i 相邻的所有未标号节点 j，若 (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 )是后向弧，若 fji0，则节点 j 标号为[i?, q( j )]，表示 从节点 j 流向 i，可增广 q( j )=min[q( i ), fji] ； 3、重复步骤 2，可能出现两种情况： (1) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流 v( f ) 就是最大流；所有获标号的节点在 V 中， 最大流最小割的标号法步骤（续） 未获标号节点在 V 中，V 与 V 间的弧即为最小割集；算法结束 (2)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增广链；到第二步 第二步：增广过程 1、对增广链中的前向弧，令 f?=f +q(t)，q(t) 为节点 t 的标记值 2、对增广链中的后向弧，令 f?=f ?q(t) 3、非增广链上的所有支路流量保持不变 第三步：抹除图上所有标号，回到第一步 以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷。一次只找一条增广链，增广一次换一张图。最后一次用广探法，以便找出最小割集 最大流最小割集的标号法举例 最大流最小割集的标号法举例（续） 最大流标号法的复杂度讨论（了解） 找一条增广链的计算量是容易估计的，不会超过O(n2) 但是最多迭代多少次(即增广的次数)就很难估计，在最坏情况下，与边的容量有关；如上图：先增广 s ? u ? v ? t , 然后增广 s ? v ? u ? t，每次只能增广 1 个单位，故要增广4000次才能结束 克服这种缺点的经验方法： 尽量先用段数少的增广链 尽量不重复前面出现过的增广链 6.4.5 多端网络问题 6.5 最小费用流 双权网络：每条弧不但有容量，还有单位流量的通过费用 最小费用流问题：将各发点物资调运到各收点（或从各发点按最大流量调运到各收点），使总调运费用最小的问题 两种解法： 基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧 基于可行弧集的最大流算法：从 0 费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主—对偶规划的解法。使用这种方法的还有运输问题、匹配问题 * hw * 满足上述条件的网路流称为可行流，总存在最大可行流 当支路上 fij = cij ，称为饱和弧 最大流问题也是一个线性规划问题 vi A(vi) B(vi) 6.4.3 最大流最小割定理（福特-富克森） 网络的最大流等于最小割集的容量 8 6 10 7 7 5 9 9 增广过程：前向弧 f?ij=fij +q , 后向弧 f?ij=fij ?q 增广后仍是可行流 s 2 1 4 3 t 8(0) 5(0) 6(0) 5(0) 10(0) 2(0) 9(0) 7(0) 9(0) (0,∞) (s,8) (1,8) (3,5) s 2 1 4 3 t 8(5) 5(0) 6(0) 5(5) 10(0)