《图和网络问题》由会员分享，可在线阅读，更多相关《图和网络问题（47页珍藏版）》请在金锄头文库上搜索。
1、第10章 图和网络问题,1. 图的遍历 2. 网络流量 3. 二分图,1. 图的遍历,图的深度优先遍历一般用栈结构支持 图的广度有限遍历一般用队列结构支持 图的深度优先遍历和广度优先遍历都可以产生一棵声称树 去掉连通无向图的接合点后，该无向图不再连通,2. 网络流量,2.1 网络流量的基本概念和性质 2.2 Ford_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和收点t c(u, v)是顶点对(u, v)的容量函数 常见问题：寻找从s到t的最大流量,s,a,b,d,c,e,t,6/8,4/6,5/5,2/2,3/5,4/6,5/5,2/2,2/2,2.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)是一个点对到实数的映射，它不是任意的，它必须满足流量约束条件,s,a,b,d,c,e,t,8,6,5,2,5,6,5,2,2,2.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) = 0,s,a,b
4、,d,c,e,t,6/8,4/6,5/5,2/2,3/5,4/6,5/5,2/2,2/2,2.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的值|f|为：,流量有这样的性质：如果f是G中的一个流量，S, T是G中的任意一个割集，则|f| = f(S, T),s,a,b,d,c,e,t,6/8,4/6,5/5,2/2,3/5,4/6,5
5、/5,2/2,2/2,2.1.6 流量的剩余容量和剩余图,流量f的剩余容量函数r定义为：对任意u,vV，r(u,v) = c(u,v) f(u, v) 流量f的剩余图是一个有向图R = (V, Ef)。其中，V是原图的顶点集合， Ef = (u, v) | r(u, v) 0 容易观察出：如果f(u, v) d-b-f就是M的一条扩张路径,a,b,c,d,e,f,3.2.4 无向图匹配的扩张路径定理,a,b,c,d,e,f,设M是G的一个匹配。若P是M的一条扩张路径，则把P的路径上所有边的匹配性质翻转，可以得到另一个匹配M，并且有|M| = |M|+1 无向图G的匹配是最大匹配，当且仅当G不包
6、含M的扩张路径,a,b,c,d,e,f,3.2.5 二分图,如果无向图G = (V, E)的顶点集V可以分为两个子集X和Y，满足X Y= ， XY= V，G的任何一条边的两个端点，一个在X中，另一个在Y中，则称图G是二分图，二部图，或偶图 定理：图G是二分图，当且仅当G中没有奇数长度的回路,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,3.2.6 可增广链解决引例问题,二分图的可扩张路径又称为二分图的可增广链。利用可增广链可以快速实现二分图的最大匹配 利用可增广链求二分图最大匹配的思路是：从空的匹配开始，循环地发现可增增广链并翻转该可增广链,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,3.3 二分图最大匹配的最大流方法,x1,x2,x3,x4,x5,y1,y2,y3,y4,y5,
