DDOSvoid's Blog

欧拉回路

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

简介

定义

欧拉通路：通过图中每条边且只通过一次，并且经过每一顶点的通路

欧拉回路：通过图中每条边且只通过一次，并且经过每一顶点的回路

有向图的基图：忽略所有边的方向，得到的无向图称为该有向图的基图

一条回路也可视为一条通路

定理及推论

无向图定理

无向图 $G$ 存在欧拉通路的充要条件：

$G$ 是连通图，并且 $G$ 仅有两个奇度节点或者无奇度节点

推论：

  1. 当 $G$ 有且仅有 $2$ 个奇度节点的时候，$G$ 的欧拉通路必以这两个节点为端点
  2. 当 $G$ 是无奇度节点连通图时，$G$ 必有欧拉回路

有向图定理

有向图 $D$ 存在欧拉通路的充要条件是：

$D$ 的基图连通，并且所有顶点的出入度相等；

或者除两个顶点外，其余顶点的入度和出度相等，而这两个顶点中，一个顶点的出度与入度之差为 1，另一个顶点的出度与入度之差为 1

推论：

  1. $D$ 中只有两点的出入度不同且一个点的出度与入度的差为 $1$，另一点的入度与出度的差为 $1$，$D$ 有欧拉通路且以这两点为顶点
  2. 当所有点的出入度都相等时，$D$ 中一定存在欧拉回路

求解欧拉回路

$Hierholzer$ 算法

需要注意的是这个算法当且仅当存在欧拉回路才是正确的，所以要提前判是否存在欧拉回路

1
2
3
4
5
6
7
void dfs(int u) {
    for (int &i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; bool &ext = e[i].ext, &Ext = e[i ^ 1].ext;
        if (ext) continue; ext = Ext = 1; dfs(v); // 在这里记录边
    }
    // 在这里记录点
}

拓展

应用

给边定向

  1. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，现在需要给每条边定向，使得尽量多的点满足入度等于出度

    $n\le 200$

    简要题解：容易发现答案最大为度数为偶数的点的个数，我们首先猜测能否构造出这样的解

    考虑欧拉回路，注意到有度数为奇数的点，所以我们不能直接跑欧拉回路，但同时我们注意到度数为奇数的点的个数一定有偶数个，所以我们新建一个点，将其与所有度数为奇数的点相连，然后我们跑欧拉回路就行了

    CF 723E One-Way Reform

  2. 简要题意：给定 $n$ 个数列，第 $i$ 个数列的长度为 $m_i$，现在要求将这 $\sum_{i=1}^nm_i$ 个数划分进两个可重集合中，要求这两个可重集合完全相同，每个数只能进一个集合，同时必须保证每个数列都有恰好一半的数进入 $A$ 集合，另一半进入 $B$ 集合

    $n\le 10^5,\sum_{i=1}^nm_i\le 2\times 10^5$

    简要题解：我们考虑将数字和数组都看成点，如果一个 $x$ 在 $i$ 数列中出现了 $k$，那么就连 $k$ 条 $x$ 到 $i$ 的双向边，然后我们跑欧拉回路，我们将入边和出边看成左右集合，因为每个点的入度都等于出度，所以两个条件都能得到满足

    CF 1634E Fair Share

  3. 简要题意：现在有 $n$ 个点 $(x_i,y_i)$，要求将每个点染成红色或者蓝色，且横坐标相同的点中蓝色和红色点的数量相差不超过 $1$，纵坐标同理

    $n\le 2\times 10^5$

    简要题解：我们考虑将横坐标和纵坐标看成图中的点，如果有一个点 $(x,y)$，我们就连一条 $x$ 到 $y$ 的无向边

    现在我们需要染色，这相当于给无向边定向，且定向之后需要保证每个点的入度和出度的差的绝对值不超过 $1$，如果要求入度等于出度的话，我们容易想到欧拉回路，但现在是要求入度和出度的绝对值不超过 $1$

    我们考虑将其转化为入度等于出度的情况，注意到图中度数为奇数的点一定有偶数个，那么我们新建一个点，将所有奇数点连向这个点，然后再跑欧拉回路就行了

    CF 547D Mike and Fish