图和网络问题.

第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.1.7瓶颈容量2.1.8最大流量最小割定理2.1.1网络的四元组表示(G,s,t,c)G=(V,E)是一个有向图图中有两个不同的顶点：源点s和收点tc(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也就是说对任意点对(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/23/54/65/52/22/22.1.4割集割集{S,T}是一个划分，它把顶点V划分成两个子集S和T，使得sS，tT。如果用c(S,T)表示割集{S,T}的容量，则有TvSuvucTSc,,,用f(S,T)表示割集{S,T}的交叉流量TvSuvufTSf,,,f(S,T)表示S到T的所有正流量之和，减去T到S的所有正流量之和2.1.5割集的性质如果f是G的一个流量，定义f的值|f|为：sVuvsfsVsff,,流量有这样的性质：如果f是G中的一个流量，{S,T}是G中的任意一个割集，则|f|=f(S,T)sabdcet6/84/65/52/23/54/65/52/22/22.1.6流量的剩余容量和剩余图流量f的剩余容量函数r定义为：对任意u,vV，r(u,v)=c(u,v)–f(u,v)流量f的剩余图是一个有向图R=(V,Ef)。其中，V是原图的顶点集合，Ef={(u,v)|r(u,v)0}容易观察出：如果f(u,v)c(u,v)，那么Ef中包含边(u,v)和(v,u)；如果原图u和v之间没有边，那么边(u,v)和(v,u)都不在Ef中sabdcet6/84/65/52/23/54/65/52/22/2sabdcet25222624245232.1.7瓶颈容量如果f是G中的一个流量，f的剩余图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是一个流量，那么下面的三个命题等价：1)存在一个容量为c(S,T)=|f|的割集{S,T}2)f是G中的最大流量3)不存在f的扩张路径最大流量最小割定理提供了寻找最大流量的一种方法：循环地寻找一条扩张路径，然后在扩张路径上的压入瓶颈容量的流量，可以使得流量增大；这个过程持续至不能再找到扩张路径为止。但Ford_Fulkerson方法是每一次都寻找最大扩张路径2.2Ford_Fulkerson法最大容量扩张sabdct8463546sabdct0/80/40/60/30/50/40/6sabdct84635460000000当前容量/路径容量：s当前容量/路径容量：8sa当前容量/路径容量：4sab000当前容量/路径容量：4sab4t当前容量/路径容量：4sab4当前容量/路径容量：8sa4当前容量/路径容量：3sac4当前容量/路径容量：3sac4t当前容量/路径容量：3sac4t当前容量/路径容量：3sac4当前容量/路径容量：8sa4当前容量/路径容量：s4sabdct8463546sabdct0/80/40/60/30/50/40/6sabdct8463546当前容量/路径容量：6s4d当前容量/路径容量：6s6dt当前容量/路径容量：6s6d当前容量/路径容量：6s6当前容量/路径容量：6结束6Ford_Fulkerson法分为若干相似的步骤，每一步都需要寻找一条具有最大瓶颈容量的剩余图的路径Ford_fulkerson法的步骤数量不会超过总的边数。这是因为，每一次查找最大瓶颈容量的剩余图时，会使得一条或多条边从不饱和到饱和状态。所以，步骤总数不会超过总边数每个步骤需要用深度优先完成最大瓶颈容量路径的搜索，可以用回溯的方式或分支限界的方式搜索最优路径。2.3最短路径法容量扩张sabdct8463546s/0a/1b/2d/1c/2t/28463546t与s的最短距离是2，并不是3利用最短路径法容量扩张求解最大容量的问题时，算法比较简单，也分为若干步（步骤总数也不会超过原图的边的总数）要利用Dijkstra算法发现从s到t的具有剩余容量的一条最短路径（路径长度的定义是路径上边的条数）对找到的最短路径进行容量扩张依次重复上面的步骤，直至不能发现可扩张路径为止2.4网络最大流举例动物们成功出逃动物园，它们要从下图左上角动物园出发，向着右下角它们的乐园进发。每段道路都有容量，为了拦截动物，要在道路上布置与道路容量一致的警力。问：最少需要多少警力？下图网格可达到200*200的规模最大流，最小割最短路径三者统一3.二分图3.1引例3.2二分图相关定义和性质3.3二分图最大匹配的最大流方法3.4二分图最大匹配的线性规划方法3.5二分图最大匹配的匈牙利树方法3.6二分图最大匹配应用举例3.1引例(红娘问题)x1x2x3x4x5y1y2y3y4y53.2二分图相关定义和性质3.2.1匹配和最大匹配3.2.2匹配点和自由点3.2.3交替回路和扩张路径3.2.4无向图匹配的扩张路径定理3.2.5二分图3.2.6可增广链3.2.1匹配和最大匹配如果G=(V,E)是一个（普通的）无向图，如果存在边集ME，使得M中所有的边都没有公共顶点，则称M是G的一个匹配M的边数记为|M|边数最多的匹配称为最大匹配abcdabcd3.2.2匹配点和自由点如果M是G的一个匹配，边e既属于E也属于M，则称e是匹配的如果顶点vV，且存在一条匹配边与v关联，则称顶点v是被许配的；否则，称v是自由的abcde3.2.3交替回路和扩张路径设M是G的一个匹配。若G中存在一条路径p，p是由匹配边和非匹配边交替构成的，则称p为交替路径，其长度用|p|表示如果交替路径p的两个端点重合，则称p为交替回路如果交替路径p的两个端点都是自由的，则称p为M的扩张路径（或者称为可增广链）下图中e-d-b-f就是M的一条扩张路径abcdef3.2.4无向图匹配的扩张路径定理abcdef设M是G的一个匹配。若P是M的一条扩张路径，则把P的路径上所有边的匹配性质翻转，可以得到另一个匹配M，并且有|M|=|M|+1无向图G的匹配是最大匹配，当且仅当G不包含M的扩张路径abcdef3.2.5二分图如果无向图G=(V,E)的顶点集V可以分为两个子集X和Y，满足XY=，XY=V，G的任何一条边的两个端点，一个在X中，另一个在Y中，则称图G是二分图，二部图，或偶图定理：图G是二分图，当且仅当G中没有奇数长度的回路x1x2x3x4x5y1y2y3y4y53.2.6可增广链解决引例问题二分图的可扩张路径又称为二分图的可增广链。利用可增广链可以快速实现二分图的最大匹配利用可增广链求二分图最大匹配的思路是：从空的匹配开始，循环地发现可增增广链并翻转该可增广链x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y53.3二分图最大匹配的最大流方法x1x2x3x4x5y1y2y3y4y53.4二分图最大匹配的线性规划方法x1x2y1y2y3y412345}10{,,,,max5432154321，zzzzzzzzzzsx1最多被许配一次x2的约束y1的约束y2的约束y3的约束y4的约束1111115241354321zzzzzzzzzz3.5二分图最大匹配的匈牙利树方法3.5.1交替路径树3.5.2在二分图中发现交替路径树3.5.3匈牙利树3.5.4利用匈牙利树求解二分图的最大匹配3.5.1交替路径树x1x2x3x4x5y1y2y3y4y5x1y2y3x2x3y1y4y5二分图中的交替路径树以一个自由节点作为根。根到叶子节点的路径上，不匹配与匹配的连线交替出现。每个节点的下面包含所有可能的子节点3.5.2在二分图中发现交替路径树x1x2x3x4x5y1y2y3y4y5x1y2y3x2x3y1y4y5用广度优先遍历的方式发现交替路径树某个节点在交替路径树中出现之后，便不再出现3.5.3匈牙利树x1x2x3x4x5y1y2y3y4y5x4y2y3x1x3如果最终构造的交替路径树的叶子节点全部是已许配了的节点，则这棵树就是匈牙利树出现匈牙利树就意味着通过这些节点和边不可能提高匹配的数量3.5.4利用匈牙利树求解二分图的最大匹配1)初始匹配为空，匹配数设为0。转入下步。2)如果节点集为空，则转入5)；否则转入下步。3)用广度优先遍历法求得一棵交替路径树。转入下步。4)如果交替路径树是匈牙利树，则匹配数增加该匈牙利树中的匹配数，并在图中删除该树转入步骤2)；否则，翻转交替路径树上的由根到叶子的最长路径，转入步骤2）。5)返回并退出匹配总数。3.6二分图最大匹配应用举例3.6.1同声传译问题3.6.2狗和主人问题3.6.3投篮问题3.6.1同声传译问题某机构需要6种语言的同声传译，翻译人员共5名，他们能进行同声传译工作的语言情况如图所示。问：最多能有几门语言能被同时进行同声传译？3.6.2狗和主人问题主人和狗要去旅游。主人的路线给定（用一串坐标给出“人景点”），狗要游览的“狗景点”也用若干个坐标给出。狗必须在主人到达每一个人景点时与主人会合。已知狗的速度是主人的两倍，并且要求：主人在两个相邻的“人景点”之间的行程上，狗最多只能游览一个“狗景点”。请计算在这趟行程上，狗最多能够游览多少个“狗景点”3.6.3投篮问题n个球要进若干个瓶子里，要求：1)按照编号1—n依次放置2)小号球在下，大号球在上3)如果瓶子中的篮球数大于1，则相邻两个球之和必须为素数问：至少需要多少个瓶子？1234561,2,3,4,5,6111895671012341,2,3,4,5,6,7,8,9,10,112345678910111234561,2,3,4,5,61234561234561234561234566–4=21234567891011123456789101112345678