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

《图论的割顶、桥和强连通分量.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论中的割顶、桥和强连通分量基本概念割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。割边(桥)：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。块强连通子图(强连通分量(支,块))2021/7/292块及其相关知识DFS算法割点(一般对于无向图而言)割边(一般对于无向图而言)块(一般对于无向图而言)强连通子图(一般对于有向图而言)2021/7/293DFS算法PROCEDUREDFS(v);begininc(sign);dfn[v]:=sign;//给v按照访问顺序的

2、先后标号为signfor寻找一个v的相邻节点uif边uv没有被标记过thenbegin标记边uv;给边定向v→u;如果u被标记过,uv为返祖边,否则记uv为父子边ifu未被标记thenDFS(u);end;end;2021/7/294DFS算法父子边用黑色标记，返祖边用红色标记如下图，除掉返祖边之后，我们可以把它看作一棵DFS树12345672021/7/295割点G是连通图，v∈V(G)，G–v不再连通，则称v是G的割顶。2021/7/296具体数据定义借助两个辅助数组dfn[],low[]进行DFS便可

3、找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通过其他边回到其祖先的最早时间。low[i]=min(low[i],dfn[son[i]])2021/7/297求割点的算法下图所示，每个点左边是dfn值，右边是low值。(经过返祖边后则停止)1.12.13.24.25.26.17.72021/7/298三个定理定理1：DFS中，e=ab是返祖边，那么要么a是b的祖先，要么a是b的后代子孙。定理2：DFS中，e=u

4、v是父子边，且dfn[u]>1，low[v]≥dfn[u]，则u是割点。定理3：DFS的根r是割点的充要条件是：至少有2条以r为尾(从r出发)的父子边证明？证明？证明？2021/7/299具体证明设v,u之间有边w(v,u)，从v->u：如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。2021/7/2910程序代码PROCEDUREDFS(v);begininc(sign);

5、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;2021/7/

6、2911割边G是连通图，e∈E(G)，G–e不再连通，则称e是G的割边，亦称做桥。2021/7/2912求割边的算法与割点类似的，我们定义low和dfn。父子边e=u→v，当且仅当low[v]>dfn[u]的时候，e是割边。我们可以根据割点算法的证明类似的证明割边算法的正确性。2021/7/2913程序代码PROCEDUREDFS(v);begininc(sign);dfn[v]:=sign;//给v按照访问顺序的先后标号为signlow[v]:=sign;//给low[v]赋初始值for寻找一个v的相邻节

7、点uif边uv没有被标记过thenbegin标记边uv;给边定向v→u;ifu未被标记过thenbeginDFS(u);//uv是父子边，递归访问low[v]:=min(low[v],low[u]);iflow[u]>dfn[v]thenvu是割边endelselow[v]:=min(low[v],dfn[u]);//uv是返祖边end;end;2021/7/2914割点与割边猜想：两个割点之间的边是否是割边?割边的两个端点是否是割点？都错！2021/7/2915嗅探器(1)在无向图中寻找出所有的满足下面条

8、件的点：割掉这个点之后，能够使得一开始给定的两个点a和b不连通，割掉的点不能是a或者b。(ZJOI2004)ab2021/7/2916嗅探器(2)数据范围约定结点个数N≤100边数M≤N*(N-1)/22021/7/2917嗅探器(3)朴素算法：枚举每个点，删除它，然后判断a和b是否连通，时间复杂度O(NM)如果数据范围扩大，该算法就失败了！2021/7/2918嗅探器(4)题目要求的点一定是图中的割点，但是图中