资讯详情

广义串并联图

本文中默认无向图是连通的。不连通的图会特别指出。

若无向图 \(G\) 不存在同胚于 \(K_4\) 的子图，则称 \(G\) 是广义串并联图。

显然，树、基环树、仙人掌都是广义串并联图。

广义串并联图方法

对无向图 \(G\) 执行下面三个操作：

• 删一度点：若 \(u\) 的度数为 \(1\)，则把 \(u\) 和与之相连的边删除。
• 缩二度点：若 \(u\) 的度数为 \(2\)，设与之邻接的点为 \(v,w\)，则把 \(u\) 和边 \((u,v),(u,w)\) 删除，添加一条边 \((v,w)\)。
• 叠合重边：若存在两条边 \((u,v)\)，删除其中一条。

称为广义串并联图方法。

广义串并联图方法可以通过类似于拓扑排序的方式实现。

我们不加证明地给出以下结论：

• 若 \(G\) 是广义串并联图，则对其应用广义串并联图方法可以将其缩为一个点。
• 若 \(G\) 是有 \(n\) 点 \(m\) 边的一般无向图，设 \(k=m-n\)，则对其应用广义串并联图方法可以将其缩为 \(n'\le 2k,m'\le 3k\) 的新图。

第二个结论常用于题目保证 \(k\) 很小的情况。由此可以看出，广义串并联图方法并不局限于广义串并联图使用。先将 \(k\) 较小的图的点数和边数缩小到 \(O(k)\) 量级再跑爆搜或者状压 DP 也是一个很常用的套路。

在应用广义串并联图方法缩图的过程中，常常根据题意在点或边上维护 DP，在删一度点、缩二度点、叠合重边时进行转移。

例题：P6790 [SNOI2020] 生成树

显然，无向图 \(G\) 是广义串并联图。

设 \(f_{(u,v),0/1}\) 表示在不考虑其他边的情况下，\((u,v)\) 这条边不选/选的方案数。

初值是 \(f_{(u,v),0}=f_{(u,v),1}=1,\forall(u,v)\in V\)，\(\textrm{ans}=1\)。

接下来考虑三种操作时的转移。

删一度点：设一度点为 \(v\)，邻接点为 \(u\)。要选出生成树出来，那么 \((u,v)\) 这条边必须选，直接把 \(f_{(u,v),1}\) 乘到答案里。

\[\textrm{ans}\gets\textrm{ans}\times f_{(u,v),1} \]

缩二度点：设二度点为 \(v\)，邻接点为 \(u,w\)。要得到生成树，\((u,v),(v,w)\) 不能都不选（不然 \(v\) 就不连通了），两条边都选才相当于选了边 \((u,w)\)。

\[\begin{aligned} f_{(u,w),1}&\gets f_{(u,v),1}\times f_{(v,w),1}\\ f_{(u,w),0}&\gets f_{(u,v),1}\times f_{(v,w),0}+f_{(u,v),0}\times f_{(v,w),1}\\ \end{aligned} \]

叠合重边：设有两条 \((u,v)\) 边，记作 \((u,v)_1\) 和 \((u,v)_2\)。要得到生成树，这两条边最多选一条（不然就有重边了），两条边都没选才相当于没选 \((u,v)\)。

\[\begin{aligned} f_{(u,v),1}&\gets f_{(u,v)_1,1}\times f_{(u,v)_2,0}+f_{(u,v)_1,0}\times f_{(u,v)_2,1}\\ f_{(u,v),0}&\gets f_{(u,v)_1,0}\times f_{(u,v)_2,0}\\ \end{aligned} \]

缩成一个点时 \(\textrm{ans}\) 即为答案。

习题：P10779 BZOJ4316 小 C 的独立集

已 AC，待补充。

习题：P4426 [HNOI/AHOI2018] 毒瘤

已 AC，待补充。

习题：P10044 [CCPC 2023 北京市赛] 最小环

已 AC，待补充。

习题：P8426 [JOI Open 2022] 放学路 / School Road

已 AC，待补充。

习题：P11832 [省选联考 2025] 图排列

不会做。