欧拉图(Euler Graph)

约 355 个字 20 行代码 预计阅读时间 1 分钟

定义

• 欧拉回路：通过图中每条边恰好一次的回路
• 欧拉通路：通过图中每条边恰好一次的通路
• 欧拉图：具有欧拉回路的图
• 半欧拉图：具有欧拉通路但不具有欧拉回路的图

性质

欧拉图中所有顶点的度数都是偶数。

若 $G$ 是欧拉图，则它为若干个环的并，且每条边被包含在奇数个环内。

判别法

1. 无向图是欧拉图当且仅当：
   • 非零度顶点是连通的
   • 顶点的度数都是偶数
2. 无向图是半欧拉图当且仅当：
   • 非零度顶点是连通的
   • 恰有 2 个奇度顶点
3. 有向图是欧拉图当且仅当：
   • 非零度顶点是强连通的
   • 每个顶点的入度和出度相等
4. 有向图是半欧拉图当且仅当：
   • 非零度顶点是弱连通的
   • 至多一个顶点的出度与入度之差为 1
   • 至多一个顶点的入度与出度之差为 1
   • 其他顶点的入度和出度相等

查找无向图欧拉回路

定义全局变量use[N]，表示点u的前use[u]条边已经被用过了，dfs时只走没用过的边，边为二元组（另一点，反向边的存储位置），记录第二个信息方便标记反向边已经用过

int use[N];
vector<array<int, 2>> e[N];
void dfs(int u)
{
    while (use[u] < e[u].size())
    {
        auto [v, ind] = e[u][use[u]];
        if (v == -1)
        {
            ++use[u];
            continue;
        }
        e[v][ind][0] = -1;
        ++use[u];
        dfs(v);
    }
}
int pos1 = e[u].size(), pos2 = e[v].size();
e[u].push_back({v, pos2});
e[v].push_back({u, pos1});