/ Algorithm

算法:无向图的割点、桥与双连通分量

概念

对于无向图\(G\),删除顶点\(v\)和其相连的边后\(G\)所包含的连通分量增多,则称\(v\)为关节点 (articulation point) 或割点 (cut point)。同理,删除边\(e\)和其相连的顶点后图包含的连通分量增多,则\(e\)是割边 (cut edge) 或 (bridge)。

割点形式化的定义:\(A\)是割点当且仅当存在两个点\(u,v\),使得\(u\)到\(v\)的每条路径都会经过\(A\)(去掉\(A\)后,\(u\)到\(v\)没有路径)。

不含任何割点的图称为双连通图。任一无向图都可视作若干个极大双连通子图组合而成,每一个子图称为双连通分量 (bi-connected component)。

双连通分量的定义:是极大双连通子图,即如果\(G\)是双连通分量,则不存在\(G^\prime\),使得\(G\)是\(G^\prime\)的子图且\(G^\prime\)也是双连通分量。

点双连通分量:在连通分量中去掉一个顶点,连通分量仍连通。特殊的,点双连通分量又叫做

边双连通分量:在连通分量中去掉一条边,连通分量仍连通。

等价关系 (equivalence relation):边\(e_{1}\)和\(e_{2}\)是等价关系当且仅当\(e_{1} = e_{2}\)或\(e_{1}\)与\(e_{2}\)在一个回路中。

等价类 (equivalence class):一个等价类中的两条边都是等价关系。

重要性

相对于图中其他顶点,割点更为重要。在网络系统中相当于网关,决定子网之间能否连通。在航空网络中,某些枢纽机场的损坏,可能导致与其他机场之间交通的中断。故在资源总量有限的情况下,应该找出图中的割点予以保障,这是提高系统整体稳定性和鲁棒性的基本策略。

命题与证明

命题1 两个双连通分量之间最多有一个公共点。

证明:假设双连通分量\(C_1\)、\(C_2\),且有两个公共点\(v_1\)、\(v_2\),因为双连通分量划分非桥边,所以\(v_1\)与\(v_2\)之间至少有两条边,因此假设\(v_1\)与\(v_2\)有两条边\(e_1\)和\(e_2\),如下图:

Figure 1

在这种情况下,\(e_1\)和\(e_2\)可能是路径,也可能是边,不失一般性地,我们假设\(e_1\)和\(e_2\)为边。

因为\(e_1\)在\(C_1\)中,因此\(e_1\)与\(C_1\)中任何一条边都在一个简单回路中,同理,\(e_2\)与\(C_2\)中任何一条边都在一个简单回路中。因为\(e_1\)和\(e_2\)在一个回路中,所以\(e_1\)与\(C_2\)中任何一条边都在一个简单回路中,\(e_2\)与\(C_1\)中任何一条边都在一个简单回路中。所以\(C_1\)、\(C_2\)合并。

命题2 两个双连通分量之间的一个公共点是割点。

证明:如果公共点不是割点,则将点\(A\)删除后\(C_1\)、\(C_2\)依然连通。因此必然存在\(u\)、\(v\)使得\((u, v) \in E\)。因此当\(A\)存在时,\(u\)到\(A\)存在路径,\(A\)到\(v\)存在路径,\(u\)和\(v\)间又存在一条边,则\((u, v)\)与\(C_1\)中任何一条边都存在一个简单回路,\((u, v)\)与\(C_2\)中任何一条边都存在一个简单回路,则\(C_1\)、\(C_2\)合并。

Figure 2

命题3 割点一定属于至少两个双连通分量。

证明:如果割点仅属于一个双连通分量,根据双连通分量的定义,去掉任何一个点都不会让图不连通,与割点的定义矛盾。

命题4 在一个双连通分量中至少要删除两个点才能够使图\(G\)不连通。

证明:根据双连通分量的定义易证。

命题5 对于根顶点\(u\),\(u\)为割点当且仅当\(u\)有至少两个儿子。

引理 无向图仅有树边 (tree edge) 和反向边 (back edge)。证明略。

证明:

证明充分性:已知\(G_n\)的根是割点,如果\(G_n\)中根节点\(s\)只有一个子节点\(t\),则去除了根节点后,其子节点\(t\)仍然连接着分支,这与根节点\(s\)为割点条件不符,因此根至少有两个子节点。

证明必要性:如果\(G_n\)中根有至少两个子节点,因为无向图只存在树边、反向边,没有交叉边 (cross edge),因此当根去除后,分量之间不能连接,因此根为割点。

命题6 对于非根顶点\(u\),\(u\)为割点当且仅当\(u\)只要存在一个子顶点\(s\),使得\(s\)、\(s\)的后裔(不是真后裔)没有指向\(u\)的真祖先的反向边。

证明:

证明充分性:已知\(G_n\)中某个非根节点\(v\)是割点,如果任何\(v\)的子顶点\(s\)或\(s\)的后裔指向\(v\)的真祖先的反向边,我们考虑一个分量,假设反向边为\((a, b)\),其中\(a\)为\(v\)的子顶点,\(b\)为\(v\)的真祖先。当\(v\)删除后,因为\(v\)的真祖先连通,\(v\)的子顶点之间连通,如果存在\({a, b}\)的边,则\(v\)的真祖先和\(v\)的子顶点也连通,与条件矛盾。

证明必要性:如果存在一个子顶点\(s\),不存在\(s\)或\(s\)的后裔指向\(v\)的真祖先的反向边,则\(v\)的真祖先区域和\(v\)的子顶点区域不连通,因此\(v\)为割点。

命题7 定义\(hca[u]\)为\(u\)或\(u\)的子树中能通过反向边追溯到的最高的节点。(即DFS序号\(d\)最小的节点,亦即开始搜索的时间。)对于非根顶点\(u\)为割点,当且仅当存在相邻子顶点,使得\(hca[v] \ge d[u]\)。

证明:

证明充分性:

因为\(u\)为割点,因此\(u\)有一个子顶点\(v\),不存在\(v\)或\(v\)的真后裔顶点指向\(u\)的真祖先的反向边。

因为\(hca[v] = \mathrm{min}\{d[v], d[w]\}\),其中对于\(v\)的后裔\(u\),\((u, w)\)为反向边。

因为\(d[w] \ge d[u]\),所以\(hca[v] \ge d[u]\)。

证明必要性:

因为\(hca[v] \ge d[u]\),所以\(hca[v] = \mathrm{min} \{d[v], d[w]\} \ge d[u]\),因为\(d[v] \ge d[u]\),所以\(d[w] \ge d[u]\),所以\(w\)为\(u\)的后裔。

所以不存在\(v\),使得\(v\)或\(v\)的子顶点存在指向\(u\)的真祖先的反向边,因此\(u\)为割点。

命题8 \((u, v)\)是桥,当且仅当\(hca[v] > d[u]\)。

证明:

证明充分性:已知\((u, v)\)是桥,则此边不在任何简单回路中,不失一般性,先访问\(u\)再访问\(v\),则\(hca[v] = \mathrm{min}\{d[v], d[w]\}, d[w] > d[u]\),所以\(hca[v] > d[u]\)。

证明必要性:已知\(hca[v] > d[u]\),所以\(d[w] > d[u]\),所以不存在\(v\)或\(v\)的子顶点,使得\((v, w)\)为反向边,且\(w\)是\(u\)的后裔,所以\((u, v)\)不属于简单回路,所以是桥。

命题9 双连通分量的任意两条边位于同一个简单回路等价于双连通分量中没有割点。

证明:

如果存在割点\(u\),设与\(u\)相邻的点为\(v_1, v_2, \dots , v_n\),则因为\(u\)去掉后,应该使得\(v_1 \dots v_n\)中的至少其中一个顶点和\(u\)不连通,假设此点为\(v_i\),但是根据双连通分量的定义,\((u, v_i)\)位于简单回路,因此根据定义\(u\)和\(v_i\)应该仍然连通,所以矛盾。

查找点双连通分量算法

给定无向图\(G\),如何确定割点和点双连通分量?

实际上,在求割点的过程中就能顺便把每个点双连通分量求出。

由命题5、命题6可知,对于一颗DFS搜索树中根顶点和内定点为割点的充分必要条件。其中重要的就是判断某一顶点有无子树与该顶点的真祖先通过反向边相连。那么,我们可以通过比对HCA (highest connected ancestor) 来记录可(经反向边)连接的最高祖先,然后通过比较每个顶点被搜索的开始时间\(start\_time\),判断哪个祖先越高(开始时间越小说明节点高度越高)。

以下代码在图的DFS基础上进行修改:

void BCC(int v, int &clock, stack<int> &s) {
    hca(v) = start_time(v) = ++clock;
    status(v) = DISCOVERED;  // 发现v
    s.push(v);               // 顶点v入栈,枚举其所有邻居
    for (int u = first_neighbor(v); u > -1; u = next_neighbor(v, u)) {
                             // 当u没有邻居时,next_neighbor返回-1
        switch (u) {         // 视u的情况进行处理
        case UNDISCOVERED:   // 若u未被搜索,则(v, u)为树边,从顶点u开始继续深入递归搜索
            parent(u) = v;
            type(v, u) = TREE;
            BCC(u, clock, s);
            if (hca(u) < start_time(v)) {
                             // 递归返回后,若发现u可达的祖先比v还高,则说明u可以通过反向边连接v的真祖先
                hca(v) = min(hca(v), hca(u));
                             // 对v而言亦如此
            }
            else {           // 否则,v为割点,u以下即为一个BCC,且其中顶点集中于栈s的顶部
                while (v != s.top()) {
                    s.pop(); // 依次弹出当前BCC中的节点,亦可根据实际需求转存至其他结构
                }
                s.push(v);   // 最后一个顶点(割点)重新入栈,均摊下来不足1次
            }
            break;
        case DISCOVERED:
            type(v, u) = BACKWARD;
                             // 标记(v, u),并按照“越小越高”的准则
            if (u != parent(v)) {
                hca(v) = min(hca(v), start_time(u));
                             // 更新hca(v)
            }
            break;
        default:             // 对于无向图,剩下一种情况是已经访问(VISITED)
            type(v, u) = (start_time(v) < start_time(u)) ? FORWARD : CROSS;
            break;
        }
    }
    status(v) = VISITED;     // 结束对v的访问
    return;
}

由于访问的是无向图,DFS搜索在\(v\)的子节点\(u\)返回后通过比较\(hca(u)\)和\(start\_time(v)\)的大小关系即可判断\(v\)是否割点。当\(hca(u) \ge start\_time(v)\)时,\(u\)和其后代无法通过反向边与\(v\)的真祖先联通。既然栈\(s\)存放了搜索过的顶点,则此时与该割点对应的双连通分量内的顶点应该集中在\(s\)的顶部,因此可以依次弹出它们。\(v\)作为多个联通分量的连接枢纽,在弹出以后应该重新进栈。

若\(hca(u) < start\_time(v)\),则说明\(u\)可以经过反向边连接\(v\)的真祖先,这一规则对\(v\)同样适用,则有必要将\(hca(v)\)进行更新。当然,每遇到一条反向边\((v, u)\),也需要及时的更新\(hca(v)\),以保证\(hca(v)\)始终能记录顶点\(v\)经反向边向上连通到的最高的祖先。

复杂度分析

与基本的DFS相比,此处只增加了一个规模为\(O(n)\)的辅助栈,故整体空间复杂度没有变化,仍然为\(O(n + e)\)。

对于时间复杂度,同一顶点\(v\)可能多次入栈,但是每一次重复入栈都对应于发现新的双连通分量,因此必有至少另一顶点出栈并且不再入栈,故这类重复入栈操作不会超过\(n\)次,则入栈操作不会超过\(2n\)次,故算法整体复杂度依然是\(O(n + e)\)。

参考资料

  • 参考邓俊辉著《数据结构(C++版)》(第3版)。
  • 参考这篇文章