中考语文复习(写作实践)3

6.4网络的最大流

6.4.1网络最大流的有关概念网络流一般在有向图上讨论定义网络上每条弧的容量为其最大通过能力，记为cij，弧上的实际流量记为fij图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0

fij

cij平衡条件：满足上述条件的网路流称为可行流，总存在最大可行流当支路上fij=cij

，称为饱和弧最大流问题也是一个线性规划问题viA(vi)B(vi)16.4网络的最大流6.4.1网络最大流的有关概6.4.2割和割的容量定义：所谓割是指将容量网络中的发点（s）和收点（t）分割开，并使st的流中断的一组弧的集合。一般包含s点的成分中的节点集合用V表示，包含t点的成分中的节点集合用V表示割的容量是指割中各弧的容量之和

6.4.3最大流最小割定理（福特-富克森）

网络的最大流等于最小割集的容量86107759926.4.2割和割的容量定义：所谓割是指将容量网络中6.4.4求网络最大流的标号算法从任一个初始可行流出发，如0流基本算法：找一条从s到t点的增广链(augmentingpath)若在当前可行流下找不到增广链，则已得到最大流增广链中与s到t方向一致的弧称为前向弧，反之后向弧

增广过程：前向弧f

ij=fij+q,后向弧f

ij=fij

q

增广后仍是可行流

36.4.4求网络最大流的标号算法从任一个初始可行最大流最小割的标号法步骤第一步：标号过程，找一条增广链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)是后向弧，若fji>0，则节点j标号为[i

,q(j)]，表示从节点j

流向i，可增广q(j)=min[q(i),fji]；3、重复步骤2，可能出现两种情况：(1)节点t尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V中，4最大流最小割的标号法步骤第一步：标号过程，找一条增广链4最大流最小割的标号法步骤（续）未获标号节点在V中，V与V间的弧即为最小割集；算法结束(2)节点t获得标号，找到一条增广链，由节点t标号回溯可找出该增广链；到第二步第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t的标记值2、对增广链中的后向弧，令f=f

q(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷。一次只找一条增广链，增广一次换一张图。最后一次用广探法，以便找出最小割集5最大流最小割的标号法步骤（续）未获标号节点在Vs2143t8(0)5(0)6(0)5(0)10(0)2(0)9(0)7(0)9(0)(0,∞)(s,8)(1,8)(3,5)s2143t8(5)5(0)6(0)5(5)10(0)2(0)9(5)7(0)9(0)(0,∞)(s,7)(2,7)(4,7)P165例66s2143t8(0)5(0)6(0)5(0)10(0)2(0s2143t8(5)5(0)6(0)5(5)10(7)2(0)9(5)7(7)9(7)(0,∞)(s,3)(2,2)(4,2)(1,3)s2143t8(7)5(2)6(0)5(5)10(9)2(0)9(5)7(7)9(9)(0,∞)(s,1)(3,1)P165例6（续）(1,1)最小割集：{(3,t),(2,4)}最大流v(f*)=147s2143t8(5)5(0)6(0)5(5)10(7)2(0最大流最小割集的标号法举例(s+,)(s+,6)(2

,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5

,2)(4+,2)8最大流最小割集的标号法举例(s+,)(s+,6)(2,6最大流最小割集的标号法举例（续）(s+,)(s+,3)(2

,3)最小割集最小割集：{(s,1),(2,5),(2,4),(3,4)}最大流v(f*)=359最大流最小割集的标号法举例（续）(s+,)(s+,3)(2最大流标号法的复杂度讨论（了解）找一条增广链的计算量是容易估计的，不会超过O(n2)但是最多迭代多少次(即增广的次数)就很难估计，在最坏情况下，与边的容量有关；如上图：先增广suvt,然后增广svut，每次只能增广1个单位，故要增广4000次才能结束克服这种缺点的经验方法：尽量先用段数少的增广链尽量不重复前面出现过的增广链10最大流标号法的复杂度讨论（了解）找一条增广链的计算6.4.5多端网络问题116.4.5多端网络问题11

6.5最小费用流双权网络：每条弧不但有容量，还有单位流量的通过费用最小费用流问题：将各发点物资调运到各收点（或从各发点按最大流量调运到各收点），使总调运费用最小的问题两种解法：基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧基于可行弧集的最大流算法：从0费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主—对偶规划的解法。使用这种方法的还有运输问题、匹配问题126.5最小费用流双权网络：每条弧不但有容量，还有算法原理定理若是流量为的最小费用流，μ是关于的所有增广链中费用最小的增广链，那麽沿着μ去调整得到的新的可行流就是流量为的最小费用流。实现思路构造加权网络图（即扩展费用网络图），借助最短路算法寻找最小费用增广链。在该链上调整流量，得到增加流量后的最小费用流。循环往复直至达到要求为止。13算法原理定理若是流量为求最小费用流的步骤

第一步从零流f0开始.f0是可行流，也是流量为0时的最小费用流。

第二步对可行流fk构造加权网络W(fk):非饱和且非零流(0<fij<cij)弧上bij

原有弧（流量可以增加）

-bij

新加弧（流量可以减少）饱和弧上wij=-bij只能为反向弧（流量可以减少）零流弧上

wij=bij

只能为正向弧（流量可以增加）14求最小费用流的步骤第一步从零流f

求最小费用流的步骤（续）第三步在加权网络W(fk)中，寻找费用最小的增广链，也即求从使st的最短路。并将该增广链上流量调整至允许的最大值，得到一个新的流量fk+1（>

fk）第四步若当前可行流fk已达要求，则停止迭代；否则重复第二、三两步，一直到达到要求或在当前加权网络W(fk)中找不到增广链（也即找不出最短路）为止。当前可行流fk即为最小费用流。s321t算法举例(cij,bij)4,34,34,24,13,23,42,12,315求最小费用流的步骤（续）第三步在加s321t33212413s321t4,04,04,04,03,03,02,02,0(f0

=0)(w(f0

))s321t4,04,04,34,03,33,02,02,0(f1

=3)s321t3321-2413(w(f1

))-2举例（续1）16s321t33212413s321t4,04,04,0s321t4,04,04,34,23,33,02,02,2(f2

=5)s321t3321-241(w(f2

))-2-3-1s321t4,04,24,34,43,33,02,22,2(f3

=7)s321t332-24(w(f3

))-2-3-1-1-3举例（续2）17s321t4,04,04,34,23,33,02s321t4,24,44,34,43,33,02,22,2(f4

=9)s321t32-2