欧拉路径

欧拉路径貌似很多博客都喜欢⽤⼀笔画来引⼊欧拉路径，但像您这样的强者时⽆需那些繁琐的东西，我们直接进⼊正题。

定义：图中经过所有边恰好⼀次的路径叫做欧拉路径。

如果起点和终点⼀样，那它就是欧拉回路。

判定：判定当前图中是否存在欧拉路径其实⽐寻找更⿇烦显然，欧拉回路也是欧拉路径，但为了⽅便区分，下⽂判定中的欧拉路径特指起点和终点不同。

判定⽅法：⾸先，当且仅当这张图将有向边视为⽆向边时联通。

1. 有向图欧拉路径：图中恰好存在⼀个点（起点）出度⽐⼊度多1，恰好⼀个点（终点）⼊度⽐出度多1，剩下所有点⼊度等于出度。

2. 有向图欧拉回路：图中所有点⼊度等于出度（任⼀点都可以做起点和终点）。

3. ⽆向图欧拉路径：图中恰好有两个点的度数为奇数（起点和终点），其他所有点的度数为偶数。

4. ⽆向图欧拉回路：图中所有点的度数都为偶数（任⼀点都可以做起点和终点）。

寻找：算法⼀：Fluery 算法。

时间复杂度O(m2)，不常⽤。

算法⼆：Hierholzer 算法。

时间复杂度O(m)，常⽤。

只写 Hierholzer 算法，做法⾮常简单。

1. 从起点开始dfs，标记选了的边不能重复选，这⾥⽤类似Dinic的当前弧优化。

2. 当前点不存在出边时回退，并将当前点⼊栈P。

3. 当dfs结束时倒序输出栈P中的节点即可。

算法导论上似乎有该算法证明。

例题：题⽬保证联通，所以直接判断⼊度和出度即可。

要求字典序最⼩，那么每次都要选能到达的最⼩的点。

可以将边离线下来按v从⼤到⼩排序，然后依次插⼊到链式前向星⾥，这样可以保证每次选到的都是最⼩的。

当前弧优化不加复杂度就假了。

code:#include<bits/stdc++.h>using namespace std;#define int long long#define in read()inline int read(){int p=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*f;}const int N=1e5+5;const int M=2e5+5;int n,m;struct edge{int v,nxt;}e[M];inline void insert(int u,int v){e[++en].v=v;e[en].nxt=head[u];head[u]=en;}struct QWQ{int u,v;}E[M];inline bool cmp(QWQ a,QWQ b){return a.v>b.v;}int p[M],pn;void dfs(int u){for(int i=head[u];i;i=head[u]){int v=e[i].v;head[u]=e[i].nxt;dfs(v);}p[++pn]=u;}int flagin,flagout,flag;int ind[N],outd[N];int S=1;signed main(){n=in,m=in;for(int i=1;i<=m;i++)E[i].u=in,E[i].v=in,outd[E[i].u]++,ind[E[i].v]++;sort(E+1,E+1+m,cmp);for(int i=1;i<=m;i++)insert(E[i].u,E[i].v);for(int i=1;i<=n;i++){if(ind[i]!=outd[i])flag++;if(ind[i]==outd[i]+1)flagout++;if(ind[i]+1==outd[i])flagin++,S=i;}if(flag==0||(flag==2&&flagout==1&&flagin==1)){dfs(S);for(int i=pn;i>=1;i--)cout<<p[i]<<' ';}else cout<<"No";return 0;}练习：将每个字母视为点，单词视为边，就和上⾯差不多了，注意欧拉路径的起始点。

第十三章欧拉图与哈密顿图欧拉图产生的背景就是前面介绍的七桥问题。

1736年，瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”。

欧拉在这篇论文中提出了一条简单准则，确定七桥问题是不能解的。

下面给出有关定义及定理。

定义2－1.1 设是无向连通图或有向弱连通图。

通过G的每条边一次且仅一次的路径(循环)称为G的欧拉路径(循环)。

具有欧拉循环的图称为欧拉图(规定平凡图是欧拉图)。

例2－1.1图2－1.1，有欧拉路径，，无欧拉路径和欧拉循环，，是欧拉图。

如何判断一个无向连通图或有向弱连通图是否为欧拉图？是否有欧拉路径？定理2－1.1 设是无向连通图，则1）当且仅当G的每个顶点都是偶顶点时，G才是欧拉图。

2）当且仅当G除两个顶点是奇顶点外，其他顶点都是偶顶点时，G才有欧拉路径。

证明 1)设是欧拉图：当时，G只含一个顶点，这个顶点显然是偶顶点。

当时，由所给条件知有G的欧拉循环，因为G的每条边在中出现且仅出现一次，故必通过G的每个顶点，且通过顶点时，此顶点的度就增加2，从而G的每个顶点都是偶顶点。

设G的每个顶点都是偶顶点：当时，G显然是欧拉图。

当时，由所给条件，G中必有循环，故也必有基本循环，从G中去掉各边后得生成子图，中每个顶点仍为偶顶点。

若是零图，则就是G的欧拉循环。

即G是欧拉图；若不是零图，即还有边，则必有与有一公共顶点的基本循环。

由于两条有一公共顶点的简单循环通过这个公共顶点可合并成一条简单循环，故和可合并成一条简单循环。

再从中去掉各边后得；最后得出一条通过G每条边的简单循环，这就是G的欧拉循环，故G是欧拉图。

2)设和是G有欧拉路径当且仅当有欧拉循环(即是欧拉图)，故由1)即得结论。

★用上面定理就能判断一个无向连通图是否为欧拉图，是否有欧拉路径。

例2－1.2 对于图2－1.2图2－1.2根据定理2－1.1中1)的结论知是欧拉图。

还可由其证明方法具体找出一条欧拉循环。

先将和合并成简单循环，再将和合并成简单循环，这就是G的一条欧拉循环。

七桥问题的通用规则七桥问题，也被称为哥尼斯堡七桥问题，是一道著名的数学难题。

该问题最早由瑞士数学家欧拉在18世纪提出，并成为图论的开端之一。

七桥问题描述了一个位于哥尼斯堡的岛屿上的一系列桥梁以及这些桥梁连接的方式。

解决这个问题需要运用到图论中的一些基本原理和规则。

在七桥问题中，岛屿上有一些桥梁，而我们的目标是从一个起点开始，遍历每一座桥且仅经过一次，最终回到起点。

然而，这个问题的挑战在于，岛屿上的桥梁连接方式并不是一个简单的环，而是一个复杂的图。

因此，我们需要运用一些通用规则来解决这个问题。

首先，我们需要了解一些图论的基本概念。

在图论中，桥梁被表示为图中的边，而岛屿则被表示为图中的顶点。

七桥问题中的桥梁连接方式可以被看作是一个图，我们需要将其转化为数学模型，以便进行分析和解决。

在这个过程中，我们可以使用图的邻接矩阵或邻接表来表示桥梁和岛屿之间的连接关系。

接下来，我们可以运用欧拉路径的概念来解决七桥问题。

欧拉路径是指一条路径，该路径恰好经过图中的每一条边一次。

对于七桥问题，我们的目标是找到一条欧拉路径，使得我们可以从一个起点开始，遍历每一座桥且仅经过一次，最终回到起点。

根据欧拉路径的特性，我们可以得出以下的通用规则。

首先，欧拉路径存在的条件是：图中所有顶点的度数为偶数，或者恰好有两个顶点的度数为奇数，其余顶点的度数为偶数。

度数是指与顶点相连的边的数量。

因此，在七桥问题中，如果岛屿上的每一座桥的连接点的度数都是偶数，或者有且只有两座桥的连接点的度数为奇数，我们就可以找到一条欧拉路径。

其次，如果图中存在度数为奇数的顶点，那么我们的欧拉路径的起点和终点一定是这些顶点中的一个。

因为每条桥梁的连接点度数为偶数，除了起点和终点外，其余所有顶点的度数一定是偶数，无法成为欧拉路径的起点和终点。

因此，在七桥问题中，如果岛屿上存在两座或更多的桥梁连接点的度数为奇数，我们就可以从其中一个度数为奇数的连接点出发，找到一条欧拉路径。

欧拉回路构造算法全文共四篇示例，供读者参考第一篇示例：欧拉回路是图论中的一个重要概念，在一幅图中指的是一条包含图中每一条边且经过每一条边仅一次的闭合路径。

欧拉回路构造算法是指寻找一条欧拉回路的方法，即将给定的图转化为满足欧拉回路性质的路径。

欧拉回路构造算法有多种，其中最为经典和常用的算法是Fleury 算法和Hierholzer算法。

Fleury算法是一种基于贪心思想的算法，其基本思路是每次选择一条不是桥的边，通过DFS搜索来构造欧拉回路。

具体步骤如下：1. 从图中任选一个顶点作为起点。

2. 找到可以走的一条不是桥的边，并走向该边所连接的顶点。

3. 如果该边是割边，则在走完该边后，必须选择一条不是割边的边继续前进。

4. 重复步骤2和步骤3，直到不能走为止。

Fleury算法的时间复杂度为O(E^2)，其中E为图中的边数。

Hierholzer算法是另一种求解欧拉回路的经典算法，其基本思想是通过遍历所有的边来构造欧拉回路。

具体步骤如下：1. 从图中任意一个顶点开始，选择一条边进行遍历。

2. 如果走到某个节点时无法继续行走，则回退到之前分叉点重新选择一条边继续遍历。

3. 直到遍历完所有的边，形成一个闭合回路即为欧拉回路。

欧拉回路构造算法的应用十分广泛，例如在网络设计、图像处理、数据压缩等领域都有着重要的作用。

通过欧拉回路构造算法，我们可以快速有效地找到一条经过所有边的闭合路径，从而解决一系列实际问题。

欧拉回路构造算法是解决图论中欧拉回路问题的重要工具。

不同的算法适用于不同的情况，可以根据具体问题的要求选择合适的算法。

通过学习和了解欧拉回路构造算法，我们可以更好地运用图论知识解决实际问题，提高问题解决的效率和准确性。

希望本文对读者有所帮助，欢迎大家进一步深入学习和探讨。

第二篇示例：欧拉回路构造算法是图论中一种重要的算法，用于寻找图中存在的欧拉回路。

欧拉回路是指一条包含所有边且不重复经过任何边的闭合路径。

在很多实际应用中，欧拉回路是一个非常有用的概念，比如在电子电路的布线设计、网络路由、以及城市旅行等领域都有很多应用。

.欧拉路径（欧拉回路）相关定义：若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。

若该路径是一个圈，则称为欧拉回路。

具有欧拉回路的图称为欧拉图（简称E图）。

具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

判断图是否为欧拉图：无向图为欧拉图，当且仅当为连通图且所有顶点的度为偶数。

无向图为半欧拉图，当且仅当为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。

有向图为欧拉图，当且仅当其基图（忽略有向图所有边的方向，得到的无向图称为该有向图的基图）连通，且所有顶点的入度等于出度。

有向图为半欧拉图，当且仅当其基图连通，且有且仅有一个顶点的入度比出度大1、有且仅有一个顶点的入度比出度小1，其它所有顶点的入度等于出度。

欧拉回路（路径）的算法：有向图：第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。

第二步，如果存在欧拉路径，从入度比出度小1的点开始BFS；如果存在欧拉回路，从任意一点开始。

第三步，设DFS到点u，遍历u的出边e(u,v)。

第四步，如果e未被标记，转到第五步，否则转到第三步。

第五步，标记e(u,v)，DFS点v。

第六步，边e(u,v)入栈。

第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。

无向图：第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。

第二步，如果存在欧拉路径，从度为奇数的点开始BFS；如果存在欧拉回路，从任意一点开始。

第三步，设DFS到点u，遍历u的出边e(u,v)。

第四步，如果e未被标记，转到第五步，否则转到第三步。

第五步，标记e(u,v)及它的反向边，DFS点v。

第六步，边e(u,v)入栈。

第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。

'.。