无向图中含k条边的偶正则子图计数算法求解

核心概念回顾 #

偶正则子图等价于偶度边子集：子图中每个顶点的度数均为偶数（包括0，即空集）。这类子集构成图的循环空间（GF(2)上的向量空间），其维度为 d = m - n + c，其中m是总边数，n是总顶点数，c是连通分量数。

分治策略：按连通分量处理 #

整个图的偶正则子图是各连通分量的偶正则子图的不交并，因此可按以下步骤拆分问题：

• 拆分原图为所有连通分量；
• 对每个连通分量计算其偶度边子集的生成函数（按边数计数的多项式）；
• 将所有连通分量的生成函数相乘，结果中x^k的系数即为所求的计数。

单个连通分量的生成函数计算 #

针对单个连通分量H（含n_H个顶点、m_H条边，循环空间维度d_H = m_H - n_H + 1），具体步骤如下：

1. 生成循环空间的基：
   • 为H构造一棵生成树，得到n_H - 1条树边，剩余d_H条非树边；
   • 每条非树边对应一个基本回路：由该非树边加上生成树中连接其两端的唯一路径组成，记为C_1, C_2, ..., C_{d_H}，每个回路的边数为s_1, s_2, ..., s_{d_H}。
2. 动态规划计算生成函数：
   • 初始化状态：用哈希表或数组维护dp，其中dp[t]表示当前得到的含t条边的偶度子集数量，初始时dp[0] = 1（空集），其余为0；
   • 逐个处理每个基本回路C_i：
     遍历当前dp中的所有非零项，对每个t对应的计数cnt，计算加入C_i后得到的新子集的边数t' = t + s_i - 2 * |当前子集与C_i的公共边数|（公共边在对称差中会被抵消）；
     更新dp：dp[t'] += cnt（需注意GF(2)下的线性组合，相同特征向量的项合并计数）；
   • 最终dp数组即为该连通分量的生成函数，dp[t]就是H中含t条边的偶度子集数量。

复杂度分析 #

暴力枚举所有边子集的复杂度为O(2^m)，而本算法的时间复杂度为O(Σ_{H} 2^{d_H} * m_H)，其中Σd_H = d = m -n +c。由于d通常远小于m（例如连通图中d = m -n +1，当图是树时d=0，仅空集一个偶度子集），因此复杂度显著优于暴力法。

补充说明 #

• 孤立顶点不影响偶度子集的边数计数，可直接忽略；
• 空集是合法的偶正则子图，若题目要求非空结果，只需在k=0时将计数减1。

内容的提问来源于stack exchange，提问作者katsudon