博客

欧拉道路和欧拉回路

  • Post author:
  • Post category:其他




欧拉通路

: 通过图中每条边且只通过一次，并且经过每一顶点的

通

路



欧拉回路

: 通过图中每条边且只通过一次，并且经过每一顶点的

回

路


有向图的

基图

：忽略有向图所有边的方向，得到的无向图称为该有向图的基图。


无向图


设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为

欧拉通路

；



如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路是

欧拉回路


具有欧拉回路的无向图G成为欧拉图


有向图


（1）设D是有向图，D的基图连通，则称经过D的每条边一次并且仅有一次的有向路径为

有向欧拉通路


（2）如果有向欧拉通路是有向回路，则称此有向回路为

有向欧拉回路


（3）具有有向欧拉回路的图D称为

有向欧拉图


定理


无向图G存在欧拉通路的充要条件是：G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。


推论


（1） 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点；


（2）当G是无奇度结点的连通图时，G必有欧拉回路


（3）G为欧拉图（存在欧拉回路）的充分必要条件是  G为无奇度结点的连通图



（有向图） 定理


有向图D存在欧拉通路的充要条件是：D为有向图，D的基图连通，并且所有顶点的出度与入度相等；或者  除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1.


推论


（1）当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度相等时，D的有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。


（2）当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。


（3）有向图D为有向欧拉图的充要条件是  D的基图为连通图，并且所有顶点的出、入度都相等。

欧拉回路的求解

两种方法：（1）DFS搜索  （Fleury）佛罗莱算法

（1）DFS搜索 思想求解欧拉回路的思路为：利用欧拉定理判断出一个图存在欧拉通路或欧拉回路后，选择一个正确的起始顶点，用DFS算法遍历所有的边（每条边只遍历一次），遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来。这组边的排列就组成了一条欧拉通路或回路。

（2） （Fleury）佛罗莱算法

设G为一个无向欧拉图，求G中一条欧拉回路的算法如下：

（1） 任取G中一顶点v0，令P0=v0；

（2）假设沿Pi=v0e1v1e2v2……eivi走到顶点vi，按下面方法从E(G)-{e1,e2,…,ei}中选ei+1。

ei+1与vi相关联

除非无别的边可供选择，否则ei+1不应该是Gi=G-{e1,e2,…,ei}中的桥。

（3）当（2）不能再进行时算法停止。

可以证明的是，当算法停止时，所得到的简单回路Pm=v0e1v1e2v2……emvm，（vm=v0）为G中一条欧拉回路。

备注知识：

设无向图G(V,E)为连通图，若边集E1属于E，在图G中删除E1中所有的边后得到的子图是不连通的，而删除了E1的任一真子集后得到的子图是连通图，则称E1是G的一个

割边集

。若一条边构成一个割边集，则称该边为

割边

，或

桥


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

//欧拉路径的输出(此图为无向图)

#include<iostream>

using


namespace


std;

#define M 200

struct


stack

{



int


top,node[M];

}s;


//顶点的栈结构

int


Edge[M][M];


//邻接矩阵

int


n;


//顶点个数

void


dfs(


int


x)


//这里的深度优先跟标准版有所区别，即不需要回溯

{



s.top++;



s.node[s.top]=x;


//将即将要扩展的结点压入栈中



for


(


int


i=0;i<n;i++)



{



if


(Edge[i][x])


//如果该节点还存在边



{



Edge[i][x]=0;



Edge[x][i]=0;


//删除该边，然后搜索另一结点



dfs(i);



break


;



}



}

}

void


Fleury(


int


x)


//对头节点使用Fleury算法 查找欧拉路径

{



s.top=0;



s.node[s.top]=x;



while


(s.top>=0)



{



int


flag=0;


//记录当前结点是否有边可以扩展



for


(


int


i=0;i<n;i++)



{



if


(Edge[i][s.top])



{



flag=1;



break


;



}



}



if


(!flag)



{



cout<<s.node[s.top]+1<<


" "


;


//记录时是从0--n-1，所以应该加1



s.top--;


//结点输出了，此结点出栈



}



else



{



s.top--;


//因为dfs处理时，需要先进栈，所以这里要先出栈，然后再进栈



dfs(s.node[s.top+1]);


//处理那个结点



}



}



cout<<endl;

}

int


main()

{



int


m,s,t;


//边数，读入的边的起点和终点



int


degree,num,start;


//每个顶点的度、基度顶点个数、欧拉回路的起点



cin>>n>>m;


//n---顶点数  m---边数



memset


(Edge,0,


sizeof


(Edge));



for


(


int


i=0;i<n;i++)



{



cin>>s>>t;



Edge[s-1][t-1]=1;



Edge[t-1][s-1]=1;



}



num=0;



start=0;


//如果存在奇度顶点，则从奇度顶点出发，否则从顶点0出发



for


(


int


i=0;i<n;i++)



{



degree=0;



for


(


int


j=0;j<n;j++)



degree+=Edge[i][j];



if


(degree%2)



{



num++;



start=i;



}



}



if


(num==0||num==2) Fleury(start);



else


cout<<


"No Euler path"


<<endl;



return


0;

}

练习：


单词（https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1070）

具体大意：

输入n（n<=100000）个单词，是否可以把所有这些单词排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同（例如 acm、malfon、mouse）。每个单词最多包含1000个小写字母，输入中可以有重复单词。

分析：

把字母看做节点，单词看成有向边，则问题有解，当且仅当图中有欧拉路径。前面讲过，有向图存在欧拉道路的条件有两个：底图（忽略边方向后得到的无向图）连通，且度数满足上面讨论过的条件。判断连通的方法有两种，一是之前介绍过的DFS，二是并查集，可以按照自己喜好选用。