欧拉回路
几个定义
性质与定理
二、性质与定理
在以下讨论中，假设图 G不存在孤立点（度为0）；否则，先将所有孤立点从图中删除。 显然，这样做并不会影响图G中欧拉回路的存在性。
我们经常需要判定一个图是否为欧拉图（或半欧拉图），并且找出一条欧拉回路（或欧 拉路径）。对于无向图有如下结论：
定理1
无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。
充分性
假设图G中不存在回路，而G是连通图，故 一定是G树，那么有 |E|=|V|−1 由于图G所有顶点的度为偶数而且不含孤立点，那么图G的每一个顶点的度至少为2。由握手定理，有 |E|=12∑v∈Vd(v)≥V ，与假设相矛盾。故图G中一定存在回路。设图G中边数最多的一条简单回路边没有重复出现为 C={
e1=(v0,v1),e2=(v1,v2),...,em=(vm−1,v0)}
下面证明回路C是图G的欧拉回路
假设C不是欧拉回路,则C中至少含有一个点 vk ,该点的度大于C经过该点的关联边的次数。令 v′0=vk ，从 v′0 出发有一条不属于C的边 e′1=(v′0,v′1) 。若 v′0=v′1 ,则 v′0 自身成环，可以将其加入C中形成一个更大的回路。否则若 v′0≠v′1 ,由于 v′1 的度为偶数,而C中经过 v′1 的关联边的次数也是偶数,所以必然存在一条不属于C的边 e′2=(v′1,v′2) 依此类推，存在不属于C的边 e′3=(v′2,v′3),...,e′k=(v′k−1,v′0) .
故 C′={
e′1,e′2,...,e′k} 是一条新的回路，将其加入C中可以形成一个更大的回路。这与C是图G的最大回路相矛盾，故C是图G的欧拉回路。
推论1
无向图G为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外， 其它所有顶点的度为偶数。
证明：将两个度为奇数的顶点连接，由定理一得该图为欧拉图，故去掉环上一边为半欧拉图。
定理2
有向图G为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出度。
推论2
有向图G为半欧拉图，当且仅当G的基图连通，且存在顶点u的入度比出度大1 、v的入度比出度小 1，其它所有顶点的入度等于出度。
证明同定理1相似。
性质1
设C是欧拉图G中的一个简单回路，将C中的边从图G中删去得到一个新的图G ′ ,则 G ′ 的每一个极大连通子图都有一条欧拉回路。
性质2
算法主体
由此可以推出欧拉图的算法：
例题
uoj117：求给定图的欧拉回路
对于第三点可以做如下优化：
for(int &e=last[now];e;e=before[e])通过改变last来删除边，保证了 O(E) 的时间复杂度。
- Code
#include
1<<
" "; }
else
puts(
"NO"); }
return; }
inline
void dfs1(
int now) {
for(
int &e=last[now];e;e=before[e]) {
if(vis[e])
continue;
int t=e; cnt++; vis[e]=
1; vis[e^
1]=
1; dfs1(to[e]); st[++top]=t; } }
inline
bool check1() {
for(
int i=
1;i<=maxind;i++)
if(in[i]%
2)
return
false;
return
true; }
inline
void solve1() { n=read(),m=read();
for(
int i=
1;i<=m;i++) {
int x=read(),y=read(); add(x,y);add(y,x); in[x]++;in[y]++; maxind=max(maxind,max(x,y)); }
if(!check1())
puts(
"NO");
else { dfs1(maxind);
if(cnt==m) {
puts(
"YES");
for(
int i=top;i>=
1;i--) {
if(st[i]%
2)
putchar(
'-');
cout<<(st[i]/
2)<<
" "; } }
else
puts(
"NO"); }
return; }
int main() {
int t=read();
if(t==
1)solve1();
else solve2(); }
poj1041：求字典序最小的欧拉回路
这道题只说一下怎么求字典序最小。
对于给定的边先按照字母排序，然后从大到小加边，那么访问一个点的边就是从小到大遍历。
- Code（代码写得很随意，仅供参考）
#include
" ";
cout<
else
puts(
"Round trip does not exist."); } } }
poj1386:Play on Words
- 题意：
给你n个单词，要求这些单词相连，要求是前面的字母的尾字母和后面单词的头字母相同，问你这n个单词能不能全部连起来，可以连成一条链或者连成一个环。
不用说，套板。
#include
poj2230:求无向图欧拉图（要求每条边走两遍且方向不同）
同样板题，将无向图的边转化为两条有向边，就变成了求有向边欧拉图。
poj2513字符串的欧拉图
其实一样，注意用trie树
poj2337字典序。。
还是排序后加边。。。
#include
inline
void add(
int x,
int y) { ++ecnt; before[ecnt]=last[x]; last[x]=ecnt; to[ecnt]=y; }
inline
int getf(
int x) {
if(x==fa[x])
return x;
return fa[x]=getf(fa[x]); }
inline
void dfs(
int now) {
for(
int &e=last[now];e;e=before[e]) {
if(vis[e])
continue; vis[e]=
1;
int t=e; dfs(to[e]); st[++top]=t; } }
int bg1,ed1;
inline
bool check() {
int t=getf(bg);
for(
int i=
1;i<=
26;i++) {
if(!fa[i])
continue; bg=min(bg,i);
if(getf(i)!=t)
return
false; }
for(
int i=
1;i<=
26;i++) {
if(in[i]==out[i])
continue;
else
if(in[i]==out[i]-
1) {
if(bg1)
return
false; bg1=i; }
else
if(in[i]==out[i]+
1) {
if(ed1)
return
false; ed1=i; }
else
return
false; }
return
true; }
int main() {
scanf(
"%d",&T);
while(T--) { ecnt=
1;bg=
0;top=
0;bg1=ed1=
0;
memset(last,
0,
sizeof(last));
memset(fa,
0,
sizeof(fa));
memset(in,
0,
sizeof(in));
memset(out,
0,
sizeof(out));
memset(vis,
0,
sizeof(vis));
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++) {
cin>>ch[i]; q[i].s=ch[i]; q[i].id=i; } sort(q+
1,q+n+
1);
for(
int i=n;i>=
1;i--) {
int x=q[i].s[
0]-
'a'+
1,y=q[i].s[q[i].s.size()-
1]-
'a'+
1;
if(!fa[x])fa[x]=x;
if(!fa[y])fa[y]=y;
if(!bg)bg=x; fa[getf(x)]=getf(y); out[x]++;in[y]++; add(x,y); id[ecnt]=q[i].id; }
if(check()) {
if(bg1)dfs(bg1);
else dfs(bg);
for(
int i=top;i>=
1;i--) {
cout<
if(i!=
1)
cout<<
"."; }
cout<
else
puts(
"*"); } }
poj1637:Sightseeing tour求混合图欧拉回路
这个有点难，我的另一篇博客写了题解：poj1637:Sightseeing tour(混合图欧拉回路，网络流)
HDU 2894,Poj1392，
(占坑，写后来写题解)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/207242.html原文链接：https://javaforall.net
