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