欧拉回路

基本概念及定理
1. 欧拉通路、欧拉回路、欧拉图
无向图：
1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；
2) 如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）；
3) 具有欧拉回路的无向图G称为欧拉图（Euler graph）。
有向图：
1) 设D是有向图，D的基图连通，则称经过D的每条边一次并且仅一次的有向路径为有向
欧拉通路；
2) 如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路（directed Euler circuit）；
3) 具有有向欧拉回路的有向图D称为有向欧拉图（directed Euler graph）。
请思考图5.1中的无向图及有向图是否为欧拉图或有向欧拉图。

图5.1 欧拉回路及有向欧拉回路

2. 定理及推论
欧拉通路和欧拉回路的判定是很简单的，请看下面的定理及推论。
定理5.1 无向图G存在欧拉通路的充要条件是：
G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。
推论5.1：
1) 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。
2) 当G是无奇度结点的连通图时，G必有欧拉回路。
3) G为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度结点的连通图。

EXP图5.1(a)所示的无向图，存在两个奇度顶点v2和v5，所以存在欧拉通路，且欧拉通路必
以这两个顶点为起始顶点和终止顶点；该无向图不存在欧拉回路。图5.1(b)所示的无向图为欧拉
图。

定理5.2 有向图D存在欧拉通路的充要条件是：
D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余
顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度
与入度之差为-1。
推论5.2：
1) 当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度都相等时，D的
有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为
终点。
2) 当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。
3) 有向图D为有向欧拉图的充分必要条件是D的基图为连通图，并且所有顶点的出、入度
都相等。
例如图5.1(c)所示的有向图，顶点v2和v4入度和出度均为1；顶点v1的出度为2、入度为1，
二者差值为1；顶点v3的出度为1、入度为2，二者相差为-1；所以该有向图只存在有向欧拉通路，
且必须以顶点v1为始点，以顶点v3为终点。图5.1(d)所示的有向图不存在有向欧拉通路。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 using namespace std;
  5 const int MAX = 60;
  6 int edge[MAX][MAX];
  7 int degree[MAX];
  8 int in[MAX],out[MAX];
  9 int n,type;                           //judge  grape 类型
 10 int e;                                //边数
 11 int top;                              // 栈底  初始化为 0；
 12 int stack[MAX];                       //记录欧拉通路的路径
 13 int vis[MAX];                         //是否已经访问；
 14 void DFS(int cur)                     //连通性的判断  是否完全访问掉
 15 {
 16     int i ;
 17     for(i = 0; i<n; i++)
 18     {
 19         if(!vis[i]&&edge[cur][i])
 20         {
 21             vis[i] = 1;
 22             DFS(i);
 23         }
 24     }
 25 }
 26 
 27 
 28 // 判断是否存在欧拉回路:
 29 // 无向图中: 连通图且所有顶点度数为偶数
 30 // 有向图中: 连通图且所有顶点的入度等于出度
 31 bool judge()
 32 {
 33     memset(vis,0,sizeof(vis));        //访问初始化
 34     DFS(0);
 35     for(int i =0; i<n; i++)
 36     {
 37         if(!vis[i])
 38             return false;
 39     }                            //连通性的判断  是否完全访问掉
 40     if(type)                     //有向图
 41     {
 42         for (int i=0; i<n; i++)
 43             if (in[i] != out[i])
 44             {
 45                 return false;
 46             }
 47     }
 48     else                           //无向图
 49     {
 50         for(int i =0; i<n; i++)
 51         {
 52             if(degree[i]%2)
 53             {
 54                 return false;
 55             }
 56         }
 57     }
 58     return true;
 59 }
 60 // 有向图的欧拉回路, 在 cur 点, 从 pos 点开始搜
 61 void DFS_first(int cur ,int pos)
 62 {
 63     int i,a,b;
 64     stack[top++] = cur;
 65     for(i = pos;i<n;i++)
 66     {
 67         if(edge[cur][i] != 0)
 68         {
 69             edge[cur][i] = 0;
 70             out[cur]--;
 71             in[i]--;
 72             DFS_first(i,0);
 73             break;
 74         }
 75     }
 76     if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步
 77     {
 78         b = stack[--top];
 79         a = stack[--top];
 80         edge[a][b] = 1;
 81         out[a]++;
 82         in[b]++;
 83         DFS_first(a,b+1);
 84     }
 85 }
 86 // 无向图的欧拉回路, cur 点, 从 pos 点开始搜
 87 void DFS_two(int cur,int pos)
 88 {
 89         int i,a,b;
 90     stack[top++] = cur;
 91     for(i = pos;i<n;i++)
 92     {
 93         if(edge[cur][i] != 0)
 94         {
 95              edge[i][cur] = 0;
 96             edge[cur][i] = 0;
 97 degree[cur]--;
 98 degree[i]--;
 99             DFS_two(i,0);
100             break;
101         }
102     }
103     if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步
104     {
105         b = stack[--top];
106         a = stack[--top];
107         edge[a][b] = 1;
108         edge[b][a] = 1;
109         degree[a]++;
110         degree[b]++;
111         DFS_two(a,b+1);
112     }
113 
114 }
115 int main()
116 {
117     printf("0, 无向图    1, 有向图 : ");
118     scanf("%d", &type);
119     printf("输入顶点个数: ");
120     scanf("%d",&n);
121     memset(edge,0,sizeof(edge));
122     memset(degree,0,sizeof(degree));  //无向图的度数
123     memset(in,0,sizeof(in));          //有向图的入度
124     memset(out,0,sizeof(out));        //有向图的出度
125 
126     while(true)
127     {
128         int a,b;                      //边集
129         scanf("%d %d",&a,&b);
130         if(!(a||b))                   //  0 0 break
131         {
132             break;
133         }
134         edge[a][b] = 1;
135         in[b]++;
136         out[a]++;
137         if(!type)                     // 如果是无向图
138         {
139             edge[b][a] = 1;
140             degree[a]++;                   //无向图的度数
141             degree[b]++;
142         }
143     }
144     if(judge())
145     {
146         printf("
一条欧拉回路: ");
147         if(type)
148             DFS_first(0,0);
149         else
150             DFS_two(0,0);
151         for(int i =0; i<top; i++)
152         {
153             printf("%d",stack[i]);
154             if(i+1!=top)
155                 printf(" -> ");
156         }
157         putchar('
');
158     }
159     else
160     {
161         printf("
不存在欧拉回路!
");
162     }
163     return 0;
164 }

View Code

摘自《图论算法理论、实现及应用-王桂平》