1.定义：

奇点 度数为奇数的点

欧拉路径 一笔画路径

欧拉回路 一笔画且能回到起点的路径

欧拉图 图$G$能一笔画而且可以回到起点

半欧拉图 图$G$能一笔画但路径的起点和终点不相同

哈密尔顿环 指不重复走过所有的点，最后还能回到起点的回路

2.欧拉图/半欧拉图的判定：

• 无向图的判定：

欧拉图 $G$联通且所有顶点的度均为偶数

半欧拉图 $G$联通且有两个顶点的度为奇数，其他为偶数

• 有向图的判定：

欧拉图 $G$的基图联通且所有顶点的入度=出度

半欧拉图 $G$的基图联通且存在顶点$u$的入度比出度大$1$，$v$的入度比出度小$1$，其他所有顶点的入度$=$出度

（基图：忽略有向图所有边的方向得到的无向图）

3.欧拉路径/欧拉回路的查找算法：

1）暴力算法

深度优先遍历，用邻接矩阵表示图，当顶点数和边数都很小的话可行。

若寻找欧拉回路，从任意一个点开始遍历；若寻找欧拉路径 ，则从一个奇点开始$dfs$。

$dfs$时，如果所有边都被遍历，就返回路径；若否则枚举与当前节点连接的未标记的边遍历。

#include<bits/stdc++.h>
using namespace std;
const int N=25; 
int n,m;
bool vis[N][N];
int path[N<<1];
void dfs(int pos,int way){
	if(way==m+2){
		for(int i=1;i<way;i++) printf("%d ",path[i]);
		printf("\n");
		return ;
	}
	for(int i=1;i<=n;i++){
		if(i==pos) continue;
		if((!vis[pos][i])||(!vis[i][pos])) continue;
		vis[pos][i]=false;vis[i][pos]=false;
		path[way]=i;
		dfs(i,way+1);
		vis[pos][i]=true;vis[i][pos]=true;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	if(n+1>m) return 0;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		vis[u][v]=true;
		vis[v][u]=true;
	}
	path[1]=1;
	dfs(1,2);
	return 0;
} 

2）Fleury算法 $O(m+n)$

本质思路是：考虑到欧拉环的两个性质（见“5.欧拉图的性质”），我们可以只遍历一遍就可以找到一个欧拉环。首先随便找一个环，显然它的欧拉路径可求。再在剩下的图中找欧拉路径，这样递归下去，最后一个一个合并，得到最终的欧拉路径。

用两个栈维护答案，一个是搜索栈，表示搜索顺序；一个是结果栈，用来记录结果。

这里我们考虑找一条欧拉路径。从一个奇点开始搜索，先把这个点压入栈，在类似dfs搜索与这个点相连的点并删去连接边，直到搜到一个已经没有出度的点为止。此时不断弹出栈，将弹出的点加入结果栈中，直到有一个点还有出度。此时继续搜索即可。

最后，结果栈中的数，就是一条欧拉路径遍历的点。

下面的代码是用邻接表建边，如果要找出字典序最小的一组遍历，要用邻接矩阵。

这种维护方法，本质上和思路一样。直到有一个点没有出度，就是找到了一个环。不断出栈是为了找到这个环和其他边的连接点。

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m;
struct Edge{
	int u,v;
	int next;
	bool vis;
}edge[N<<1];
int head[N],tot=0;
int outd[N];
int conn[N<<1];
void add_edge(int u,int v){
	outd[u]++;tot++;
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].next=head[u];
	edge[tot].vis=false;
	head[u]=tot;
}
stack<int>q,ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edge(u,v);add_edge(v,u);
		conn[tot]=tot-1;conn[tot-1]=tot;
	}
	for(int i=1;i<=n;i++){
		if(outd[i]%2==1){
			q.push(i);
			break;
		}
	}
	while(!q.empty()){
		int t=q.top();q.pop();
		if(outd[t]==0) ans.push(t);
		else{
			q.push(t);
			for(int i=head[t];i;i=edge[i].next){
				if(edge[i].vis==true||edge[conn[i]].vis==true) continue;
				q.push(edge[i].v);
				outd[t]--;outd[edge[i].v]--;
				edge[i].vis=true;edge[conn[i]].vis=true;
				break;
			}
		}
	}
	while(!ans.empty()){
		printf("%d ",ans.top());ans.pop();
	}
	return 0;
}

4.哈密尔顿环的查找算法：

暴力算法:

利用深度优先搜索（$dfs$）即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=25;
bool vis[N];
bool w[N][N];
int tot=0;
int path[N];
void dfs(int pos,int way){
	if(way==n+1&&pos==1){
		tot++;
		for(int i=1;i<way;i++) printf("%d ",path[i]);
		printf("1\n");
		return ;
	}
	path[way]=pos;
	for(int i=1;i<=n;i++){
		if(i==pos) continue;
		if(!w[pos][i]) continue;
		if(vis[i]) continue;
		vis[i]=true;
		dfs(i,way+1);
		vis[i]=false;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		w[u][v]=true;
		w[v][u]=true;
	}
	dfs(1,1);
	printf("%d\n",tot);
	return 0;
}

注意：查找哈密尔顿环没有更好的算法，因为此问题被证明为NPC问题。

5.欧拉图的性质：

1)设$C$是欧拉图$G$的一个简单回路,将$C$中的边从$G$中删去得到$G'$,则$G'$的每一个极大连通子图都有一条欧拉回路。

2)设$C_1,C_2$是$G$的两个没有公共边但至少有一个公共顶点的简单回路,则$C_1,C_2$可以合并成简单回路$C'$。