「图论相关」双连通、桥与割点

发表于 更新于 分类于
「施工中...」边双连通与点双连通的相关内容

本文仍有一些 typo 和错误，以及部分需要补充的东西。

#1.0 边双连通

#1.1 定义

给定简单无向图 \(G=(V,E)\)，对于 \(u,v\in V\)，如果 \(u\) 到 \(v\) 之间有两条边不相交的路径，那么称 \(u\) 和 \(v\) 边双连通，另一个等价的定义是如果删除图中的任意一条边，\(u\) 和 \(v\) 依旧连通，那么 \(u\) 和 \(v\) 边双连通。

如果 \(\forall u,v\in V\)，\(u,v\) 边双连通，那么图 \(G(V,E)\) 边双连通。

如果删除一条边后图的连通性改变，那么这条边是桥。

#1.2 性质

  1. 边双连通是等价关系，即

    • \(u\) 和 \(u\) 本身边双连通；
    • 若 \(u\) 和 \(v\) 边双连通，那么 \(v\) 和 \(u\) 边双连通；
    • 若 \(u,v\) 边双连通且 \(v,w\) 边双连通，那么 \(u,w\) 边双连通；

前两点很显然，下面只证明第三点：

容易知道，\(u,v\) 之间有两条边不相交的路径，等价与两者之间的最小割 \(C(u,v)\geq2\)，于是有 \[ C(u,w)\geq\min\{C(u,v),C(v,w)\}\geq2 \] 于是得证。

  1. 将边双连通图的每一条边定向，可以得到一张强连通图。

考虑如何构造。我们直接 DFS，将每条边定向为它第一次被访问时的方向，由于 DFS 树上的每一条非树边都是后向边，于是显然得到的图是强连通图。

#1.3 如何求得

类似上面的第二条性质，我们同样可以对于边双连通分量定向成为强连通分量，然后直接在定向后的图上 Tarjan 求强连通分量即可，注意到 Tarjan 的过程本身就是 DFS，于是不需要单独定向，直接在原图上 Tarjan 即可，只需注意本身记录的是双向边，不应当再次反向经过刚进入的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void tarjan(int x, int frm) {
    dfn[x] = low[x] = ++ T;
    stk[++ stp] = x, instk[x] = 1;
    for (int i = ghead[x]; i; i = ge[i].nxt) {
        if (i == (frm ^ 1)) continue;
        if (!dfn[ge[i].v]) {
            tarjan(ge[i].v, i);
            low[x] = min(low[x], low[ge[i].v]);
        } else if (instk[ge[i].v])
          low[x] = min(low[x], dfn[ge[i].v]);
    }
    if (low[x] == dfn[x]) {
        int y; ++ scnt;
        do {
            y = stk[stp --];
            bel[y] = scnt;
            instk[y] = 0;
        } while (y != x);
    }
}

#2.0 点双连通

#2.1 定义

给定简单无向图 \(G=(V,E)\)，这里假设 \(|V|\geq2\)，对于 \(u,v\in V\)，如果 \(u\) 到 \(v\) 之间有两条点不相交的路径，那么称 \(u\) 和 \(v\) 边双连通，另一个等价的定义是如果删除图中除 \(u\) 和 \(v\) 的任意一个点，\(u\) 和 \(v\) 依旧连通，那么 \(u\) 和 \(v\) 边双连通。

如果 \(\forall u,v\in V\)，\(u,v\) 点双连通，那么图 \(G(V,E)\) 点双连通。

如果删除一个点后图的连通性改变，那么这个点是割点。

#2.2 性质

  1. 点双连通是等价关系么？不是。

考虑 \(1\leftrightarrow2\leftrightarrow3\) 这样一个图，容易看出 \(1\) 和 \(2\) 点双连通，\(2\) 和 \(3\) 点双连通，但是 \(1\) 与 \(3\) 并不是点双连通。

  1. 注意到最简单的点双连通分量是环，考虑如果两个环有边相交，那么显然这两个环应当在同一个点双连通分量，于是有每条边恰好属于一个边双连通分量。

#2.3 构建

现在我们考虑如何求出一个图中的所有点双连通分量，这里直接采用构建圆方树来处理点双连通分量。

在圆方树上，我们令一个圆点表示原图上一个点，一个方点表示一个点双连通分量，方点与所有在这个点双连通分量中的圆点相连，一个圆点可能与多个方点相连，显然在圆方树上不会存在两个相邻的圆点或方点。

具体的构造方式与 Tarjan 求强连通分量类似，具体见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct Edge {int u, v, nxt;} ge[N], te[N];

int gecnt(1), tecnt(1), ghead[N], thead[N], T, n, bcnt;

inline void add_edge_t(int u, int v) {
    te[tecnt].u = u, te[tecnt].v = v;
    te[tecnt].nxt = thead[u], thead[u] = tecnt ++;
}

void biconnect(int x) {
    dfn[x] = low[x] = ++ T; stk[++ stp] = x;
    for (int i = ghead[x]; i; i = ge[i].nxt)
      if (!dfn[ge[i].v]) { /*未访问过*/
          biconnect(ge[i].v);
          low[x] = Min(low[x], low[ge[i].v]);
          /*找到了一个边双连通分量*/
          if (low[ge[i].v] == dfn[x]) {
              int y; ++ bcnt;
              do {
                  y = stk[stp --];
                  bel[y] = bcnt;
                  add_edge_t(bcnt, y);
                  s[bcnt].insert(w[y]);
              } while (y != ge[i].v);
              add_edge_t(x, bcnt);
          }
      } else low[x] = Min(low[x], dfn[ge[i].v]);
      /*这里必须是 dfn[ge[i].v]，因为一定在栈里，*/
      /*low[ge[i].v] 有可能在其他边双连通分量中更新*/
}

/*连通图只需要从一点开始，我们令圆点为原编号，方点为 n+1 以上编号*/
void build_tree() {bcnt = n; biconnect(1);}