欧拉回路与欧拉通路

定义、性质及结论

一些定义：

回路：从一个点出发又回到这个点的路径。
通路：从一个点出发到任意一个点结束的路径。
有向图强联通：所有点两两可达
有向图弱联通：把所有有向边变成无向后所有点都属于一个联通快
欧拉回路：通过图中每条边恰好一次的回路。
欧拉通路：通过图中每条边恰好一次的通路。
欧拉图：具有欧拉回路的图。
半欧拉图：具有欧拉通路但不具有欧拉回路的图。

一些关系：

欧拉回路是欧拉通路的一种。
欧拉图不属于半欧拉图。

一些性质：

欧拉图中所有顶点的度数都是偶数。
一个欧拉图有若干个环组成，也可以说他是若干个环的并。

证明：你若是想要有回路，那么必须能从起点走出去再走回来，那么这必定是一个环，路径上想要能形成回路必定也由环组成，那样才能保证按照原来的一条主线形成回路。或者反证法，图上不是环便是链，链你能形成回路吗？
若一个图是欧拉图，则这个图中的每条边都被包含在奇数个环内。

证明：这是必然的，思考反证法——如果一条边被包含在偶数个环内，那么这条边的两个端点必定度数都是奇数。

判别方法：

无向图是欧拉图当且仅当：
- 非零度顶点是连通的。
  
  证明：那样才存在欧拉回路，不然边之间都不是两两可达。
- 顶点的度数都是偶数。
  
  证明：既然是由环组成，那么每个环中的边对环中每个节点的度的贡献必定是偶数，所有得证。
  
  还有一种构造法证明，因为很简单这里就简单讲解一下：就是我们先从起点开始找到一条回路，然后对于剩下的必定还是以很多环的形式存在，因为这个回路只会将回路上的节点未访问过的连接边数减 \(2\) ，而且我们还能得到剩下的有连边的集合必定和当前的回路上的节点有交集，不然他们就不满足是一个联通块。那么我么可以对子图进行相同操作即可形成欧拉回路。
无向图是半欧拉图当且仅当：
- 非零度顶点是连通的。
  
  证明：那样才存在欧拉回路，不然边之间都不是两两可达。
- 恰有 \(2\) 个奇度顶点。
  
  证明：我们不难发现，我们假设把两个奇度数节点再连一条边，就能形成一个欧拉回路，那么我们让这条边最后遍历，然后删去它，那么就是一条欧拉通路。而至于不能是 \(0\) 个奇度节点是因为如果是 \(0\) 个奇度节点的话就是欧拉回路，而半欧拉图不允许是欧拉回路。
  
  那么这里延伸出去可得：若图中存在欧拉通路那么要恰好有 \(0\) 或 \(2\) 个奇度节点。
有向图是欧拉图当且仅当：
- 非零度顶点是强连通的。
  
  证明：不难想象，既然是由若干环组成，那么所有非零度节点一定是能两两到达，因为一个环可以走到所有和他相邻的环上，那么以此走遍所有环。
- 每个顶点的入度和出度相等。
  
  证明：同样可以发现既然是环组成，那肯定会把环上节点的入读和出度每个都加 \(1\) 。
有向图是半欧拉图当且仅当：
- 非零度顶点是弱连通的。
  
  证明：不然就不可能存在，因为他们间就不存在可达的路径。
- 至多一个顶点的出度与入度之差为 \(1\) 。
- 最多一个顶点的入度与出度之差为 \(1\) 。
  
  证明：此条和前一条一起来看。我们依旧是连一条边，那样就变成欧拉图了。
- 剩余顶点的入度和出度相等。
  
  证明：不然连边后就不能形成欧拉图。

求欧拉回路

「一本通 3.7 例 1」欧拉回路。

以下是以无向图的角度考虑的，有向图不单独写了，同理。

可行解

自然是先判定存不存在。

我们先考虑一种可行解，就是我们从一个任意节点开始，然后递归所有没有遍历过得边所指向的点，每个点所指出去的所有边都遍历完时（或者说是回溯时）记录编号。

证明：我们考虑是图是环的并，那么我们只需要从任意环开始，路径上以这个环为主线，中间可能会有其它环，但是我们可以递归下去，依旧又回到当前点，然后按照主线往后递归，最后回退，不难发现必定会一直这样遍历到终点，然后回溯时记录还能避免中间主线的点上有环没有遍历到，所说义必定没有问题。

最小解

如题，要求字典序最小。我们对每个点所连向的所有点按字典序从小到大排个序，然后直接按顺序遍历所到达的节点，回溯时记录节点编号。对于起点，我们选编号最小的。而最后因为序列是反着记录的，那么我们翻转序列再输出。

证明：自己当时想可能有一种情况，就是一个节点 \(u\) 有多条连出去的边，先遍历编号最小的那个点 \(v\) ，那么我们可能会继续递归，然后回溯过来，发现当前点还有边没有走过，那个边连向的点是 \(x\) ，那样编号肯定会比先走 \(x\) 再走 \(v\) 大（因为是回溯时记录，那么我们可以让 \(v\) 最后走，那么回他的编号就越大，最后翻转序列时他就越小），所以可不可能有时候先走编号大的边，再走编号小的呢？实则不然，我们考虑 \(v\) 回溯到 \(u\) 时，还存在一个没遍历到过的点 \(x\) ，就证明 \(v\) 和 \(x\) 处于同一个环上，而 \(x\) 不处于这个环上，那么假设先遍历 \(x\) ，那么他必定能回到 \(u\) ，然后递归 \(v\) ，那么 \(v\) 还是一样的顺序回溯的，所以这种方法没有更优，得证。

#include <bits/stdc++.h>
#define L(i, a, b) for(int i = a; i <= b; i++)
#define R(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int N = 100010;
struct Edge{
	int v, i, t;
	friend bool operator < (const Edge a,const Edge b){
		return a.v < b.v;
	}
};
int t, n, m, s, tot;
int d[N], h[N], vis[N << 2], ans[N << 1];
vector<Edge>g[N];
void Dfs(int u){
	L(i, h[u], g[u].size() - 1){
		if(i < h[u]) i = h[u];
		if(i >= g[u].size()) break;
		h[u] = i + 1;
		int v = g[u][i].v, id = g[u][i].i << 1 | g[u][i].t;
		if(vis[id ^ 1]) continue;
		vis[id] = 1;
		Dfs(v);
		ans[++tot] = g[u][i].t? -g[u][i].i : g[u][i].i;
	}
}
int main(){
	scanf("%d%d%d", &t, &n, &m);
	L(i, 1, m){
		int u, v;
		scanf("%d%d", &u, &v);
		s = u;
		if(t == 1){
			g[u].push_back({v, i, 0});
			g[v].push_back({u, i, 1});
			d[u]++, d[v]++;
		}
		else{
			g[u].push_back({v, i, 0});
			d[u]++, d[v]--;
		}
	}
	L(i, 1, n){
		if(t == 1 && (d[i] & 1) || t == 2 && d[i]){
			puts("NO");
			return 0;
		}
	}
	Dfs(s);
	if(tot != m){
		puts("NO");
		return 0;
	}
	puts("YES");
	reverse(ans + 1, ans + tot + 1);
	L(i, 1, m)
		printf("%d ",ans[i]);
	return 0;
}

求欧拉通路

其实非常简单，和求欧拉回路一样的思路，就是判断是否存在的时候有差别。

P7771 【模板】欧拉路径。

#include <bits/stdc++.h>
#define L(i, a, b) for(int i = a; i <= b; i++)
#define R(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int N = 100010;
int n, m, tot, s, in[N], out[N], h[N], ans[N << 1];
vector<int>g[N], ss;
void Dfs(int u){
	L(i, h[u], g[u].size() - 1){
		if(i < h[u]) i = h[u];
		if(i >= g[u].size()) break;
		h[u] = i + 1;
		int v = g[u][i];
		Dfs(v);
	}
	ans[++tot] = u;
}
int main(){
	scanf("%d%d", &n, &m);
	L(i, 1, m){
		int u, v;
		scanf("%d%d", &u, &v);
		ss.push_back(u), ss.push_back(v);
		g[u].push_back(v);
		out[u]++, in[v]++;
	}
	L(i, 1, n){
		if(abs(in[i] - out[i]) > 1){
			puts("No");
			return 0;
		}
		if(in[i] < out[i]){
			if(s){
				puts("No");
				return 0;
			}
			s = i;
		}
		sort(g[i].begin(), g[i].end());
	}
	if(!m){return 0;}
	sort(ss.begin(), ss.end());
	Dfs(s? s : ss[0]);
	if(tot != m + 1){
		puts("No");
		return 0;
	}
	reverse(ans + 1, ans + tot + 1);
	L(i, 1, tot)
		printf("%d ",ans[i]);
	return 0;
}

常见的应用

很多时候是需要模型转换发现是个可以用欧拉通路或欧拉回路做的东西，比如说一条无向边走两次——拆成两条有向边再求解，再比如说有时候我们要会“抽象大法”，比如说有道题目是把木条首尾相接，然后每个木条首尾都有单词，要求所有连接处的单词都相等的方案。那么我们要能把连接处抽象成点，木条抽象成边才能做。基础的欧拉回路一般比较套路，很多时候和其它算法结合起来用。