图论的割顶、桥和强连通分量

图论中的割顶、桥和强连通分量2020/2/262基本概念割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。割边(桥)：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。块强连通子图(强连通分量(支,块))2020/2/263块及其相关知识DFS算法割点(一般对于无向图而言)割边(一般对于无向图而言)块(一般对于无向图而言)强连通子图(一般对于有向图而言)2020/2/264DFS算法PROCEDUREDFS(v);begininc(sign);dfn[v]:=sign;//给v按照访问顺序的先后标号为signfor寻找一个v的相邻节点uif边uv没有被标记过thenbegin标记边uv;给边定向v→u;如果u被标记过,uv为返祖边,否则记uv为父子边ifu未被标记thenDFS(u);end;end;2020/2/265DFS算法父子边用黑色标记，返祖边用红色标记如下图，除掉返祖边之后，我们可以把它看作一棵DFS树12345672020/2/266割点G是连通图，v∈V(G)，G–v不再连通，则称v是G的割顶。2020/2/267具体数据定义借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。low[i]=min(low[i],dfn[son[i]])2020/2/268求割点的算法下图所示，每个点左边是dfn值，右边是low值。(经过返祖边后则停止)1.12.13.24.25.26.17.72020/2/269三个定理定理1：DFS中，e=ab是返祖边，那么要么a是b的祖先，要么a是b的后代子孙。定理2：DFS中，e=uv是父子边，且dfn[u]1，low[v]≥dfn[u]，则u是割点。定理3：DFS的根r是割点的充要条件是：至少有2条以r为尾(从r出发)的父子边证明？证明？证明？2020/2/2610具体证明设v,u之间有边w(v,u)，从v-u：如果low[u]=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。2020/2/2611程序代码PROCEDUREDFS(v);begininc(sign);dfn[v]:=sign;//给v按照访问顺序的先后标号为signlow[v]:=sign;//给lowlink[v]赋初始值for寻找一个v的相邻节点uif边uv没有被标记过thenbegin标记边uv;给边定向v→u;ifu未被标记过thenbeginDFS(u);//uv是父子边，递归访问low[v]:=min(low[v],low[u]);iflow[u]=dfn[v]thenv是割点endelselow[v]:=min(low[v],dfn[u]);//uv是返祖边end;end;2020/2/2612割边G是连通图，e∈E(G)，G–e不再连通，则称e是G的割边，亦称做桥。2020/2/2613求割边的算法与割点类似的，我们定义low和dfn。父子边e=u→v，当且仅当low[v]dfn[u]的时候，e是割边。我们可以根据割点算法的证明类似的证明割边算法的正确性。2020/2/2614程序代码PROCEDUREDFS(v);begininc(sign);dfn[v]:=sign;//给v按照访问顺序的先后标号为signlow[v]:=sign;//给low[v]赋初始值for寻找一个v的相邻节点uif边uv没有被标记过thenbegin标记边uv;给边定向v→u;ifu未被标记过thenbeginDFS(u);//uv是父子边，递归访问low[v]:=min(low[v],low[u]);iflow[u]dfn[v]thenvu是割边endelselow[v]:=min(low[v],dfn[u]);//uv是返祖边end;end;2020/2/2615割点与割边猜想：两个割点之间的边是否是割边?割边的两个端点是否是割点？都错！2020/2/2616嗅探器(1)在无向图中寻找出所有的满足下面条件的点：割掉这个点之后，能够使得一开始给定的两个点a和b不连通，割掉的点不能是a或者b。(ZJOI2004)ab2020/2/2617嗅探器(2)数据范围约定结点个数N≤100边数M≤N*(N-1)/22020/2/2618嗅探器(3)朴素算法：枚举每个点，删除它，然后判断a和b是否连通，时间复杂度O(NM)如果数据范围扩大，该算法就失败了！2020/2/2619嗅探器(4)题目要求的点一定是图中的割点，但是图中的割点不一定题目要求的点。如上图中的蓝色点，它虽然是图中的割点，但是割掉它之后却不能使a和b不连通由于a点肯定不是我们所求的点，所以可以以a为根开始DFS遍历整张图。对于生成的DFS树，如果点v是割点，如果以他为根的子树中存在点b，那么该点是问题所求的点。2020/2/2620嗅探器(5)时间复杂度是O(M)的如图，蓝色的点表示问题的答案，黄色的点虽然是图的割点，但却不是问题要求的答案ab2020/2/2621关键网线(1)无向连通图中，某些点具有A属性，某些点具有B属性。请问哪些边割掉之后能够使得某个连通区域内没有A属性的点或者没有B属性的点。(CEOI2005)数据范围约定结点个数N≤100000边数M≤10000002020/2/2622关键网线(2)朴素算法：枚举每条边，删除它，然后判断是否有独立出来的连通区域内没有A属性或者没有B属性。复杂度O(M2)当然，这个复杂度太大了！2020/2/2623关键网线(3)正如嗅探器一样，题目要求的边一定是原图中的割边，但是原图中的割边却不一定是题目中要求的边。设A种属性总共有SUMA个，B中属性总共有SUMB个。和嗅探器类似的，如果边e=u→v是割边，且以v为根的子树中，A种属性的数目为0或者为SUMA，或者B种属性的数目为0或者为SUMB，那么e就是题目要求的边。2020/2/2624关键网线(4)下图中，蓝色的边表示题目要求的边，黄色的边表示虽然是图中的割边，但不是题目要求的边。ABAAAAAAABB2020/2/2625块没有割点的图叫2-连通图，亦称做块，G中成块的极大子图叫做G的块。把每个块收缩成一个点，就得到一棵树，它的边就是桥。2020/2/2626求块的算法在求割点的算法中，当结点u的所有邻边都被访问过之后，如果lowlink[u]=dfn[u]，我们把u下方的整块和u导出作为图中的一个块。这里需要用一个栈来表示哪些元素是u代表的块。2020/2/2627程序代码PROCEDUREDFS(v);begininc(sign);dfn[v]:=sign;//给v按照访问顺序的先后标号为signlowlink[v]:=sign;//给lowlink[v]赋初始值inc(tot);stack[tot]:=v;//v点进栈for寻找一个v的相邻节点uif边uv没有被标记过thenbegin标记边uv;给边定向v→u;ifu未被标记过thenbeginDFS(u);//uv是父子边，递归访问2020/2/2628程序代码lowlink[v]:=min(lowlink[v],lowlink[u]);endelselowlink[v]:=min(lowlink[v],dfn[u]);//uv是返祖边end;iflowlink[v]=dfn[v]thenbegin块数目number+1;repeat标记stack[tot]这个点为number;dec(tot);//点出栈untilstack[tot+1]=v;end;end;2020/2/2629新修公路(1)给出一张简单无向图，问最少添加几条边能够使得原图中没有割边。(CEOI2000)数据范围约定结点个数N≤2500边数M≤200002020/2/2630新修公路(2)为了简化数据关系，我们先将原图收缩，变成一棵树，容易知道的是，剩下的任务就是添最少的边，使得树成为一个块。(树中的两个结点之间连边相当于原图中两个块中分别任意取点连在一起)猜想：每添一条边，就选择树中的两个叶子结点，将它们连起来，于是最少的添边数目就是(叶子结点个数+1)/22020/2/2631新修公路(3)如图所示，点代表了原图中的一个块，它们之间的连边是割边。连接a与c，b与d之后，图中就没有割边了。abcd2020/2/2632新修公路(4)但并不是任意连接两个叶子结点就可以达到目标。假如连接了a与b，c与d，原图并没有变成一个块。abcd2020/2/2633新修公路(5)进一步分析刚才的算法，每次连接两个叶子结点之后，把新生成的圈压缩成为一个点，以前和圈上的点关联的点，都和新生成的这个“压缩点”相关联。于是原来的树在添加一条边之后，又变回了一棵树。2020/2/2634新修公路(6)在连接a与c之后，新生成的树只剩下2个叶子结点；连接b与d之后，树就被压缩成了一个点。abcdbd2020/2/2635新修公路(7)而如果先连接a与b，那么新生成的树会剩下3个叶子结点，连接c与d之后，树中还剩2个叶子结点，所以这种连接方法还需要多连一条边。现在的问题是，是否一定能找出这样子的两个叶子结点，使得压缩成的点不会成为新的叶子节点呢？2020/2/2636新修公路(8)连接的两个点的那条树中的唯一路径上，如果除了它们的最近公共祖先到自己的父亲有连边以外，其他的结点没有别的分叉，那么连接这两个点之后缩圈得到的点将会是一个叶子结点。假设图中的任意两个叶子连接之后，都会多产生一个叶子结点。当图中的叶子结点是2个或者3个的时候，怎么连都没有区别。2020/2/2637新修公路(9)当图中的叶子结点有4个的时候，a和b到它们的最近公共祖先都没有别的分叉，且c和d到它们的最近公共祖先没有别的分叉，可以知道，a和c到它们的最近公共祖先上一定有分叉。这个与假设矛盾。所以我们总能找到两个叶子结点，使得它们连边之后缩成的树不会新产生叶子结点。2020/2/2638新修公路(10)具体实现：首先一个问题是会碰到图的压缩，一个简单易行的方法是，新建一棵树来表示压缩过之后的图。接着还会碰到一个缩圈的问题，怎么实现这一个环节？是否需要重新建树？可以采取标号法，当缩一个圈的时候，在圈上取一个代表点，并把其他的点都标记为该代表点。一个潜在的问题是，压缩成的点可能还会被再次压缩，那么标记的时候就比较麻烦了。所以这里可以用并查集来实现标号这一步。2020/2/2639新修公路(11)算法流程：(1)求出图中的所有块，建立一棵代表树(2)挑出2个叶子结点，使得连接他们之间的唯一路径上的分叉数目最多(3)连接这两个叶子结点，并压缩新生成的圈，得到一棵新的树(4)如果树中剩下一个叶子结点和一个根结点，直接连接它们，算法结束；如果树已经成为一个点，算法结束，否则转(2)2020/2/2640有向图的DFS有向图的DFS与无向图的DFS的区别在于搜索只能顺边的方向进行，所以有向图的DFS不止一个根，因为从某个结点开始不一定就能走完所有的点。另外，有向图的DFS除了产生父子边和返祖边以外，还会有横叉边。我们这样定义它：u和v在已形成的DFS森林中没有直系上下关系，并且有dfn[v]dfn[u]，则称e=uv是横叉边。注意，没有dfn[v]dfn[u]这种横叉边。2020/2/2641连通与强连通图定义：将所有有向边改为无向边，如果该无向图是连通的，那么原有向图也称之为连通图。对于图中的任意两个