图的连通性

Vision271 · 2022-09-07 21:26:54 · 个人记录

概述

• 不是很知道概述啥...

无向图的连通性

定义

• 连通子图：原图的连通的子图。

• 连通分量：原图的极大连通分量。没有特别声明的时候，连通块也指连通分量。

  • 即不可进一步扩展的连通分量。

  • 形式化定义即为边集 V' 使得 \forall u,v\in V'，u,v 连通，且 \nexists w\notin V' 使得 \forall u\in V',u,w 连通。

• 割点：如果将一个点及所有与之相连的边从图中删去可以使得图不再连通，那么称该点为这个连通（子）图的割点。

• 桥（割边）：如果将一条边删去可以使图不再连通，那么称该边为这个连通（子）图的桥（割边）。

• 点双连通图：没有割点的图。下文简称为点双。如果原图不连通，那么指的是点双连通分量（v-dcc）。

• 边双连通图：没有桥的图。同上（e-dcc）。

• 缩点：将所有连通分量用一个广义点 v' 代替，该连通分量内部的边略去，向外的边认为是连到了 v' 上。

割点与桥的求解：tarjan 算法

• tarjan 算法是一种基于 dfs 序的算法。具体来讲，主要有三个核心内容：

  • 搜索树。对原图跑 dfs 所得的一棵树。称树上的边为树边，余下的边为非树边。

  • 时间戳。按访问顺序对点重编的一个号，记为 dfn。

  • 回溯值。较复杂的一个值，形式化为 low_i=\min(dfn_{i},low_{sons},dfn_{to})，其中 sons 为 i 在搜索树上的儿子，to 为与 i 相连的非树边指向的点。

• 结论1：非树边一定是返祖边。即，非树边的两个端点一定为祖孙关系。

  • 使用反证法。如果不为祖孙关系，那么在将 dfn 较小的点的子树 dfs 完毕时（暂且不考虑这条边），dfn 较大的点一定还没有被遍历过。

  • 从而该边会成为一条树边，较大的点会退化为较小的点的儿子。

  • 从这一结论出发，我们可以给出 low 的另一个定义：从 i 出发，只经过至多一条返祖边，所能到达的 dfn 最小的节点的 dfn。

• 结论2：如果一条边满足 low_{son}> dfn_i，那么它是桥。

  • 非常显然。这代表着对应子树内不存在足够返祖的返祖边可以到该子树外。

• 结论3：如果 \sum (low_{son}\geqslant dfn_i)\geqslant 1，那么 i 是割点。特别地，如果 i=rt，那么式右的 1 要变成 2。

  • 证明同上，不存在边可以绕出该子树。

  • 对于根的话，其实可以看出括号内条件总是成立，所以其实等价于 e_{rt}.size()>1，即要求根不是链的一端——那就相当于叶节点。

• 结论4：如果一个图是点双，那么或者 V\leqslant 2，或者任意两点共环。

  • 首先容易证明 V\leqslant 2 的情况下，G 一定是点双。

  • 然后讨论 V>2 的情况。使用反证法，若存在两点不共环，则路径唯一，则删去路径上任意点后两点不再连通。

• 结论5：如果一个图是边双，那么任意两点共环。

  • 反证删边。

• p.s.：在无向连通图的意义下，任意两点共环和任一一条边是环上边等价。

  • 充分性：假设有一条边不在环上，但其两端点在环上，则其两端点之间必然有一条不经过该边的路径，从而构环。

  • 必要性：假设有两点不共环，由无向连通图知一定存在一条路径，又任意边为环上边，故走过的路径必为环的一部分，从而共环。

• 结论6：任意一条边要么是桥，要么属于某个边双；任意点一定属于某个边双。

  • 显然。

• 结论7：删去桥后，任意连通块为边双。

  • 双联通性：反证，否则有桥，与删去桥矛盾。

  • 极大性：进一步扩展一定遇到桥。

  • 推论：将极大的边双缩点后得到的新图一定是一棵树。

    • 反证法。如果不是一棵树说明存在环，环一定是边双，故可以进一步缩点。

• 结论8：任意边一定属于某个点双；任意点要么属于一个点双，要么是割点并且属于多个点双。

  • 略。

• 结论9：割点的每个 low_{to}\geqslant dfn_{now}，即无法越过割点和外界连通的子树中，不为其他割点子树的点成点双（包括这个割点本身）。

  • 这里的子树不含根。或者说其实想表示的就是每个方向的子树都是点双，形式化地说就是 \forall u\in subtree,\nexists v\in path(now,u) \And v \text{ is cutvertex},u\in \text{v-dcc}。

  • 即所有该子树内的，到 now 的路径上（不含 u,now）没有割点的点都在这个点双内。

  • 双连通性：所有割点都是边界节点。

  • 极大性：进一步扩展一定导致割点不是边界节点。

  • 推论：可以模仿线段树优化建图，对每个点双开一个虚点，该虚点向其内的点连边。这样构成的图一定是一棵树。

    • 显然每个点双是一个菊花图，各菊花图共了一些顶点（割点）。

    • 圆方树相关先略过。

• 边双/桥的求解：

  • 容易 tarjan 求桥并标记。

  • 从而可以从每个点出发不走桥 dfs 染色，同色点为一个边双。

  • 也可以并查集（将非桥的两个端点合并）。

  • 也可以栈。模仿强连通那边的办法，low=dfn 的点是退栈处。

• 点双/割点的求解：

  • 也许可以暴力染色，不允许走到割点但是把走到的点全部染色或者说全部丢进 vector 里？

  • 比较经典的求法是，用显式栈辅助 dfs。我们站在割点处理被割的儿子，dfs 完对应儿子后，将对应儿子到栈顶的元素丢到一个点双里并弹栈，然后把割点本身加进去。即结论 9。

  • 注意此时一定认为根是“割点”，即一定有一个以根为根的点双，理由显然。

示范代码

• 只给出 tarjan 的核心，即求 low。按需加东西。

int dfn[maxn],dfntot,low[maxn];
il void tarjan(int now,int fa){
    dfn[now]=low[now]=++dfntot;
    for(int to:e[now])
        if(!dfn[to]){
            tarjan(to,now);
            chkmin(low[now],low[to]);
        }
        else if(to!=fa) chkmin(low[now],dfn[to]);
    return;
} 

有向图的连通性

定义

• 强连通图：

  • 图上任意两点互相可达即任意两点共环的图是强连通图。

  • 形式化地，对于所有的无序点对 (u,v)，总有至少一条 u\to v 的路径。

  • 强连通分量简称为 scc。

求解：tarjan

• 算法同前。这里搜索树的情况稍有不同：非树边一定是 dfn 意义下的回退边，但不一定是返祖边（考虑 dfn 意义下较晚的子树指向较早的子树的边）。

• 结论10：dfn=low 的点是一个 scc 的起始点即最浅点，换言之，dfn=low 的点子树内不为其他 dfn=low 的点的子树的点构成一个强连通分量。

  • 首先，这样的点及其子树所有边都指向子树内。如果有指向子树前的，不应当有 dfn=low；如果有指向子树后的，对应点应当在此时就被扩展到子树内。

  • 然后，不存在一个跨越它的环，环的小端（在搜索树的 dfn 意义下）至多为它。

  • 从而这个环（也可能是单点）是一个极大环，从而是极大强连通子图即 scc。故我们可以在退出一个 dfn=low 的点时将此处到栈顶的点取出，它们构成一个强连通分量。

  • 特别地，这里更新 low 的前提是 to 还在栈里。

    • 如果对应点已经被归为某个强连通分量，则可以证明对应强连通分量与当前点所共的极大子树的根一定不在对应强连通分量中。

    • 或者说，既然对应强连通分量已经结算，则对应子树已经完全退出，只存在从当前 scc 指向这个已经结算的 scc 的边，不存在从已结算 scc 发出的边。

    • 于是走过去是“断头路”，因为没法回到当前 scc 的祖先；如果能回到，说明对应祖先在那个 scc 里，那么，那个 scc 不应当已经结算，因为这个祖先的子树还没有 dfs 完。

• 结论11：将强连通缩点后所得的新图一定是一幅 DAG。

  • 略。

  • 从此结论出发我们可以得到一种泛用的有向图 DP 方式：缩点-（点内暴力）-拓扑排序-DP。

例题

P2860 [USACO06JAN]Redundant Paths G

• 题意：给定一张图，求将它变成一个边双最少要加几条边。

• 数据范围：不知道，感觉应该可以到 5\times 10^7。

• 缩出点双树。观察可以发现，每个叶节点必须作为一条新边的端点。从而答案为 \lceil \dfrac{leafs}{2} \rceil。

POJ 3694

• 题意：对无向图加边，在线询问桥数。

• 数据范围：n\leqslant 10^5,m\leqslant 2\times 10^5,q\leqslant 10^3。

• 缩点建树，新加的边当且仅当是新图上的非树边时能减少桥，此时进一步缩点即可。复杂度...感觉上好像是 O(n)？

• 哦好像有更妙一点的解法，用区间染色并查集，链上能做树上也能做。这样更好写。

POJ 2942

• 题意：n 个骑士有 m 对矛盾关系。求不能坐进任何一个圈的骑士人数。

  • 一个圈：人数 \geqslant 1 且为奇数，相邻两者没有矛盾。

• 数据范围：n\leqslant 10^3,m 顶满。

• 感觉上手可以先求补图。转化题意后其实是问不属于任何一个奇环的骑士有多少名。

• 后面不会（这是个历史遗留问题，我有空再来处理）。

P2746 [USACO5.3] 校园网 Network of Schools

• * 1.最少把一种软件给几个学校能使所有学校都用上。 * 2.最少加几对支援关系，可以使所有学校都总能用到一个软件，无论这个软件一开始给谁。

• 嗯。首先肯定缩点。

• 然后第一问相当于入度为 0 的点数。

• 第二问有点意思，其实就是补成一个强连通。

• 考虑模仿那个边双题。先缩点，容易发现入度为 0 的点一定需要入边，出度为 0 的点一定需要出边。从而一定有下界 \max(indeg_0,outdeg_0)。

• 但这样的连法能保证整个图强连通吗？乍一看好像有点问题，可能是多个彼此孤立的强连通。

• 考虑把入度为 0 的放在左边，出度为 0 的点放在右边，从上至下依次编号，然后 0 号无出度与 1 号无入度连，以此类推。

• 其实就是构了一个极大环。

支配问题

• 求有向图上 s\to t 的必经点/边集。

  • Task1：DAG。

  • Task2：普通有向图。

• （其实我自己很难想到）模仿 A* 求 k 短路的算法，分别从 s,t 开始跑 bfs，前者跑正图后者跑反图，一个点被扩展到的次数就是走到它的方案数，分别记为 f,g。

• 从而如果有 f_x\times g_x=f_t，x 为必经点。受此启发，我们可以想到如果有 f_s\times g_e（s,e 为边的起终点），则对应边是必过点。

• Task2？那是支配树。不会。