专栏文章

神秘图论

ssunkuangzheng
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqgetfs
此快照首次捕获于
2025/12/04 04:22
3 个月前
此快照最后确认于
2025/12/04 04:22
3 个月前
查看原文

切边等价理论

在边双连通图里，定义两条边 e1,e2e_1,e_2 是 切边等价 的，当且仅当任意一个简单环要么同时包含 e1,e2e_1,e_2，要么同时不包含 e1,e2e_1,e_2。
上面的条件等价于：
  • 同时断开 e1,e2e_1,e_2 后图不连通。
  • 若 e1,e2e_1,e_2 都是生成树的树边，则任意非树边要么同时跨过 e1,e2e_1,e_2，要么同时不跨过。
条件一等价于断开 e1e_1 后 e2e_2 是割边，因此包含 e2e_2 的所有简单环都需要包含 e1e_1；同理包含 e1e_1 的所有简单环也需要包含 e2e_2。
可以根据条件二快速找到切边等价类：给每条非树边随一个权值，给路径上所有树边异或上这个权值。边权相等的边是一个切边等价类。特别的，边权为 00 的边是图的割边。
推论：图的极小割集的边权异或和是 00；异或和是 00 的边集是图的割集。
根据上述推论，找输入的边集是否存在异或和为 00 的子集即可。
考虑一个大小为 tt 的切边等价类。 如果有 k∣tk \mid t，那直接给每个颜色染 t/kt/k 条边显然合法；因此，k∣gcd⁡(ti)k \mid \gcd(t_i) 是一个 kk 合法的充分条件。
我们猜测这就是一个 kk 合法的充要条件。必要性的证明先咕一下。

边三连通分量

一个很 naive 的想法是，如果一个切边等价类的大小大于 11，就把这些边全都断开。然后剩下的每一个连通块就是一个边三。这个做法看起来很优美，但是是假的，看下图：
这个图里 3,4,5,7,83,4,5,7,8 是一个边三连通分量，但是按照上述做法会求出 4,5,7,84,5,7,8 和 33 两个。
上面断边想法的来源是，如果 u→vu \to v 路径上经过了两条切边等价的边，那么断开它们后图不连通。但是注意图不连通不等于 u→vu \to v 不连通，u,vu,v 可能通过非树边连通。
考虑一条树上极长的切边等价连续段路径 u→vu \to v。显然对于任意一条真子路径 u′→v′u' \to v'，u′,v′u',v' 都不可能不通过这个等价类连通。考虑 u,vu,v 是否可以通过非这个等价类的边连通。
  • 如果 u,vu,v 任意一个的度数是 11，那这和边双连通图矛盾；
  • 如果 (u,v)(u,v) 只被 11 条非树边经过，显然应该被删除。
  • 如果 (u,v)(u,v) 这个等价类段出现不止一次，那也不可能连通，感性理解就是永远跨不进两段中间。
  • 剩余情况即这个等价类出现的是连续一条链。此时直接走跨过它的非树边绕过去即可。必定可以连通。
因此添加一条边 (u,v)(u,v) 后，然后再跑上述找连通块算法即可。使用线性哈希表的总复杂度是 O(n+m)\mathcal O(n+m)。

耳分解与双极定向

耳分解

对于无向图 GG 的某个子图 G′G'，如果一条简单路径/简单环 p1,p2,…,pkp_1,p_2,\ldots,p_k 满足 p1,pk∈G′p_1,p_k \in G' 且 ∀i∈[2,k−1],pi∉G′\forall i \in [2,k-1],p_i \not \in G'，则称 PP 是关于 G′G' 的一个开耳。
如果一张无向图可以从一个点开始，每次加入一个开耳，最后扩展到全图，我们就称这张图是可以耳分解的。
无向图可以耳分解的充要条件是，图是边双连通的。耳分解是刻画边双连通结构的好结构。
考虑每次加入一个耳来刻画边双连通结构。数据范围很小，考虑状态压缩 DP 暴力模拟耳分解的过程。
设 fSf_S 是点集合 SS 进行耳分解的最小代价，每次需要加入一个耳。但是枚举新加入的一整个耳的复杂度太高了，考虑一条一条边的加入。
设 dpS,u,vdp_{S,u,v} 表示当前点集合是 SS，要加入一条 u→vu \to v 的路径的最小代价。考虑转移：
  • 从完整的边双出发，加入一个 u→x→…→vu \to x \to \ldots \to v 的耳。此时有 fS+du,x→dpS,u,vf_S + d_{u,x} \to dp_{S,u,v}。
  • 继续加入耳，有 dpS,u,v+du,w→dpS∣{u},w,vdp_{S,u,v} + d_{u,w} \to dp_{S|\{u\},w,v}。
  • 封上一个耳，有 dpS,u,v+du,v→fS∣{u}dp_{S,u,v} + d_{u,v} \to f_{S|\{u\}}。
但是这样会有问题。情况 11 的 u=vu = v 时，会导致转移反复利用一条边，形成 u→x→uu \to x \to u 的二元环。为了解决这个问题，我们特判这个情况：
  • 上面的转移钦定 u≠vu \ne v。
  • 特判二元环，有转移 fS+du,v+du,v′→fS∣{v}f_S + d_{u,v} + d'_{u,v} \to f_{S|\{v\}} ，其中 d′d' 指的是两点之间的次短边。
  • 特判 u=vu = v 的大于二元环。此时需要环上的第一个点转移时不能回到 uu，可以在状态里再加一维 0/10/1，但是更方便的是，注意到上面的状态都能保证 u∉Su \not \in S，这种情况我们直接让 SS 并上 uu 来表示。
总的复杂度是 O(2nn3)\mathcal O(2^nn^3)，还是很快的！

双极定向

无向图的双极定向问题指的是，给每条边定向，使得：
  • 这张有向图是有向无环图。
  • 点 11 的入度是 00，且其它点的入度均不是 00。
  • 点 nn 的出度是 00，且其它点的出度均不是 00。
这个问题等价于，找一个排列 pp 满足 p1=1,pn=np_1 = 1,p_n = n 且其每一个前缀和每一个后缀的导出子图都连通。
上述问题有解的充要条件是：加入一条边 (1,n)(1,n) 后图是边双连通的。
根据两种不同的题目描述有两种做法，这里将介绍按照第一份题目描述的做法。
考虑首先找到一棵以 11 为根的 dfs 树，那么 1→n1 \to n 路径上所有边应该都定向成向下。
然后考虑定向一条树边 (x,y)(x,y) 后，找到所有返祖边 (x,u)(x,u) 满足 uu 在 yy 子树内，将 x→ux \to u 定向成与 x→yx \to y 相同的方向，将 uu 向上的所有未定向树边全都定反向，如下图。这个过程可以 bfs 一直做下去。
首先这样定向完所有路径都是 1→n1 \to n 方向的，因此显然是一个 DAG。然后没有返祖边的树边都以路径的形式被穿过，显然至少有一条入边一条出边；如果有返祖边那么返祖边和反向的树边显然构成一入一出（此处要求上面的树边未被定向，但是如果上面的树边已经被定向且这个点不是 nn 那这个点就已经满足要求）。什么时候会无解？需要有一条不在 1→n1 \to n 路径上的树边没有被任何返祖边覆盖，此时这条边怎么定向都无解（注意需要是 DAG）。这个条件等价于加入一条边 (1,n)(1,n) 后图仍然不边双连通。
双极定向板子题。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...