欧拉回路相关问题

定义：

按照是否回到出发点分别定义为欧拉回路和欧拉路径，同时也分别称图为欧拉图和半欧拉图。

注：以下讨论均建立在图联通的基础上，且欧拉回路并不局限于简单图。

存在性判定：

无向图为欧拉图当且仅当无奇度点。
无向图为半欧拉图当且仅当存在2个奇度点。
有向图为欧拉图当且仅当所有点入度等于出度。
有向图为半欧拉图当且仅当存在一个点入度等于出度 + 1，一个点入度等于出度 - 1。

生成欧拉回路：

Hierholzer 算法：证明暂时不会，据说与存在性判定证明等价，时间复杂度\(O(n+m)\)。

模板如下：选择合适起点开始dfs，路径倒序存储在res中，对于欧拉回路，首尾均为起点。

//有向图
int cur[N];
vector<int>path;
vector<vector<int>>e;
void dfs(int u)
{
    for (int& i = cur[u]; i < e[u].size(); i = cur[u])
    {
        i++;
        dfs(e[u][i]);
    }
    path.push_back(u);
}
//无向图
int h[N], e[N << 1], ne[N << 1], idx = 2, cur[N];
bool vis[N];
void dfs(int x) {
    for (int& i = cur[x]; i;) {
        if (!vis[i]) {
            vis[i] = vis[i ^ 1] = 1;
            dfs(e[i]);
        }
        i = ne[i];
    }
    res.push_back(x);
}

对于求字典序最小的欧拉路径，只需在算法执行前对出边从小到大排序即可。

性质与结论：

对于存在 \(2k (k > 0)\) 个奇度顶点的图，至少需要 \(k\) 笔才能画完。且每次都需要选择两个奇度顶点作为起点和终点。
对于无向图 \(G\) ，所有顶点的度都是偶数等价于图 \(G\) 有圈分解。圈分解即为用若干个圈（不重复经过顶点的回路）使图 \(G\) 的每一条边恰经过一次。
有向欧拉图中以任意一点为根的内向树个数均相同。

相关计数：

问题：求有 \(n\) 个节点且无奇度点的有标号简单无向图个数。

先考虑前 \(n - 1\) 个顶点，发现无论如何连边，都可以通过 \(n\) 号点来微调满足均为偶度点的条件，且对应的 \(n\) 号点连边方式是唯一的，于是方案数为 \(2^{\binom{n-1}{2}}\)。

问题：求有 \(n\) 个节点的有标号无向欧拉图个数。

记 \(f_i\) 为有 \(n\) 个节点的有标号无向欧拉图个数，\(g_i\) 为有 \(n\) 个节点且无奇度点的有标号简单无向图个数。则 \(g_i = 2^{\binom{n-1}{2}}\)，而\(f_i = g_i - g_i\) 中不联通的部分。后者可以通过枚举 \(i\) 号点所在连通块大小确定，即 \(\sum_{j=1}^{i-1}f_jg_{i-j}\binom{i-1}{j-1}\)。

于是 \(f_i = g_i - \sum_{j=1}^{i-1}f_jg_{i-j}\binom{i-1}{j-1}\)。

生成函数：待更新。

问题：给定 \(n\) 个节点 \(m\) 条边的无向连通图，求该图有多少无奇度点的生成子图。

考虑原图任意一颗生成树，对于非树边，我们随便决定是否保留，对于树边，我们先随意选择一个点为根，然后自底向上调整非根结点为偶度点。也就是说树边是否保留是确定的，因为奇度点的个数为偶数，所以此时的根必为偶度点，符合条件。

综上，合法的生成子图个数为 \(2^{m-n+1}\)。

问题：给定 \(n\) 个节点 \(m\) 条边的无向连通图，求从 \(1\) 号点开始的欧拉回路数。

先找到一棵以 1 号点为根的内向树（即每个点有唯一的一条路径到达 1 号点），然后为一个点的所有不在树上的出边定序。则上述方案与欧拉回路一一对应。

详细证明见2018国家集训队论文《欧拉图相关的生成与计数问题探究》。

根据上述结论，记 \(T_i\) 为以 \(i\) 为根的内向树数量，\(d_i\) 为 \(i\) 号点的出度。对 \(1\) 号点定序，我们有 \(d_1!\) 种方案，而对非根结点 \(i\) 定序，我们有 \((d_i-1)!\) 种方案。所以所求方案数 \(=T_1d_1!\prod_{i = 2}^{n}(d_i-1)!\) 。

问题：给定 \(n\) 个节点 \(m\) 条边的有向欧拉图，求欧拉回路数。（BEST 定理）

因为欧拉回路是循环同构的，为了避免重复计数，我们按照最小表示法确定起点，即第一条边总是 \(1\) 号结点编号最小的出边。分析可知对于上一个问题得到的答案，每一条欧拉回路都会重复统计 \(d_1\) 次，于是欧拉回路数量\(=T_1\prod_{i = 1}^{n}(d_i-1)!\) 。

注：\(T_i\) 可以通过矩阵树定理求出，时间复杂度为 \(O(n^3)\) 。

欧拉回路相关问题

定义：

存在性判定：

生成欧拉回路：

性质与结论：

相关计数：

题单：

参考资料：