欧拉图详解

欧拉图定义

经过图（无向图或有向图）中每条边一次且仅一次并且行遍图中每个顶点的回路(通路)，称为欧拉回路（欧拉通路）。存在欧拉回路的图，称为欧拉图。

欧拉图判断定理：

引理1：对于边数m > 0的连通图G,SEO靠我 如果G的每个顶点为偶数，则G有环

反证法：

假设G无环 => G是一个无向树 => G中至少包含两个树叶(度数为1的顶点) ，与每个顶点度数为偶数矛盾。

定理1：无向图G是欧拉图的充分必要条件是G 是连通SEO靠我图并且所有顶点度数为偶数。

证明：

平凡图显然成立(n = 1, m = 0)

（1）必要性 ： 设图G是欧拉图，证明G连通且且所有顶点度数为偶数。

G是欧拉图 => G中存在欧拉回路tour （根据欧拉图定SEO靠我义）

回路tour经过图G中每一个顶点 => G连通

对于回路tour上的任一中间顶点v，经过一条边e进入v，经过另一条边f离开v，进入v次数等于离开v次数 => 顶点v度数为偶数。

对于回路tour的起点SEO靠我和终点s，第一次离开，最后一次进入 => s度数为偶数。

充分性：G连通且所有顶点度数为偶数，证明G是欧拉图。（数学归纳法）

（a） 简单情况

n = 1, m = 0

n = 1, m = 1 (自环)

（bSEO靠我）归纳步骤（强归纳法）

设连通图G顶点数为N > 0 , 边数为M > 0。

假设任意顶点数 n < N, 边数m < M，且所有顶点度数为偶数的连通图Gi是欧拉图，证明顶点数 = N,

边数 = M且所有SEO靠我顶点度数为偶数的连通图G是欧拉图。

证明：欧拉图是若干边不相交的回路合并findCircle(G)算法 //G是连通图, S是一个全局栈 1 根据引理1，G有环，找出一个回路C，将回路CSEO靠我压入栈S //PUSH(S, C) 2 删除回路C上的边, 得到G= G - E[C] 3 如果G连通，调用findCircle(G) //继续搜索G中的回路 SEO靠我 4 否则返回G //算法终止时返回s个连通分量 mergeCircle(G) 算法 1 G = findCircle(G) //调用findCircle(G)SEO靠我, 得到回路集合S和非连通图G 2 设G = {G1, G2,...Gs}，其中s > 1 3 根据归纳假设，G的每个连通分量Gi(1 <= i <= s)有一条欧拉子SEO靠我回路Ci 4 p = POP(S) //取出栈顶的回路p，p是findCircle算法找出的最后一条回路，删除p后，图G变成非连通图G， 所以回路p与每一个连通分量Gi都有交点。 SEO靠我 5 p依次与Gi(1 <= i <= s)的欧拉子回路Ci合并，得到C //此时C包含图G的所有顶点 6 while(S is not empty) //按搜索回路次序的逆SEO靠我序合并 7 p = POP(S) 8 C = p 合并 C //从回路p任一点出发，遇到和回路C的交点v时，先走完回路C回到交点v之后，继续走完p

mergeCircleSEO靠我(G)算法终止时，C包含图G的所有边和顶点，且边不重复，所以C是图G的一条欧拉回路，得证。

Fleury算法（避桥法）

从任意一点开始，沿着没有走过的边向前走

在每个顶点，优先选择剩下的非桥边，除非只有一条SEO靠我边

直到得到欧拉回路或者宣布失败FLEURY(G)u = v0; //如果求欧拉通路，则degree[v0]为奇数while degree[u] > 0 {FIND-BRIDGES(u) //从顶点u对SEO靠我子图G - {e1, e2, ..., ei-1}深搜，标记所有桥//找出顶点u关联的一条非桥边或者桥边eEdge e = null; //选择的边for(Edge x = adj[u].first;SEO靠我 x != null; x = x.next) {v = x.v;//(u, v)if(!visited[u][v]){//边(u, v)未访问if(e == null){//第一条未访问的边ee =SEO靠我 x;} if(!isBrige(x) ){//x是非桥边e = x;//break;}}}//标记已访问的无向边evisited[e.u][e.v] = true;visited[e.v][e.u]SEO靠我 = true;degree[e.u]--;degree[e.v]--;P = P + {e} //将边e添加到欧拉回路或者欧拉通路u = e.v}if(P.length() == M)return SEO靠我P;//欧拉回路或者欧拉通路的边序列 else Print("No euler circuit")

应用（轮盘设计）

设旋转磁鼓分成8个扇区，每个扇区标记一个0和1，有3个探测器能够读出连续的3个扇区的标SEO靠我记。现在的问题是：如何赋给扇区的标记，使得能够根据探测器读书确定磁鼓的问题。

思路：