5.6Ford-FullkersonPPT推荐.ppt
- 文档编号:3777481
- 上传时间:2023-05-02
- 格式:PPT
- 页数:12
- 大小:124KB
5.6Ford-FullkersonPPT推荐.ppt
《5.6Ford-FullkersonPPT推荐.ppt》由会员分享,可在线阅读,更多相关《5.6Ford-FullkersonPPT推荐.ppt(12页珍藏版)》请在冰点文库上搜索。
5.6Ford-Fullkerson最大流标号算法,引言:
@#@将最大流的方法具体化,任意给定了网络的一个容许流分布f后。
@#@标号过程:
@#@检查网络中是否存在关于f的增流路径.如果在标号过程中最后能标到结点t,即存在s到t的增流路径。
@#@深度优先否则由定理5.5.2此时的f是最大流分布,其流量W为最大流.增流过程:
@#@确定一条s到t的增流路径并修正这条路上的流.得到f.,在标号时,首先对源s标以(-,).设e是连接的边,若u已标号而v尚未标号.正向标号:
@#@如果e=f(e)f(e)0,则标号方向为负,v得到的标号为(u-,v),其中v=min(u,f(e)在标号过程中,每个结点最多进行一次标号,有可能重复标记时,请按某种策略取舍,如增量最大、边的条数最少即深度优先等,u,v,u,v,以上标号方法,在标完s后,下一个待标的结点如何确定,当然是s的后继结点,但有时某个结点是多个结点的后继点,该如何处理呢?
@#@深度优先,其实是任选下一个结点,不成功则回溯,当然人工操作时,可以选来量最大的边或从未处理结点中,查找结点编号最小的点.也可以随意选择!
@#@不限制!
@#@,以上标号方法,在标完s后,下一个待标的结点如何确定,当然是s的后继结点,但有时某个结点是多个结点的后继点,该如何处理呢?
@#@取增加最大的结点.具体编码实现时不可行!
@#@每个点都标记到了,则寻找一条增流路.a标记(s+,3),b标记(a+,3),t标记(b+,2)t加2来源于b,b加2源于a,a加2源于s.,S,以上标号方法,在标完s后,下一个待标的结点如何确定,当然是s的后继结点,但有时某个结点是多个结点的后继点,该如何处理呢?
@#@取增加最大的结点.每个点都标记到了,则寻找一条增流路.t加2来源于b,b加2源于a,a加2源于s.,删除重新开编,结点b有3条来路,从d流过来最大,故选d.人工可以确定,但程序方式不好确定,换成其它方式再进行增流scd-t,删除重新开编,结点b有3条来路,从d流过来最大,故选d.再进行增流scd-t,删除重新开编,寻找s-a-d-t深度优先要回溯!
@#@,删除重新开编,寻找s-a-d-t,删除重新开编,s到a已饱和,a-c又无流量,故a不能动!
@#@b可在c的基础上增加1,增加到b上的量无法流出,故不行!
@#@c增加的2后无法运出去!
@#@故是最大流!
@#@,S=s,c,b,a,S=d,t(i,j)边(iS,jS)为割切!
@#@正向边均饱和=(c,d)+(a,d)+(b,t)=2+1+2=5逆向边当前流量均为0,(d,b)=0割切的容量=正向边的容量和=2+1+2有一个割切的容量=割切的静流量,故为最大值,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 5.6 Ford Fullkerson