《图论中的圈与块,无向图的最小环》由会员分享，可在线阅读，更多相关《图论中的圈与块,无向图的最小环（80页珍藏版）》请在金锄头文库上搜索。
1、图论中的圈与块图论中的圈与块绍兴县柯桥中学 黄劲松2018/7/161浙江省2006年集训讲义基本概念w圈(环)w割点 w割边(桥)w块 w强连通子图(强连通分量(支,块)Date2浙江省2006年集训讲义圈及其相关知识wMST(最小生成树)另类算法w最小环问题Date3浙江省2006年集训讲义MST另类算法w任意构造一棵原图的生成树，然后不断的添 边，并删除新生成的环上的最大边。1017253算法证明?Date4浙江省2006年集训讲义水管局长(1)w给定一张带权无向连通图，定义max(p)为路 径p上的最大边，min(u,v)为连接u和v的所有 路径中，max(p)的最小值。动态的做如下两
2、 个操作：1：询问某两个点之间的min(u,v)2：删除一条边w你的任务是对于每个询问，输出min(u,v)的值 。(WC2006)Date5浙江省2006年集训讲义水管局长(2)w数据范围约定结点个数N1000图中的边数M100000询问次数Q100000删边次数D5000Date6浙江省2006年集训讲义水管局长(3)w根据kruskal算法可以知道，最小生成树上的 连接两点之间的唯一路径一定是最大边最小 的w那么，只要维护一棵图的最小生成树，那么 就可以在O(N)的时间内回答每一个min(u,v) 的询问w不断的删边然后维护最小生成树？Date7浙江省2006年集训讲义水管局长(4)w通
3、过删边的形式我们似乎很难维护一张图的 最小生成树 w根据刚才提到的MST的另类做法，我们反向 处理它的每个操作，也就是先删除所有要删 的边，然后再逆向添边并回答min(u,v)w于是该问题就可以用另类MST算法解决了Date8浙江省2006年集训讲义水管局长(5)w这里涉及到一些图与树的存储操作，如何在 O(N)的时间内找到环上最大边，并维护一棵 最小生成树呢？w如果采取邻接表的存储方式来记录一棵最小 生成树，从添加的边的某个点开始遍历整棵 树，寻找出环上的最大边，虽然理论复杂度 是O(N)的，但是有很多的冗余Date9浙江省2006年集训讲义水管局长(6)w这里我们采取父亲表示法来存储一棵最
4、小生 成树，如图所示：现在添加入一条红色的边AB我们根据被删边所在的位置来决 定AB的定向如果被删边在B到LCA(A,B)A和 B的最近公共祖先的那条路径上 ，则定义AB的方向为B-A，即A 是B的父亲，并将被删边到B的这 条路径上的所有边反向(同理可得 被删边在A到LCA(A,B)的那条路 径上的情况)ABDate10浙江省2006年集训讲义小H的聚会(1)w给定每个节点的度限制，求在满足所有度限 制的条件下的最大生成树。(NOI2005)w这是一道提交答案式的题目，对于后面的几 个较大的数据，用另类MST算法对你的解进 行调整也能取得不错的效果！Date11浙江省2006年集训讲义最小环问
5、题w虽然涉及到要求最小环的题目并不多 (Ural1004 Sightseeing trip)，但是下面介绍 的一些求最小环的算法也会对你有一定的启 示意义有向带权图的最小环问题(直接用floyd算法可解)无向带权图的最小环问题Date12浙江省2006年集训讲义朴素算法w令e(u,v)表示u和v之间的连边，再令min(u,v) 表示，删除u和v之间的连边之后，u和v之间 的最短路 w最小环则是min(u,v) + e(u,v)w时间复杂度是EV2Date13浙江省2006年集训讲义一个错误的算法w预处理出任意两点之间的最短路径，记作 min(u,v)w枚举三个点w,u,v，最小环则是min(u
6、,w) + min(w,v) + e(u,v)的最小值w如果考虑min(u,w)包含边u-v的情况？w讨论：是否有解决的方法？Date14浙江省2006年集训讲义改进算法w在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;算法证明
7、？Date15浙江省2006年集训讲义块及其相关知识wDFS算法w割点 (一般对于无向图而言)w割边 (一般对于无向图而言)w块(一般对于无向图而言)w强连通子图(一般对于有向图而言)Date16浙江省2006年集训讲义DFS算法w1973年，Hopcroft和Tarjan设计了一个有效的DFS算法 wPROCEDURE DFS(v); wbegin winc(sign); wdfnv := sign; /给v按照访问顺序的先后标号为sign wfor 寻找一个v的相邻节点u wif 边uv没有被标记过 then wbegin w 标记边uv; w给边定向vu; w 如果u被标记过,记uv为父
8、子边,否则记uv为返祖边 wif u未被标记 then DFS(u); wend; wend;Date17浙江省2006年集训讲义DFS算法w父子边用黑色标记，返祖边用红色标记w如下图，除掉返祖边之后，我们可以把它看 作一棵DFS树1234567Date18浙江省2006年集训讲义割点wG是连通图，vV(G)，G v 不再连通，则称 v是G的割顶。Date19浙江省2006年集训讲义求割点的算法w我们通过DFS把无向图定向成有向图，定义 每个顶的一个lowlink参数，lowlinkv表示沿v 出发的有向轨能够到达的点u中，dfnu的值 的最小值。(经过返祖边后则停止)1.12.13.24.2
9、5.26.17.7Date20浙江省2006年集训讲义三个定理w定理1：DFS中，e=ab是返祖边，那么要么a 是b的祖先，要么a是b的后代子孙。w定理2：DFS中，e=uv是父子边，且dfnu1 ，lowlinkvdfnu，则u是割点。w定理3：DFS的根r是割点的充要条件是：至 少有2条以r为尾(从r出发)的父子边证明？证明？证明？Date21浙江省2006年集训讲义程序代码wPROCEDURE DFS(v); wbegin winc(sign); dfnv := sign; /给v按照访问顺序的先后标号为sign wlowlinkv := sign; /给lowlinkv赋初始值 wfo
10、r 寻找一个v的相邻节点u wif 边uv没有被标记过 then wbegin w标记边uv; w给边定向vu; wif u未被标记过 then wbegin wDFS(u); /uv是父子边，递归访问 wlowlinkv := min(lowlinkv,lowlinku); wif lowlinku = dfnv then v是割点 wend welselowlinkv := min(lowlinkv,dfnu); /uv是返祖边 end; wend;Date22浙江省2006年集训讲义割边wG是连通图，eE(G)，G e 不再连通，则称 e是G的割边，亦称做桥。 Date23浙江省2006
11、年集训讲义求割边的算法w与割点类似的，我们定义lowlink和dfn。父子 边e=uv ，当且仅当lowlinkv dfnu的时 候，e是割边。w我们可以根据割点算法的证明类似的证明割 边算法的正确性。Date24浙江省2006年集训讲义程序代码wPROCEDURE DFS(v); wbegin winc(sign); dfnv := sign; /给v按照访问顺序的先后标号为sign wlowlinkv := sign; /给lowlinkv赋初始值 wfor 寻找一个v的相邻节点u wif 边uv没有被标记过 then wbegin w标记边uv; w给边定向vu; wif u未被标记过
12、then wbegin wDFS(u); /uv是父子边，递归访问 wlowlinkv := min(lowlinkv,lowlinku); wif lowlinku dfnv then vu是割边 wend welselowlinkv := min(lowlinkv,dfnu); /uv是返祖边 wend; wend;Date25浙江省2006年集训讲义割点与割边w猜想：两个割点之间的边是否是割边?割边的 两个端点是否是割点？w都错！Date26浙江省2006年集训讲义嗅探器(1)w在无向图中寻找出所有的满足下面条件的点 ：割掉这个点之后，能够使得一开始给定的 两个点a和b不连通，割掉的点不
13、能是a或者b 。(ZJOI2004)abDate27浙江省2006年集训讲义嗅探器(2)w数据范围约定结点个数N100边数MN*(N-1)/2Date28浙江省2006年集训讲义嗅探器(3)w朴素算法： w枚举每个点，删除它，然后判断a和b是否连 通，时间复杂度O(NM)w如果数据范围扩大，该算法就失败了！Date29浙江省2006年集训讲义嗅探器(4)w题目要求的点一定是图中的割点，但是图中 的割点不一定题目要求的点。如上图中的蓝 色点，它虽然是图中的割点，但是割掉它之 后却不能使a和b不连通 w由于a点肯定不是我们所求的点，所以可以以 a为根开始DFS遍历整张图。 w对于生成的DFS树，如
14、果点v是割点，如果以 他为根的子树中存在点b，那么该点是问题所 求的点。Date30浙江省2006年集训讲义嗅探器(5)w时间复杂度是O(M)的w如图，蓝色的点表示问题的答案，黄色的点 虽然是图的割点，但却不是问题要求的答案abDate31浙江省2006年集训讲义关键网线(1)w无向连通图中，某些点具有A属性，某些点具 有B属性。请问哪些边割掉之后能够使得某个 连通区域内没有A属性的点或者没有B属性的 点。(CEOI2005)w数据范围约定结点个数N100000边数M1000000Date32浙江省2006年集训讲义关键网线(2)w朴素算法：w枚举每条边，删除它，然后判断是否有独立 出来的连通
15、区域内没有A属性或者没有B属性 。复杂度O(M2)w当然，这个复杂度太大了！Date33浙江省2006年集训讲义关键网线(3)w正如嗅探器一样，题目要求的边一定是原图 中的割边，但是原图中的割边却不一定是题 目中要求的边。 w设A种属性总共有SUMA个，B中属性总共有 SUMB个。和嗅探器类似的，如果边e=uv 是割边，且以v为根的子树中，A种属性的数 目为0或者为SUMA，或者B种属性的数目为0 或者为SUMB，那么e就是题目要求的边。Date34浙江省2006年集训讲义关键网线(4)w下图中，蓝色的边表示题目要求的边，黄色 的边表示虽然是图中的割边，但不是题目要 求的边。ABAAAAAAABBDate35浙江省2006年集训讲义块w没有割点的图叫2-连通图，亦称做块，G中成 块的极大子图叫做G的块。把每个块收缩成 一个点，就得到一棵树，它的边就是桥。Date36浙江省2006年集训讲义求块的算法w在求割点的算法中，当结点u的所有邻边都被 访问过之后，如果lowlinku=dfnu，我们把 u下方的整块和u导出作为图中的一个块。w这里需要用一个栈来表示哪些元素是u代表的 块。Date37浙江省2006年集训讲义程序代码wPROCED
