图的基本应用2

《图的基本应用2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图的基本算法2K最大流问题规划模型：maxv(/)'工厶二为九,岭H儿，片屮间节点流入量等于流出量jks.t.《工人=工九=v(y)发点流出量与终点流入量为流值jk0

2、c(e)>0}・令E",返回第)步・示例:3V：(b)4,4图8.5单向调整过程算法二：最优算法算法

3、&2最大流的双向调整法——Ford-Fulkerson算决gl设N“宀“J是初始流.」T表N(f)中以s为根的有序树“表在有序树T中已生长完成的顶点：T中毎个顶点f如下获得2个标号心与仏3〉・设P是T上唯一的I路•则厶3)表示P的容備仏(。)表示在P±v的父顶点，即有(&⑷(&⑸/i

4、步.第5步取(“2)WCT，巧，令T=TJ{v}9I](u)=min{li(a)tcc(«fr)}»第6步若uH"转第4步.第7步逆向追踪求出s-t路P・第8步对(叭“)eE(P),令f(u^v)十/i(0,l2(v)=十心f(u.v)—/

5、(0,以“)=_叭转第1步・示例：N与/N(0T与PcniVz/(3.+Vt)」U.JVi(5,+5)Il”巾(3,“)5(<»,$)V

6、va]tVi3Ip=Mf,c"p)=350,3—£3内£(3.4Vi)03.5j0,5^力(2,+巧o.尢AV>(3,4-J)/t讥3,3tVi/p=冋人CS=3s3,3V：$-<•2gO/(I.*V1)J忖Jo

7、Vj3/dVH2")Ij^2・+g)5(®.5)p=wiV2/,r(p)=1v；3；3"rVi«Vj(!,+Vi)罕4L

8、v>(i,^Js（8.£）没有s4略V.3・3t5*3t『是最大流进一步讨论约束条件05厶5©,匕匕wE屮的容量值若为整数，求解上述线性规划，必得整数最大流，即各条边上的流量为整数。3、最小费用流规划模型：価工為厶时戶E（工厶二工九‘岭"岭jkMSA/=X九=V（f）jk算法一:算法&3最小代价流的负回路算法设N=(乙J)是具代价的网络.第1步求流值a的流几第2步作具代价的伴随网络W第3步若N⑴没有负回路J是流值入的呂小代价流，停.第4步设Q是负回路•作/关干Q的修改

9、流了.令U了，转第2步.例&】0求图8・8(a)的流值4的报小代价流■设图&8(6)的流为初始流•其解的过程如图8・9・示例:N与/N⑴2£中£)■ycQ

10、)tA—val/}.作于关于P和<5的修改流A・令f=Atval/—val/+<5,转第2步.示例：N与/N(f)PS0,4,2VQ3Jv,10.3,6tvalf=0s3I力0Vi3,6tP二SVztCP〉专A■J0,42V[3W'i0,3,6tvalf=0+3«=3&V

11、3.6t•■P=助"“c'(p)=1A-valf-1Cl⑷]1乡/.卜,4,2H0.3.6tval(^3+1=4•・•「val/=4••・f是流值4的最小^价流••算法三：顶点标号算法解先给％•标以（+,&）,3S=+8.检查％•的未标号的邻接点vbv2,v3,发现血点满足vsv2E,且几2=2

12、min{2,+°°}=2,给巾以标号（匕+,2）.同理给内点以标号（%+,1）•检查卩2点的未标号的邻接点「5,卩6,发现"5满足卩2"5丘匕且/25=0

13、v5eE,且/

14、5=3>0,令