跳转至

11. 双连通图和欧拉回路

阅读信息

约 479 个字  2 分钟  本页总访问量：加载中... 次

🎐Class Eleven

深度优先遍历

C
1
2
3
4
5
6
7
void dfs(点v) {
    for (与v相邻的点w) {
        if (w没有被访问过) {
            dfs(w);
        }
    }
}

判断连通块

C
1
2
3
4
5
6
7
8
void solve(图 g) {
    for (g中的点v) {
        if (没访问过v) {
            dfs(v);
            cnt++;
        }
    }
}

双连通图问题

双连通：任意删除节点后，图不分裂成两个 删除后图分裂的点成为 articulation（关节点），没有 articulation 的图是 biconnected。 只有两个节点，中间用一条边连接，也是双连通图。 biconnected component: a maximum biconnected subgraph. 关键是找到关节点

dfs 对图进行整理，根据 dfs 顺序形成树。起点是根结点，通过 v 找到 w，则 v 是 w 的父节点。 转化后缺少部分边，在树中补上。 这些新添加的边一定连接祖先和后裔，成为 back edge。（如果连接不同分支的边，一定通过这条边 dfs 时直接访问到。）

什么点是关节点？

  1. 至少含两个儿子的根节点
  2. 所有儿子都没有向上的回边。

同一分支上用数字表示层级，数字越小层级越大。回边将低层次与高层次的关系。 每个节点有两个数值，一个表示自己的层级 num，一个表示自己和所有儿子的最高层级 low。 当存在一个分支的 low< num，该点为关节点。

Text Only
1
2
3
low(u) = min{num(u),
             min{low(w) | w is a child of u},
             min{num(w) | (u,w) is a back edge} }

u is an articulation point iff:

  1. u is the root and has et least 2 children
  2. u is not the root, and has at least 1 child such that low(child) >= num(u)

欧拉回路问题

欧拉回路：从任意一点出发，将所有边走一遍并回到起点。 结论：所有点的度都是偶数，则一定存在欧拉回路。 所有点的度之和一定是偶数。 度为奇数的点有两个，一定能从其中一个点出发走过所有边到达另外一个点。

怎么构造解？

所有点的度都是偶数，从任意一点出发 dfs，最后一定回到起点，但不一定把所有边走完。 （每个点入和出的次数一定相等） 删除 dfs 回到起点后经过的路，剩下的所有点的度还是都为偶数。 在路径上选取还有边的点继续 dfs，直到所有边走完。

哈密尔顿回路问题（旅行商问题） 将所有点都走一遍