图论中的圈与块

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,浙江省2006年集训讲义,*,图论中的圈与块,绍兴县柯桥中学 黄劲松,基本概念,圈,(,环,),割点,割边,(,桥,),块,强连通子图,(,强连通分量,(,支,块,),10/11/2024,2,浙江省2006年集训讲义,圈及其相关知识,MST(,最小生成树,),另类算法,最小环问题,10/11/2024,3,浙江省2006年集训讲义,MST,另类算法,任意构造一棵原图的生成树，然后不断的添边，并删除新生成的环上的最大边。,10,1,7,2,5,3,算法证明,?,10/11/2024,4,浙江省2006年集训讲义,水管局长,(1),给定一张带权无向连通图，定义,max(p,),为路径,p,上的最大边，,min(u,v,),为连接,u,和,v,的所有路径中，,max(p,),的最小值。动态的做如下两个操作：,1,：询问某两个点之间的,min(u,v,),2,：删除一条边,你的任务是对于每个询问，输出,min(u,v,),的值。,(WC2006),10/11/2024,5,浙江省2006年集训讲义,水管局长,(2),数据范围约定,结点个数,N1000,图中的边数,M100000,询问次数,Q100000,删边次数,D5000,10/11/2024,6,浙江省2006年集训讲义,水管局长,(3),根据,kruskal,算法可以知道，最小生成树上的连接两点之间的唯一路径一定是最大边最小的,那么，只要维护一棵图的最小生成树，那么就可以在,O(N),的时间内回答每一个,min(u,v,),的询问,不断的删边然后维护最小生成树？,10/11/2024,7,浙江省2006年集训讲义,水管局长,(4),通过删边的形式我们似乎很难维护一张图的最小生成树,根据刚才提到的,MST,的另类做法，我们反向处理它的每个操作，也就是先删除所有要删的边，然后再逆向添边并回答,min(u,v,),于是该问题就可以用另类,MST,算法解决了,10/11/2024,8,浙江省2006年集训讲义,水管局长,(5),这里涉及到一些图与树的存储操作，如何在,O(N),的时间内找到环上最大边，并维护一棵最小生成树呢？,如果采取邻接表的存储方式来记录一棵最小生成树，从添加的边的某个点开始遍历整棵树，寻找出环上的最大边，虽然理论复杂度是,O(N),的，但是有很多的冗余,10/11/2024,9,浙江省2006年集训讲义,水管局长,(6),这里我们采取父亲表示法来存储一棵最小生成树，如图所示：,现在添加入一条红色的边,AB,我们根据被删边所在的位置来决定,AB,的定向,如果被删边在,B,到,LCA(A,B)A,和,B,的最近公共祖先,的那条路径上，则定义,AB,的方向为,B-A,，即,A,是,B,的父亲，并将被删边到,B,的这条路径上的所有边反向,(,同理可得被删边在,A,到,LCA(A,B),的那条路径上的情况,),A,B,10/11/2024,10,浙江省2006年集训讲义,小,H,的聚会,(1),给定每个节点的度限制，求在满足所有度限制的条件下的最大生成树。,(NOI2005),这是一道提交答案式的题目，对于后面的几个较大的数据，用另类,MST,算法对你的解进行调整也能取得不错的效果！,10/11/2024,11,浙江省2006年集训讲义,最小环问题,虽然涉及到要求最小环的题目并不多,(Ural1004 Sightseeing trip),，但是下面介绍的一些求最小环的算法也会对你有一定的启示意义,有向带权图的最小环问题,(,直接用,floyd,算法可解,),无向带权图的最小环问题,10/11/2024,12,浙江省2006年集训讲义,朴素算法,令,e(u,v,),表示,u,和,v,之间的连边，再令,min(u,v,),表示，删除,u,和,v,之间的连边之后，,u,和,v,之间的最短路,最小环则是,min(u,v,)+,e(u,v,),时间复杂度是,EV,2,10/11/2024,13,浙江省2006年集训讲义,一个错误的算法,预处理出任意两点之间的最短路径，记作,min(u,v,),枚举三个点,w,u,v,，最小环则是,min(u,w,)+,min(w,v,)+,e(u,v,),的最小值,如果考虑,min(u,w,),包含边,u-v,的情况？,讨论：是否有解决的方法？,10/11/2024,14,浙江省2006年集训讲义,改进算法,在,floyd,的同时，顺便算出最小环,gij,=,i,j,之间的边长,dist:=g;,for k:=1 to n do,begin,for i:=1 to k-1 do,for j:=i+1 to k-1 do,answer:=,min(answer,distij+gik+gkj,);,for i:=1 to n do,for j:=1 to n do,distij,:=,min(distij,distik+distkj,);,end;,算法证明？,10/11/2024,15,浙江省2006年集训讲义,块及其相关知识,DFS,算法,割点,(,一般对于无向图而言,),割边,(,一般对于无向图而言,),块,(,一般对于无向图而言,),强连通子图,(,一般对于有向图而言,),10/11/2024,16,浙江省2006年集训讲义,DFS,算法,1973,年，,Hopcroft,和,Tarjan,设计了一个有效的,DFS,算法,PROCEDURE,DFS(v,);,begin,inc(sign,);,dfnv,:=sign;/,给,v,按照访问顺序的先后标号为,sign,for,寻找一个,v,的相邻节点,u,if,边,uv,没有被标记过,then,begin,标记边,uv,;,给边定向,vu,;,如果,u,被标记过,记,uv,为父子边,否则记,uv,为返祖边,if u,未被标记,then,DFS(u,);,end;,end;,10/11/2024,17,浙江省2006年集训讲义,DFS,算法,父子边用黑色标记，返祖边用红色标记,如下图，除掉返祖边之后，我们可以把它看作一棵,DFS,树,1,2,3,4,5,6,7,10/11/2024,18,浙江省2006年集训讲义,割点,G,是连通图，,v,V(G,),，,G,v,不再连通，则称,v,是,G,的割顶。,10/11/2024,19,浙江省2006年集训讲义,求割点的算法,我们通过,DFS,把无向图定向成有向图，定义每个顶的一个,lowlink,参数，,lowlinkv,表示沿,v,出发的有向轨能够到达的点,u,中，,dfnu,的值的最小值。,(,经过返祖边后则停止,),1.1,2.1,3.2,4.2,5.2,6.1,7.7,10/11/2024,20,浙江省2006年集训讲义,三个定理,定理,1,：,DFS,中，,e=,ab,是返祖边，那么要么,a,是,b,的祖先，要么,a,是,b,的后代子孙。,定理,2,：,DFS,中，,e=,uv,是父子边，且,dfnu,1,，,lowlinkvdfnu,，则,u,是割点。,定理,3,：,DFS,的根,r,是割点的充要条件是：至少有,2,条以,r,为尾,(,从,r,出发,),的父子边,证明？,证明？,证明？,10/11/2024,21,浙江省2006年集训讲义,程序代码,PROCEDURE,DFS(v,);,begin,inc(sign,);,dfnv,:=sign;/,给,v,按照访问顺序的先后标号为,sign,lowlinkv,:=sign;/,给,lowlinkv,赋初始值,for,寻找一个,v,的相邻节点,u,if,边,uv,没有被标记过,then,begin,标记边,uv,;,给边定向,vu,;,if u,未被标记过,then,begin,DFS(u,);/,uv,是父子边，递归访问,lowlinkv,:=,min(lowlinkv,lowlinku,);,if,lowlinku,=,dfnv,then v,是割点,end,else,lowlinkv,:=,min(lowlinkv,dfnu,);/,uv,是返祖边,end;,end;,10/11/2024,22,浙江省2006年集训讲义,割边,G,是连通图，,e,E(G,),，,G,e,不再连通，则称,e,是,G,的割边，亦称做桥。,10/11/2024,23,浙江省2006年集训讲义,求割边的算法,与割点类似的，我们定义,lowlink,和,dfn,。父子边,e=,uv,，当且仅当,lowlinkv,dfnu,的时候，,e,是割边。,我们可以根据割点算法的证明类似的证明割边算法的正确性。,10/11/2024,24,浙江省2006年集训讲义,程序代码,PROCEDURE,DFS(v,);,begin,inc(sign,);,dfnv,:=sign;/,给,v,按照访问顺序的先后标号为,sign,lowlinkv,:=sign;/,给,lowlinkv,赋初始值,for,寻找一个,v,的相邻节点,u,if,边,uv,没有被标记过,then,begin,标记边,uv,;,给边定向,vu,;,if u,未被标记过,then,begin,DFS(u,);/,uv,是父子边，递归访问,lowlinkv,:=,min(lowlinkv,lowlinku,);,if,lowlinku,dfnv,then vu,是割边,end,else,lowlinkv,:=,min(lowlinkv,dfnu,);/,uv,是返祖边,end;,end;,10/11/2024,25,浙江省2006年集训讲义,割点与割边,猜想：两个割点之间的边是否是割边,?,割边的两个端点是否是割点？,都错！,10/11/2024,26,浙江省2006年集训讲义,嗅探器,(1),在无向图中寻找出所有的满足下面条件的点：割掉这个点之后，能够使得一开始给定的两个点,a,和,b,不连通，割掉的点不能是,a,或者,b,。,(ZJOI2004),a,b,10/11/2024,27,浙江省2006年集训讲义,嗅探器,(2),数据范围约定,结点个数,N100,边数,MN*(N-1)/2,10/11/2024,28,浙江省2006年集训讲义,嗅探器,(3),朴素算法：,枚举每个点，删除它，然后判断,a,和,b,是否连通，时间复杂度,O(NM),如果数据范围扩大，该算法就失败了！,10/11/2024,29,浙江省2006年集训讲义,嗅探器,(4),题目要求的点一定是图中的割点，但是图中的割点不一定题目要求的点。如上图中的蓝色点，它虽然是图中的割点，但是割掉它之后却不能使,a,和,b,不连通,由于,a,点肯定不是我们所求的点，所以可以以,a,为根开始,DFS,遍历整张图。,对于生成的,DFS,树，如果点,v,是割点，如果以他为根的子树中存在点,b,，那么该点是问题所求的点。,10/11/2024,30,浙江省2006年集训讲义,嗅探器,(5),时间复杂度是,O(M),的,如图，蓝色的点表示问题的答案，黄色的点虽然是图的割点，但却不是问题要求的答案,a,b,10/11/2024,31,浙江省2006年集训讲义,关键网线,(1),无向连通图中，某些点具有,A,属性，某些点具有,B,属性。请问哪些边割掉之后能够使得某个连通区域内没有,A,属性的点或者没有,B,属性的点。,(CEOI2005),数据范围约定,结点个数,N100000,边数,M1000000,10/11/2024,32,浙江省2006年集训讲义,关键网线,(2),朴素算法：,枚举每条边，删除它，然后判断是否有独立出来的连通区域内没有,A,属性或者没有,B,属性。复杂度,O(M,2,),当然，这个复杂度太大了！,10/11/2024,33,浙江省2006年集训讲义,关键网线,(3),正如嗅探器一样，题目要求的边一定是原图中的割边，但是原图中的割边却不一定是题目中要求的边。,设,A,种属性总共有,SUMA,个，,B