526互联

学习笔记：欧拉图 & 欧拉路

发布时间 2023-10-28 16:05:10作者: tsqtsqtsq

欧拉图 & 欧拉路

定义

图中经过所有边恰好一次的路径叫欧拉路径（也就是一笔画）。如果此路径的起点和终点相同，则称其为一条欧拉回路。

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

性质

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

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

判别法

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

当然，一副图有欧拉路径，还必须满足将它的有向边视为无向边后它是连通的（不考虑度为 \(0\) 的孤立点），连通性的判断我们可以使用并查集或 dfs 等。

存在欧拉回路（即满足存在欧拉回路的条件），也一定存在欧拉路径。

求欧拉路径或欧拉回路

寻找欧拉路径（默认存在）：

首先根据题意以及判定先确定起点 \(S\)。
从起点 \(S\) 开始 dfs 。

dfs 伪代码如下：

void dfs(int now){
    枚举 now 的出边。
        如果该边还未被访问
            标记为已访问
            dfs(该边连向的另一个点)
    now入栈
}

最后倒序输出栈内的所有节点即可。

感性理解倒序输出的原因：如果是欧拉回路，那么遍历到哪，输出到哪也是对的，因为不管怎么走都会绕某个环走回起点，所以不到最后不会出栈，然而欧拉路径会出现边都被走过了，走不回起点，最后会停留在终点，遇到这种情况这种路径会最先出栈，于是只要把这个路径先走了，前面就和欧拉回路一样随便走就行，不会出栈，于是倒序输出就是对的。

例题

洛谷 P7771 【模板】欧拉路径

题目描述

求有向图字典序最小的欧拉路径。

输入格式

第一行两个整数 \(n,m\) 表示有向图的点数和边数。

接下来 \(m\) 行每行两个整数 \(u,v\) 表示存在一条 \(u\to v\) 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 \(m+1\) 个数字，表示字典序最小的欧拉路径。

题意：给定 \(n\) 个点，\(m\) 条边，求这副有向图字典序最小的欧拉路径。

思路：

本题需要判断并找出有向图的欧拉路径。

由于本题保证“将有向边视为无向边后图连通”，所以判定时不用判断连通性。

还有一点要注意的是本题需要按照字典序输出。

这一点如何解决呢？

法一：

直接使用数组存邻接矩阵，枚举点 \(x\) 出边时，直接枚举编号从 \(1\) 到 \(n\) 的点 \(y\)，再判断 \(x\)，\(y\) 之间是否有未访问边，这样就解决了字典序的问题。

dfs 代码（对应伪代码）:

void dfs(int now){
  for(int i = 1 ; i <= n ; i ++)
      if(G[u][i] > 0)
          G[u][i]--,dfs(i);
  st.push(now);
}

但是这样的做法时间复杂度为 \(O(n^2)\)，显然会超时。

法二：

既然邻接矩阵不行，那我们就用时间复杂度更优的邻接表，将 \(now\) 的所有出边排序即可。链式前向星对于排序出边的操作有些困难，而 vector 则容易得多，所以选用 vector。

sort 代码：

for(int i = 1 ; i <= n ; i ++)sort(G[i].begin(), G[i].end());

dfs 代码：

void dfs(int now){
  for(int i = a[now] ; i < g[now].size() ; i = a[now])
  	a[now] = i + 1,dfs(g[now][i]);
  s.push(now);
}
//其中 a[now] 表示 G[now][1,2……,a[now] - 1] 都已经被标记访问过，下一次要从 G[now][a[now]] 开始访问。

dfs 时间复杂度：\(O(n)\)。

sort 时间复杂度：\(O(m\log m)\)。

总时间复杂度：\(O(n+m\log m)\)。

足以 AC 本题。

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#define MAXN 100005
using namespace std;
int n, m, u, v;
int cnt1, cnt2, tmp = 1;
int a[MAXN], rd[MAXN], cd[MAXN];
bool flag = true;
stack <int> s;
vector <int> g[MAXN];
int read(){
    int t = 1, x = 0;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')t = -1;ch = getchar();}
    while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * t;
}
void write(int x){
    if(x < 0){putchar('-');x = -x;}
    if(x >= 10)write(x / 10);
    putchar(x % 10 ^ 48);
}
void dfs(int now){
	for(int i = a[now] ; i < g[now].size() ; i = a[now])
		a[now] = i + 1,dfs(g[now][i]);
	s.push(now);
}
int main(){
	n = read();m = read();
    for(int i = 1 ; i <= m ; i ++){
        u = read();v = read();
        g[u].push_back(v);
        cd[u]++;rd[v]++;
    }
    for(int i = 1 ; i <= n ; i ++)sort(g[i].begin(), g[i].end());
    for(int i = 1 ; i <= n ; i ++){
        if(cd[i] != rd[i])flag = false;
        if(rd[i] - cd[i] == 1)cnt1++;
        if(cd[i] - rd[i] == 1)
            cnt2++,tmp = i;
    }
    if(flag == false)
        if(cnt1 != cnt2 || cnt1 != 1){
            puts("No");return 0;
    }
    dfs(tmp);
    while(!s.empty())
        write(s.top()),putchar(' '),s.pop();
    return 0;
}