神秘图论

sunkuangzheng · 2025-01-19 21:16:27 · 个人记录

切边等价理论

在边双连通图里，定义两条边 e_1,e_2 是 切边等价 的，当且仅当任意一个简单环要么同时包含 e_1,e_2，要么同时不包含 e_1,e_2。

上面的条件等价于：

• 同时断开 e_1,e_2 后图不连通。
• 若 e_1,e_2 都是生成树的树边，则任意非树边要么同时跨过 e_1,e_2，要么同时不跨过。

条件一等价于断开 e_1 后 e_2 是割边，因此包含 e_2 的所有简单环都需要包含 e_1；同理包含 e_1 的所有简单环也需要包含 e_2。

可以根据条件二快速找到切边等价类：给每条非树边随一个权值，给路径上所有树边异或上这个权值。边权相等的边是一个切边等价类。特别的，边权为 0 的边是图的割边。

推论：图的极小割集的边权异或和是 0；异或和是 0 的边集是图的割集。

• P10778 BZOJ3569 DZY Loves Chinese II

根据上述推论，找输入的边集是否存在异或和为 0 的子集即可。

• P6914 [ICPC2015 WF] Tours

考虑一个大小为 t 的切边等价类。 如果有 k \mid t，那直接给每个颜色染 t/k 条边显然合法；因此，k \mid \gcd(t_i) 是一个 k 合法的充分条件。

我们猜测这就是一个 k 合法的充要条件。必要性的证明先咕一下。

边三连通分量

一个很 naive 的想法是，如果一个切边等价类的大小大于 1，就把这些边全都断开。然后剩下的每一个连通块就是一个边三。这个做法看起来很优美，但是是假的，看下图：

这个图里 3,4,5,7,8 是一个边三连通分量，但是按照上述做法会求出 4,5,7,8 和 3 两个。

上面断边想法的来源是，如果 u \to v 路径上经过了两条切边等价的边，那么断开它们后图不连通。但是注意图不连通不等于 u \to v 不连通，u,v 可能通过非树边连通。

考虑一条树上极长的切边等价连续段路径 u \to v。显然对于任意一条真子路径 u' \to v'，u',v' 都不可能不通过这个等价类连通。考虑 u,v 是否可以通过非这个等价类的边连通。

• 如果 u,v 任意一个的度数是 1，那这和边双连通图矛盾；
• 如果 (u,v) 只被 1 条非树边经过，显然应该被删除。
• 如果 (u,v) 这个等价类段出现不止一次，那也不可能连通，感性理解就是永远跨不进两段中间。
• 剩余情况即这个等价类出现的是连续一条链。此时直接走跨过它的非树边绕过去即可。必定可以连通。

因此添加一条边 (u,v) 后，然后再跑上述找连通块算法即可。使用线性哈希表的总复杂度是 \mathcal O(n+m)。

耳分解与双极定向

耳分解

对于无向图 G 的某个子图 G'，如果一条简单路径/简单环 p_1,p_2,\ldots,p_k 满足 p_1,p_k \in G' 且 \forall i \in [2,k-1],p_i \not \in G'，则称 P 是关于 G' 的一个开耳。

如果一张无向图可以从一个点开始，每次加入一个开耳，最后扩展到全图，我们就称这张图是可以耳分解的。

无向图可以耳分解的充要条件是，图是边双连通的。耳分解是刻画边双连通结构的好结构。

• P5776 [SNOI2013] Quare

考虑每次加入一个耳来刻画边双连通结构。数据范围很小，考虑状态压缩 DP 暴力模拟耳分解的过程。

设 f_S 是点集合 S 进行耳分解的最小代价，每次需要加入一个耳。但是枚举新加入的一整个耳的复杂度太高了，考虑一条一条边的加入。

设 dp_{S,u,v} 表示当前点集合是 S，要加入一条 u \to v 的路径的最小代价。考虑转移：

• 从完整的边双出发，加入一个 u \to x \to \ldots \to v 的耳。此时有 f_S + d_{u,x} \to dp_{S,u,v}。
• 继续加入耳，有 dp_{S,u,v} + d_{u,w} \to dp_{S|\{u\},w,v}。
• 封上一个耳，有 dp_{S,u,v} + d_{u,v} \to f_{S|\{u\}}。

但是这样会有问题。情况 1 的 u = v 时，会导致转移反复利用一条边，形成 u \to x \to u 的二元环。为了解决这个问题，我们特判这个情况：

• 上面的转移钦定 u \ne v。
• 特判二元环，有转移 f_S + d_{u,v} + d'_{u,v} \to f_{S|\{v\}} ，其中 d' 指的是两点之间的次短边。
• 特判 u = v 的大于二元环。此时需要环上的第一个点转移时不能回到 u，可以在状态里再加一维 0/1，但是更方便的是，注意到上面的状态都能保证 u \not \in S，这种情况我们直接让 S 并上 u 来表示。

总的复杂度是 \mathcal O(2^nn^3)，还是很快的！

双极定向

无向图的双极定向问题指的是，给每条边定向，使得：

• 这张有向图是有向无环图。
• 点 1 的入度是 0，且其它点的入度均不是 0。
• 点 n 的出度是 0，且其它点的出度均不是 0。

这个问题等价于，找一个排列 p 满足 p_1 = 1,p_n = n 且其每一个前缀和每一个后缀的导出子图都连通。

上述问题有解的充要条件是：加入一条边 (1,n) 后图是边双连通的。

根据两种不同的题目描述有两种做法，这里将介绍按照第一份题目描述的做法。

考虑首先找到一棵以 1 为根的 dfs 树，那么 1 \to n 路径上所有边应该都定向成向下。

然后考虑定向一条树边 (x,y) 后，找到所有返祖边 (x,u) 满足 u 在 y 子树内，将 x \to u 定向成与 x \to y 相同的方向，将 u 向上的所有未定向树边全都定反向，如下图。这个过程可以 bfs 一直做下去。

首先这样定向完所有路径都是 1 \to n 方向的，因此显然是一个 DAG。然后没有返祖边的树边都以路径的形式被穿过，显然至少有一条入边一条出边；如果有返祖边那么返祖边和反向的树边显然构成一入一出（此处要求上面的树边未被定向，但是如果上面的树边已经被定向且这个点不是 n 那这个点就已经满足要求）。什么时候会无解？需要有一条不在 1 \to n 路径上的树边没有被任何返祖边覆盖，此时这条边怎么定向都无解（注意需要是 DAG）。这个条件等价于加入一条边 (1,n) 后图仍然不边双连通。

• CF730K Roads Orientation Problem

双极定向板子题。