十二重子图计数

· · 算法·理论

前言

:::warning[AI 使用说明] 使用了 deepseek v3 提供了难度评级（Trivial、Easy、Medium、Hard、Advanced）和错别字修正。 :::

本文整理了一些列无向图中的常见子图计数问题。由于笔者组合计数方面实在薄弱，所以并没有写什么和组合有关的计数问题，畏惧数学的 OIer 也可放心观看。

后续可能会整理这些问题的代码。

:::info[约定]{open} 以下讨论的计数问题默认都是无向图，无重边，无自环。用 deg_i 代表有 deg_i 条边的端点为 i。 :::

联通块计数（难度：Trivial）

:::success[结构]{open} 一个联通块内的点两两之间可以通过边直接或间接连接。求图中有多少个不同的联通块。可以发现任意两个不同的联通块点集无交且所有点集的并为整张图所有的点。 :::

直接扫描所有顶点，对未访问点进行 dfs 标记连通分量并计数。也可以用并查集统计不同祖先实现。

复杂度：\mathcal O(n + m)。

三点链计数（难度：Trivial）

:::success[结构]{open} 统计长度为 2（包含 3 个点）的简单路径数量。 :::

枚举中间点 v，以 v 为中间点的三元环数量为 \frac{deg_i \times (deg_i - 1)}{2}。因此所有简单路径数量为 \sum \limits_{i = 1}^{n} \frac{deg_i \times (deg_i - 1)}{2}。

复杂度：\mathcal O(n + m)。

三叉星计数（难度：Easy）

:::success[结构]{open} 四个点，一个点挂 3 个叶子。求图中有多少个三叉星子图。 :::

枚举中间点 v，以 v 为中间点的三叉星数量为 \frac{deg_i \times (deg_i - 1) \times (deg_i - 2)}{6}。因此所有简单路径数量为 \sum \limits_{i = 1}^{n} \frac{deg_i \times (deg_i - 1) \times (deg_i - 2)}{6}。

复杂度：\mathcal O(n + m)。

二分图计数（难度：Easy）

:::success[结构]{open} 将所有点红蓝染色后使得任意边连接的两个点颜色不同。求最多染多少个红点。若不存在任意染色方案输出 0。 :::

判断一个联通块是否为二分图可以 dfs 染色。如果存在一个联通块不能染色则整张图无法染色。否则钦定一个联通块的其中一个点是红色，染色完成后若蓝色比红色多就交换蓝色和红色。最后答案是所有联通块答案的加和。

复杂度：\mathcal O(n + m)。

三元环计数（难度：Medium）

:::success[结构]{open} 三个点，两两之间有连边。求图中有多少个三元环子图。 :::

将所有边定向，使得度数小的点指向度数大的点。并且按照这个顺序标号。

对每个顶点 u，枚举其出边邻居 v，再枚举 v 的出边邻居 w。若 w 也是 u 的出边邻居，则 (u , v , w) 构成一个三元环。每个三元环只会被枚举一次，并且一定是按照标号从小到大排列 u , v , w 的。

复杂度：O(m\sqrt m)。

:::info[复杂度证明] 记 d = \sqrt{2m}。定向后，每个顶点 v 的出度 \operatorname{out}(v) \le d：

综上，算法总循环次数为：

::: # 四点链计数（难度：Medium） :::success[结构]{open} 统计长度为 $3$（包含 $4$ 个点）的简单路径数量。 ::: 枚举中间边，设两端点为 $u , v$。则这个边作为中间边的四点链有 $(deg_u - 1) \times (deg_v - 1)$ 个，因为存在边 $u , v$ 所以 $deg_u$ 和 $deg_v$ 都至少为 $1$，无需担心 $-1 \times -1$ 出现问题。因此目前答案为 $\sum\limits_{i = 1}^{m} (deg_{u_i} - 1) \times (deg_{v_i} - 1)$。 考虑 $1 \to 2 \to 3 \to 1$ 的情况，发现两端有重合点的情况会形成三元环而不是四点链。因为三元环的每条边都会额外贡献一次答案，所以总答案减去 $3 \times$ 三元环数量即可。 复杂度 $O(m \sqrt{m})$，瓶颈在三元环计数。 # 四元环计数（难度：Medium） :::success[结构]{open} 四个点，每个点度数都为 $2$，构成一个环。求图中有多少个四元环子图。 ::: 按照三元环计数的做法将图定向。对每个顶点 $u$，枚举其两个不同的出边邻居 $v, w$。记录当前轮次中，点 $x$ 被作为 $v$ 和 $w$ 共同指向的次数。 发现每处理一个 $u$，它的每对出边邻居 $(v , w)$ 若存在边 $v \to x$、$w \to x$，则每发现一次计数 $+1$，设目前计数为 $cnt_i$，则四元环数量增加 $\frac{cnt_i \times (cnt_i - 1)}{2}$。 复杂度：$O(m\sqrt m)$。 证明方式和三元环相似。 # 钻石图计数（难度：Hard） :::success[结构]{open} 两个三元环共享一条边。求图中有多少个钻石图子图。 ::: 用和三元环相同的定向法枚举每个三元环并给三条边各计数一次，最后每条边的计数 $cnt_i$ 贡献 $\frac{cnt_i \times (cnt_i - 1)}{2}$ 个钻石图子图，注意这里是给边计数而不是点。 答案为 $\sum\limits_{i = 1}^{m} \frac{cnt_i \times (cnt_i - 1)}{2}$。 复杂度 $\mathcal O(m \sqrt m)$。证明方法和正确性见三元环计数。 # 领结图计数（难度：Hard） :::success[结构]{open} 两个三元环共享一个顶点。求图中有多少个领结图子图。 ::: 发现很难直接求出，考虑容斥。用相同方法枚举三元环并统计每个顶点所在三元环数 $cntv_i$ 和每条边所在三元环数 $cnte_i$，则共用**至少**一个顶点的两个三元环数量是 $\frac{cntv_i \times (cntv_i - 1)}{2}$。减去钻石图的贡献即可。 因为钻石图有两个公共点，所以对两端每个点都多贡献了一次。答案为 $\sum \limits_{i = 1}^{n} \frac{cntv_i \times (cntv_i - 1)}{2} - 2 \times \sum \limits_{i = 1}^{n} \frac{cnte_i \times (cnte_i - 1)}{2}$。 复杂度 $\mathcal O(m \sqrt m)$。所有需要的部分都在前面提及过。 # 双四元环计数（难度：Hard） :::success[结构]{open} 两个四元环共享一条边。求图中有多少个双四元环子图。 ::: 先用四元环计数中的定向方法，统计每条边所在的四元环数量，记为 $cnt_i$。我们可以仍然采用度数定向法来做。对每个顶点 $x$，枚举其两个出边邻居 $y , z$，在 $y , z$ 处累加。遍历过程中即可统计出每条边所在四元环的个数。可以发现四元环中每条边都会恰好被计数一次，因此直接累加即可。 对于每条边，它作为公共边能够形成的双四元环数量即为从 $cnt_i$ 个包含该边的四元环中任选两个的组合数。因此答案为： $$\sum_{i = 1}^m \frac{cnt_i \times (cnt_i - 1)}{2}$$ 复杂度：$\mathcal O(m\sqrt m)$，瓶颈在四元环计数。 # 五元环计数（难度：Advanced） :::success[结构]{open} 五个点，每个点度数都为 $2$，构成一个环。求图中有多少个五元环子图。 ::: :::success[稀疏图] 将所有边按度数定向，度数小的指向度数大的，度数相同按编号从小到大定向。记有向图为 $G'$，顶点 $u$ 的出边列表为 $\operatorname{out}(u)$。 对每个顶点 $u$，枚举其两条不同的出边 $u \to v$ 和 $u \to w$。再枚举 $v$ 的出边 $v \to x$ 以及 $w$ 的出边 $w \to y$。若 $x$ 与 $y$ 之间有边且该边在定向图中为 $x \to y$ 或 $y \to x$，则检查五个点 $u , v , w , x , y$ 是否互不相等，若互不相等则构成五元环。通过强制 $u$ 为五个点中在定向图上出度最小的那个，可以保证每个五元环只被计数一次。 如何实现：对每个点 $u$，预处理其出边列表 $\operatorname{out}(u)$。出边对 $(v , w)$，满足 $v < w$（仍然是三元环计数时的编号方式）。 对固定的 $(u , v , w)$，遍历 $v$ 的出边 $x \in \operatorname{out}(v)$；遍历 $w$ 的出边邻居 $y \in \operatorname{out}(w)$，满足 $u , v , w , x , y$ 互不相等。 哈希检查边 $(x , y)$ 是否存在。若存在，则记录一个五元环 ${u , v , w , x , y}$。 为保证每个五元环恰好计数一次，我们规定 $u$ 必须是五个点中在定向顺序下最小的顶点。由于定向规则保证了 $u \to v$ 和 $u \to w$，而 $v \to x$ 和 $w \to y$，最后 $x , y$ 之间的边方向必然使得 $x , y$ 之一指向另一个，且整个环上点的度数顺序符合定向要求。该约定使得每个五元环在其唯一的最小顶点 $u$ 处被枚举。 复杂度：$\mathcal O(ans) \approx \mathcal O(m^2\sqrt m)$。 ::::info[复杂度证明] 设 $d = \sqrt{2m}$。定向后每个顶点的出度 $\operatorname{out}(u) \le d$。 枚举外层顶点 $u$ 的每对出边 $(v,w)$ 的次数为 $\sum\limits_{u} \frac{|\operatorname{out}(u)| ^ 2 \times (|\operatorname{out}(u)| ^ 2 - 1)}{2} \le \sum\limits_{u} \frac{|\operatorname{out}(u)| ^ 2}{2} \le \frac{d}{2} \sum\limits_{u} |\operatorname{out}(u)| = \frac{dm}{2} \approx m\sqrt m$。 对每对 $(v , w)$，枚举 $v$ 的出边和 $w$ 的出边，两层循环的上界均为 $d$，因此内部枚举总次数不超过 $d^2$ 乘以 $(v , w)$ 对数。因此总枚举次数不超过 $m^2 \sqrt{m}$ 量级。 ::: :::success[稠密图] 考虑 dp。设 $a_{i , j , k}$ 表示从 $i$ 到 $j$ 长度为 $k$ 的路径条数。 由于五元环可以看作一个长度为 $2$ 的路径和一个长度为 $3$ 的路径在两端点拼接而成，我们分别计算 $a_{i , j , 2}$ 和 $a_{i , j , 3}$。 转移方程： $$a_{i , j , k} = \sum_{t = 1}^{n} a_{i , t , 1} \times a_{t , j , k - 1}$$ 其中 $a_{i , j , 1}$ 就是邻接矩阵。 对于 $k = 2$ 和 $k = 3$ 分别计算，复杂度 $O(n^3)$（$n$ 为顶点数）。 拼接时，对于每个有序对 $(i , j)$，以 $i$ 为起点、$j$ 为终点的五元环数量为 $a_{i , j , 2} \times a_{i , j , 3}$。但由于无向图中每条边会被双向计算，且环的起点和方向会被重复计数，最终答案需除以 $10$，因为每个五元环有 $5$ 个起点 $\times 2$ 个方向 $= 10$ 种表示方法。 这样得到的计数包含了非简单环的情况，其中主要干扰来自三元环加上一条额外的边）。我们需要减去这些非法情况。 枚举所有三元环 $(x , y , z)$，使得 $x \leftrightarrow y , x \leftrightarrow z , y \leftrightarrow z$ 在 $G$ 中存在。对于每个三元环，它贡献的假五元环个数为 $(deg_x + deg_y + deg_z - 3)$，减去这部分即可。 最终答案为： $$\frac{\sum_{i = 1}^{n} \sum_{j = 1}^{n} a_{i , j , 2} \cdot a_{i , j , 3}}{10} - \sum_{\substack{(x , y , z) \\ x \leftrightarrow y , x\leftrightarrow z , y \leftrightarrow z}}(deg_x + deg_y + deg_z - 3)$$ 复杂度 $O(n^3)$。 ::: # 特殊图计数（举例黄蜂图）（难度：Advanced） :::success[结构]{open} ![pic](https://cdn.luogu.com.cn/upload/image_hosting/evvzvkrz.png) 求图中有多少个黄蜂图子图。 ``` 1 2 1 3 1 4 1 5 4 5 4 6 5 7 6 7 6 8 7 9 8 9 8 10 9 10 ``` ::: 设任意图为 $H$，则我们计算它的宽度 $k$，然后可以使用 $n^{k + 1}$ dp 计算子图数量，例如这个黄蜂图的宽度为 $2$，从图中可以直观感受到。 :::info[如何计算图的宽度] 图的树宽衡量图与树的相似程度。树宽为 $k$ 的图存在一个树分解，其中每个袋子大小不超过 $k + 1$，且满足： - 每个顶点至少出现在一个袋子中。 - 每条边的两个端点同时出现在某个袋子中。 - 对于任意顶点 $v$，包含 $v$ 的所有袋子在树中连通。 精确计算树宽是 NP 难的，但对于小图可手工构造袋子。 黄蜂图可分解为大小 $3$ 的袋，故树宽 $k = 2$。 ::: :::info[什么是单射] 单射指不同的元素映射到不同的像，即若 $x \neq y$ 则 $f(x) \neq f(y)$。在黄蜂图计数 dp 中，$\sigma : x \to V(G)$ 为单射意味着袋子 $x$ 中不同的顶点必须映射到输入图 $G$ 中不同的顶点，以保证子图同构的顶点互不相同。 ::: :::info[嵌入数] 嵌入数指将 $H$ 的顶点映射到 $G$ 的顶点的所有单射 $\varphi : V(H) \to V(G)$，使得每条边 $(u , v) \in E(H)$ 对应边 $(\varphi(u) , \varphi(v)) \in E(G)$。$\texttt{子图个数} = \frac{\texttt{嵌入数}}{|H \texttt{的自同构群}|}$。对于黄蜂图，$|H \texttt{的自同构群}| = 4$。 ::: 首先我们为黄蜂图构造袋子： - $\{1 , 4 , 5\}$； - $\{4 , 5 , 6\}$； - $\{4 , 6 , 7\}$； - $\{5 , 6 , 7\}$； - $\{6 , 7 , 8\}$； - $\{6 , 8 , 9\}$； - $\{7 , 8 , 9\}$； - $\{8 , 9 , 10\}$。 然后我们构造 dp 状态： 对树分解自底向上计算。每个袋子 $x$ 的状态为：从 $x$ 中顶点到 $G$ 中顶点的所有单射 $\sigma$，且满足 $x$ 内部边在 $G$ 中必须存在。 - 先枚举所有 $n^3$ 种单射，检查内部边，合法则 $dp_x(\sigma) = 1$，否则 $0$。 - 然后枚举 $\sigma_x$，对其每个子袋子 $y$，枚举 $\sigma_y$，要求 $\sigma_x$ 与 $\sigma_y$ 在 $x \cap y$ 上一致，且 $x \cup y$ 中所有边在 $G$ 中均存在。乘法原理统计子袋的贡献，得到 $dp_x(\sigma_x)$。 - 根袋子的 $dp$ 值之和即为 $H$ 在 $G$ 中的嵌入数。 我们发现这样统计会有重复，比如会将左右触角相反的黄蜂统计为两个子图。考虑去重： 黄蜂图的自同构群大小 $ = 4$： - $2 \leftrightarrow 3$； - $9 \leftrightarrow 10$。 因此最终答案等于嵌入数除以 $2 \times 2 = 4$。 复杂度：$\mathcal O(n^3)$。 :::info[复杂度证明] 树分解的袋子数为常数，每个袋子枚举 $n^3$ 种映射，可以 $\mathcal O(1)$ dp 转移，同时袋子个数是常数量级。因此总复杂度 $\mathcal O(n^3)$。 ::: # 结语 呼——终于数完了！如果您现在看到一条边就想枚举它的度数，看到三个点就想数三角形，建议立刻关闭电脑，出门呼吸一下新鲜空气。 当然，如果写出了 $\mathcal O(n^3)$ 的子图计数并且 $n$ 恰好是 $10^5$，别慌，虔诚地祈祷评测机是量子计算机即可，上述内容有很大概率跑不满，复杂度分析也是最劣情况。 子图诚可贵，复杂度更高。若为 AC 故，二者皆可调。 # Fun Fact 本文共使用了： - $463$ 个 `$`； - $203$ 个 `\`； - $149$ 个 `m`； - $144$ 个 `:`； - $127$ 个 `{`； - $127$ 个 `}`； - $106$ 个 `n`。 # 练习 |计数问题|练习题（整理中）| |--|--| |联通块计数|[AT_abc284_c](https://www.luogu.com.cn/problem/AT_abc284_c) [P8654](https://www.luogu.com.cn/problem/P8654)| |三点链计数|| |三叉星计数|| |二分图计数|[CF2204D](https://www.luogu.com.cn/problem/CF2204D)| |三元环计数|[P1989](https://www.luogu.com.cn/problem/P1989) [AT_abc262_b](https://www.luogu.com.cn/problem/AT_abc262_b) [CF922B](https://www.luogu.com.cn/problem/CF922B)| |四点链计数|| |四元环计数|[CF489D](https://www.luogu.com.cn/problem/CF489D) [U367189](https://www.luogu.com.cn/problem/U367189) [LOJ191](https://loj.ac/p/191)| |钻石图计数|| |领结图计数|| |双四元环计数|| |五元环计数|[CF51E](https://www.luogu.com.cn/problem/CF51E)| |特殊图计数|| 欢迎投稿原题或极其相似的练习题（在练习题收集到一定数量时将会重新提交审核，麻烦专栏志愿者了，感谢）！