欧拉路与欧拉图 学习笔记

· · 个人记录

欧拉图的相关概念

设 G=(V,E)​ 是一张图：

注意，半欧拉图中不包含欧拉回路。

结合一笔画问题，从任意一个点开始都可以一笔画完的图是欧拉图，必须从某个点开始才能一笔画完的图是半欧拉图。

要注意区分欧拉图与哈密尔顿图（Hamilton graph）的差异：

哈密尔顿回路指从一个点出发，不重不漏地经过每个点的回路，而欧拉回路的定义中是边。

欧拉图的基本性质

证明：把欧拉回路分段，使每一段都是简单环。必要性同理。

证明：（必要性）设 G 有欧拉回路 v_1\ e_1\ v_2\ e_2\cdots\ v_m\ e_{m}\ (v_1)。

我们发现，v_i​ 的出现一次便意味着存在与之相连的两条边 e_{i-1} 和 e_i。（特别地，v_1 的出现是 e_1 和 e_m）

那么，对所有的点 x，若它在回路中出现了 k​ 次，那么它的度 d(x) 就是 2k，一定是一个偶数。

（充分性）我们任取一个度数不为 0 的点 v_1，从 v_1 出发经过与其相连的一条边 e_1 到达 v_2。

由于 v_2 的度数为偶数，且一定大于零（存在一条边 e_1 与之相连），因此 d(v_2)\geq 2，至少还有一条边 e_2 与之相连。

设 e_2 的另一个结点是 v_3，同上过程可以找到 v_4 与之相连，以此类推。

由于边数是有限的，因此这个过程一定会停止。停止的唯一可能是在 v_1 处（由于有 e_1​ 的存在），因此我们得到了一条回路 C。

删去这条回路和当前度数为 0​ 的点，我们得到一张新图 G^\prime​。

若 G 不是空图，那么类似对必要性的证明，我们可以得到 C 把每个点的度数都减去了一个非负偶数，因此 G^\prime​ 中每个结点的度数仍均为偶数。

由于 G 连通，因此 G^\prime 和回路中至少有一个交点 v_1^\prime。我们从 v_1^\prime 出发重复刚才的过程，得到一条新的回路 C^\prime，然后将 C^\prime 并入 C。

重复以上 找环-并入-删边 的过程，每次图的规模都会缩小，最终一定会得到一个空图。此时的回路便是包含了所有边的简单回路。

这便说明了 G​​​ 是欧拉图。证毕。

证明与上一性质类似，此处略去。

证明：（必要性）设 G​ 有欧拉路 v_1\ e_1\ v_2\ e_2\cdots\ v_{m-1}\ e_{m-1}\ v_m​。

我们发现，v_i(1<i<m)​​ 的出现一次便意味着存在与之相连的两条边 e_{i-1}​ 和 e_i​。

（特别地，v_1​ 的出现只有一条 e_1​，v_m​ 的出现只有一条 e_m​）

那么，对所有的点 x​，若它在通路中除了头尾以外的部分出现了 k​​ 次，而且它不是头也不是尾，那么它的度 d(x)​ 就是 2k​​，一定是一个偶数。

如果 x 是头或尾（依据欧拉路的定义 x 不可能既是头又是尾），那么他的度 d(x) 就是 2k+1，一定是一个奇数。这样的点有且仅有两个。

（充分性）由于 G​ 是连通图，所以一定存在一条连接这两个点的通路。

删去这条路，图中每个点的度数都是偶数。由上文第二条性质可知，每个连通块内都存在一条欧拉回路。

依次将其并入原有的通路，便得到了一条 G​ 中的欧拉路。这便说明了 G​ 是半欧拉图。 证毕。

证明与上一性质类似，此处略去。

证明：这其实是上面一些性质的扩展，而且我们由握手原理易知 k 一定是偶数。

证明的方法其实类似上面，此处不作展开。

具体地，对含有 k 个奇点的无向连通图，至少要加 \dfrac{k}{2} 条边；

对基图连通的有向图，至少要加的边数应为：

\dfrac{\sum\limits_{x=1}^n|d^+(x)-d^-(x)|}{2}

Fleury 算法

Fleuly 算法（弗洛莱算法）又称避桥法，是用于求欧拉路或欧拉回路的算法。

算法的主要流程是每次选择下一条边的过程中优先选择一条不为桥的边。（因为桥意味着走过去就再也走不回来了）

由于每次删一条边都要再跑一遍 Tarjan，因此复杂度是 \Theta(m(n+m))=\Theta(m^2) 的，效率较低。

可以依赖动态图进行一些优化，不过实践意义不大。

Hierholzer 算法

Hierholzer 算法又称逐步插入回路法，也是用于求欧拉路或欧拉回路的算法。

算法的流程与性质中的证明类似，具体地：

如果从路开始的话，就可以找到一条欧拉路。

但是，这样暴力实现的复杂度还是用于 \Theta(m^2)​​ 的，怎么进行优化呢？

我们发现，引起复杂度退化的一个主要原因是我们在访问到一个点时，会多次访问那些已经经过的边。

那么，我们只要在搜索时直接把经过的边删去即可做到 \Theta(n+m) 的复杂度。

（蓝书上的做法，一般不用）由于递归深度是 \Theta(m)​​​ 的，因此容易爆栈。可以考虑用一个栈模拟 DFS 的过程。

例题

这是无向图的板子。由于数据范围极小，因此可以采用邻接矩阵配合各种暴力。

还有，这题有重边。

void dfs(int x)
{
    for(int y=1;y<=n;y++)
        if(g[x][y]>=1) {
            g[x][y]--, g[y][x]--;
            dfs(y);
        }
    ans[++cnt]=x;
}

这是有向图的板子。由于邻接表的特性，倒着加边可以帮助我们取到字典序最小。

void dfs(int x)
{
    while(true)
    {
        int i=head[x];
        while(i&&vis[i]) i=Next[i];
        head[x]=i;
        if(i==0) break;
        vis[i]=true, dfs(ver[i]);
    }
    ans[++cnt]=x;
}

这题包着个欧拉回路的外皮，实际上没法用 Hierholzer 算法做，需要跑网络流。

这说明，Hierholzer 算法只能在单纯的有向图和无向图中使用，无法在混合图上跑。

我们发现只有初始权值和最终权值不同的需要一次修改，别的都不需要。

那么我们只需要把这些边全都加入图中，对每个连通块跑一遍 Hierholzer 即可。

输出有点麻烦，需要用一个栈去维护。具体看代码。

（LOJ 上的数据比这里强一万倍，那上面就是蓝书中提到的 DFS 爆栈题)

void solve(int rt)
{
    R[cur=1]=rt;
    while(cur) {
        int x=R[cur], i=head[x];
        while(i&&vis[i]) i=Next[i];
        head[x]=i;
        if(i==0) {
            if(ins[x]) {
                res.clear();
                res.push_back(x);
                while(st[top]!=x) {
                    res.push_back(st[top]);
                    ins[st[top]]=false, top--;
                }
                res.push_back(st[top]), ins[st[top]]=false, top--;
                v.push_back(res);
            }
            ins[x]=true, st[++top]=x;
            cur--; continue;
        }
        vis[i]=vis[i^1]=true;
        R[++cur]=ver[i];
    }
}

Code

这是一道经典题。

我们把每个 2^{k-1} 位的二进制作为一个结点，表示当前的末尾。然后对所有可能的转移连边。

比如，k=3 时，我们有结点 \texttt{00},\texttt{01},\texttt{10},\texttt{11}。

然后我们要求每种转移（就是代表着连续 k 位的二进制）出现且仅出现一次，这便是一个欧拉回路的问题。

void dfs(int x)
{
    if(g[0][x]!=-1) {
        int tmp=g[0][x];
        g[0][x]=-1;
        dfs(tmp);
    }
    if(g[1][x]!=-1) {
        int tmp=g[1][x];
        g[1][x]=-1;
        dfs(tmp);
    }
    ans[++cnt]=x;
}

int main()
{
    cin>>k;
    n=(1<<(k-1))-1;
    fo(i,0,n) fo(j,0,1) g[j][i]=((i<<1|j)&n);
    dfs(0);
    printf("%d ",(1<<k));
    int cur=k-2;
    fo(i,1,cur) putchar('0');
    while(cur<(1<<k)) {
        printf("%d",ans[cnt]&1);
        cnt--, cur++;
    }
    puts("");
    return 0;
}