「有标号欧拉图计数」

发表于 分类于 ， ， 阅读次数：

题意：求 个点的，存在欧拉回路的有标号无向图数目。

答案对 取模，。

欧拉图的充要条件：点度均为偶数，且连通。

记点度均为偶数的图的集合为 ，欧拉图的集合为 ，类似有标号连通图

接下来的任务是求出 。

考虑一张 个点的任意图，通过加入一个编号为 的点，向点度为奇数的点连边，即可得到一张 个点的偶度图。

对于一张 个点的偶度图，通过删除编号为 的点后可以对应唯一的一个 个点的图。

这就证明了 点偶度图和 点任意图之间存在双射，故有 。