图和网络问题ppt课件.ppt

《图和网络问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章图和网络问题1.图的遍历2.网络流量3.二分图1.图的遍历图的深度优先遍历一般用栈结构支持图的广度有限遍历一般用队列结构支持图的深度优先遍历和广度优先遍历都可以产生一棵声称树去掉连通无向图的接合点后，该无向图不再连通2.网络流量2.1网络流量的基本概念和性质2.2Ford_Fulkerson法最大容量扩张2.3最短路径法容量扩张2.4网络最大流举例2.1网络流量的基本概念和性质2.1.1网络的四元组表示2.1.2容量函数和流量函数2.1.3流量函数约束条件2.1.4割集2.1.5割集的性质2.1.6流量的剩

2、余容量和剩余图2.1.7瓶颈容量2.1.8最大流量最小割定理2.1.1网络的四元组表示(G,s,t,c)G=(V,E)是一个有向图图中有两个不同的顶点：源点s和收点tc(u,v)是顶点对(u,v)的容量函数常见问题：寻找从s到t的最大流量sabdcet6/84/65/52/23/54/65/52/22/22.1.2容量函数在网络(G,s,t,c)中，如果u、v是V中的任意顶点，则容量函数c(u,v)表示流经u、v的最大允许流量若边(u,v)E，则表示u到v的容量c(u,v)>0；否则,c(u,v)=0也就是说对任

3、意点对(u,v)，c(u,v)0流量函数f(u,v)是一个点对到实数的映射，它不是任意的，它必须满足流量约束条件sabdcet8652565222.1.3流量函数约束条件反对称。对任意u,vV，有f(u,v)=-f(v,u)。如果f(u,v)>0，就称f(u,v)是u到v的流量容量约束。对任意u,vV，有f(u,v)c(u,v)。如果f(u,v)=c(u,v)，则称边(u,v)是饱和的流量守恒。对任意uV-{s,t}，有vf(u,v)=0对任意vV，有f(v,v)=0sabdcet6/84/65/52

4、/23/54/65/52/22/22.1.4割集割集{S,T}是一个划分，它把顶点V划分成两个子集S和T，使得sS，tT。如果用c(S,T)表示割集{S,T}的容量，则有用f(S,T)表示割集{S,T}的交叉流量f(S,T)表示S到T的所有正流量之和，减去T到S的所有正流量之和2.1.5割集的性质如果f是G的一个流量，定义f的值

5、f

6、为：流量有这样的性质：如果f是G中的一个流量，{S,T}是G中的任意一个割集，则

7、f

8、=f(S,T)sabdcet6/84/65/52/23/54/65/52/22/22.1.6流

9、量的剩余容量和剩余图流量f的剩余容量函数r定义为：对任意u,vV，r(u,v)=c(u,v)–f(u,v)流量f的剩余图是一个有向图R=(V,Ef)。其中，V是原图的顶点集合，Ef={(u,v)

10、r(u,v)>0}容易观察出：如果f(u,v)

11、剩余图R中，由s到t的有向路径p称为流量f的扩张路径。沿着扩张路径p的所有的阶段剩余流量中的最小值称为p的瓶颈容量如果把流量f沿着扩张路径p再压入瓶颈容量的流量，则这条路径上的流量饱和sabdcet6/84/65/52/23/54/65/52/22/2sabdcet25222624245232.1.8最大流量最小割定理网络(G,s,t,c)中，如果f是一个流量，那么下面的三个命题等价：存在一个容量为c(S,T)=

12、f

13、的割集{S,T}f是G中的最大流量不存在f的扩张路径最大流量最小割定理提供了寻找最大流量的一种方法

14、：循环地寻找一条扩张路径，然后在扩张路径上的压入瓶颈容量的流量，可以使得流量增大；这个过程持续至不能再找到扩张路径为止。但Ford_Fulkerson方法是每一次都寻找最大扩张路径2.2Ford_Fulkerson法最大容量扩张sabdct8463546sabdct0/80/40/60/30/50/40/6sabdct84635460000000当前容量/路径容量：s当前容量/路径容量：8sa当前容量/路径容量：4sab000当前容量/路径容量：4sab4t当前容量/路径容量：4sab4当前容量/路径容量：8sa

15、4当前容量/路径容量：3sac4当前容量/路径容量：3sac4t当前容量/路径容量：3sac4t当前容量/路径容量：3sac4当前容量/路径容量：8sa4当前容量/路径容量：s4sabdct8463546sabdct0/80/40/60/30/50/40/6sabdct8463546当前容量/路径容量：6s4d当前容量/路径容量：6s6dt当前容量/路径容