[图](8)割点与桥

关结点和重连通图

假若删去在顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称结点v为该图的关节点(articulation point),一个没有关结点的连通图称为是重连通图(biconnected graph)

在重连通图上,任意一对顶点之间至少存在两条路径,则在删去某个顶点以及依附于该顶点的个边时也不破坏图的连通性,若在连通图上至少删去k各顶点才能破坏图的连通性,则称此图的连通图度为k

关节的和重连通在实际中有较多应用,显然,一个表示通信网络的图的连通度越高,其系统越可靠,无论是哪一站点出现故障或遭到外界破坏,都不影响系统的正常工作,又如,一个航空网若是重连通的,则当某条航线因天气等某种原因关闭时,旅客仍可从别的航线绕道而行,再如,若将大规模集成电路的关键线路设计成重连通的话,则在某些元件失效的情况下,整个片子的功能不受影响,反之,在战争中,若要摧毁敌方的运输线,仅需破坏其运输网中的关节点即可

例如,在下图中的G是连通图,但不是重连通图,图中有4个关节点A、B、D和G,若删去顶点B以及所有的依附顶点B的边,G就被分割成3个连通分量{A、C、F、L、M、J}、{G、H、I、K}和{D、E},类似的,若删去顶点A或D或G以及所有依附于它们的边则G被分割成两个连通分量,由此,关节点亦称为割点

利用深度优先搜索便可求得图中的关节点,并由此可判别图是否重连通的。

image-20210129223744761

上边右图所示从顶点A出发深度优先搜索遍历图G,所得深度优先生成树,图中实线表示树边,虚线表示回边(即不在生成树上的边),对树中任一顶点v而言,其孩子结点为在它之后搜索到的邻接点,而其双亲结点和由回边联结的祖先结点是在它之前搜索到的邻接点,由深度优先生成树可得出两类关节点的特性;

  1. 若生成树的根有两棵或两棵以上的子树,则此根顶点必为关节点,因为图中不存在联结不同子树中顶点的边,因为,若删去根顶点,生成树便变成森林,如右图中的顶点A
  2. 若生成树中某个非叶子顶点v,其某棵子树的根和子树中的其他结点均没有指向v的祖先的回边,则v为关节点,因为,若删去v,则其子树和图的其他部分被分割开来,如右图中的B、D和G。

若对图Graph=(V、{Edge})重新定义遍历时的访问函数visited,并引入一个新的函数low,则由一次深度优先搜索遍历便可求得连通图中存在的所有关节点。

定义visited[v]为深度优先搜索遍历连通图时访问顶点v的次序号,定义:

image-20210129230430244

若对于某个顶点v,存在孩子结点w,且low[w]>=visited[v],则该顶点v必为关节点,因为当w是v的孩子结点时,low[w]>=visited[v],表明w及其子孙均无指向v的祖先的回边

由定义可知,visited[v]的值即为v在深度优先生成树的前序序列中的序号,只需将DFS函数中头两个语句改为visited[v0]=++count(在DFSTraverse中设处置count=1)即可,low[v]可由后序遍历深度优先生成树求得,而v在后序序列中的次序和遍历时退出DFS函数的次序相同,由此修改深度优先搜索遍历的算法便可得到求关节点的算法。

算法如下所示:

void FindArticul(ALGraph G) {
    //连通图G以邻接表作存储结构,查找并输出G上全部关节点,全局量count对访问计数
    count = 1;
    visited[0] = 1;//设定邻接表上0号顶点为生成树的根
    for (int i = 0; i < G.vexnum; i++) visited[i] = 0;//其余顶点尚未访问
    p = G.vertices[0].firstarc;
    v = p->adjvex;
    DFSArticul(G, v);//从第v顶点出发深度优先查找关节点
    if (count < G.vexnum) {//生成树的根有至少两棵子树
        printf(0, G.vertices[0].data);//根是关节点,输出
        while (p->nextarc) {
            p = p->nextarc;
            v = p->adjvex;
            if (visited[v] == 0)
                DFSArticul(g, v);
        }//while
    }//if
}//FindArticul
void DFSArticul(ALGraph G, int v0) {
    //从第v0个顶点出发深度优先遍历图G,查找并输出关节点
    visited[v0] = min = ++count;//v0是第count个访问的顶点
    for (p = G.vertices[v0].firstarc; p; p = p->nextarc) {//对v0的每个邻接顶点检查
        w = p->adjvex;//w为v0的邻接顶点
        if (visited[w] == 0) {//w未曾访问,是v0的孩子
            DFSArticul(G, w);//返回前求得low[w]
            if (low[w] < min)min = low[w];
            if (low[w] >= visited[v0])
                printf(v0, G.vertices[v0].data);//关节点
        }
        else if (visited[w] < min) min = visited[w];
    }
    low[v0] = min;
}

例如,图G中各顶点计算所得visited和low的函数值如下所示:

i0123456789101112
G.vertices[i].dataABCDEFGHIJKLM
visited[i]15121011138694723
low[i]11151015582511
求得low值得顺序13987612352141110

其中J是第一个求得low值得顶点,由于存在回边(J,L),则low[J]=Min{visited[J]、visited[L]}=2。顺便提一句,上述算法中将指向双亲得树边也看成是回边,由于不影响关节点的判别,因此,为使算法简明起见,在算法中没有区别之

由于上述算法的过程就是一个遍历的过程,因此,求关节点的实际复杂度仍为O(n+e),若尚输出双连通分量,仅需在算法中增加一些语句即可

双连通分量

双连通分量又分点连通分量边连通分量两种,若一个无向图中的去掉任意节点(一条边)都不会改变图的连通性,即不存在割点(桥),则称作点(边)双连通图,一个无向图中的每一个极大点(边)双连通子图称作此无向图的(边)双连通分量

视频如下所示:

a

本文链接:

https://nullcode.fun/131.html
1 + 5 =
快来做第一个评论的人吧~