欧拉回路 欧拉通路 欧拉回路图

admin 管理员组

文章数量: 888526

欧拉回路 欧拉通路 欧拉回路图

来源

一、定义

对于无向图：
　　1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；
　　2) 如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）；
　　3) 具有欧拉回路的无向图G称为欧拉图（Euler graph）。
对于有向图：
　　1) 设D是有向图，D的基图连通，则称经过D的每条边一次并且仅一次的有向路径为有向欧拉通路；
　　2) 如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路（directed Euler circuit）；
　　3) 具有有向欧拉回路的有向图D称为有向欧拉图（directed Euler graph）。

二、定理

无向图：
　　无向图G存在欧拉通路的充要条件是：G为连通图，并且G**仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点**。
推论：
　　1) 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。
　　2) 当G是无奇度结点的连通图时，G必有欧拉回路。
　　3) G为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度结点的连通图。
有向图：
　　D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。
推论：
　　1) 当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度都相等时，D的有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。
　　2) 当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。
　　3) 有向图D为有向欧拉图的充分必要条件是D的基图为连通图，并且所有顶点的出、入度都相等。

三、算法

连通性：
　　采用深度搜索，如果有节点没有访问，说明不连通。

void DFS(int cur)                     //连通性的判断  是否完全访问掉
{int i ;for(i = 0; i<n; i++){if(!vis[i]&&edge[cur][i]){vis[i] = 1;DFS(i);}}
}DFS(0);for(int i =0; i<n; i++){if(!vis[i])return false;}  

欧拉图判断：

# 无向欧拉图：for(int i =0; i<n; i++){if(degree[i]%2){return false;}}
# 有向欧拉图：for (int i=0; i<n; i++)if (in[i] != out[i]){return false;}

路径查找：

// 无向图的欧拉回路, cur 点, 从 pos 点开始搜
void DFS_two(int cur,int pos)
{int i,a,b;stack[top++] = cur;for(i = pos;i<n;i++){if(edge[cur][i] != 0){edge[i][cur] = 0;edge[cur][i] = 0;degree[cur]--;degree[i]--;DFS_two(i,0);break;}}if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步{b = stack[--top];a = stack[--top];edge[a][b] = 1;edge[b][a] = 1;degree[a]++;degree[b]++;DFS_two(a,b+1);}}

// 有向图的欧拉回路, 在 cur 点, 从 pos 点开始搜
void DFS_first(int cur ,int pos)
{int i,a,b;stack[top++] = cur;for(i = pos;i<n;i++){if(edge[cur][i] != 0){edge[cur][i] = 0;out[cur]--;in[i]--;DFS_first(i,0);break;}}if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步{b = stack[--top];a = stack[--top];edge[a][b] = 1;out[a]++;in[b]++;DFS_first(a,b+1);}
}

所有代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int MAX = 60;
int edge[MAX][MAX];
int degree[MAX];
int in[MAX],out[MAX];
int n,type;                           //judge  grape 类型
int e;                                //边数
int top;                              // 栈底  初始化为 0；
int stack[MAX];                       //记录欧拉通路的路径
int vis[MAX];                         //是否已经访问；
void DFS(int cur)                     //连通性的判断  是否完全访问掉
{int i ;for(i = 0; i<n; i++){if(!vis[i]&&edge[cur][i]){vis[i] = 1;DFS(i);}}
}// 判断是否存在欧拉回路:
// 无向图中: 连通图且所有顶点度数为偶数
// 有向图中: 连通图且所有顶点的入度等于出度
bool judge()
{memset(vis,0,sizeof(vis));        //访问初始化DFS(0);for(int i =0; i<n; i++){if(!vis[i])return false;}                            //连通性的判断  是否完全访问掉if(type)                     //有向图{for (int i=0; i<n; i++)if (in[i] != out[i]){return false;}}else                           //无向图{for(int i =0; i<n; i++){if(degree[i]%2){return false;}}}return true;
}
// 有向图的欧拉回路, 在 cur 点, 从 pos 点开始搜
void DFS_first(int cur ,int pos)
{int i,a,b;stack[top++] = cur;for(i = pos;i<n;i++){if(edge[cur][i] != 0){edge[cur][i] = 0;out[cur]--;in[i]--;DFS_first(i,0);break;}}if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步{b = stack[--top];a = stack[--top];edge[a][b] = 1;out[a]++;in[b]++;DFS_first(a,b+1);}
}
// 无向图的欧拉回路, cur 点, 从 pos 点开始搜
void DFS_two(int cur,int pos)
{int i,a,b;stack[top++] = cur;for(i = pos;i<n;i++){if(edge[cur][i] != 0){edge[i][cur] = 0;edge[cur][i] = 0;
degree[cur]--;
degree[i]--;DFS_two(i,0);break;}}if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步{b = stack[--top];a = stack[--top];edge[a][b] = 1;edge[b][a] = 1;degree[a]++;degree[b]++;DFS_two(a,b+1);}}
int main()
{printf("0, 无向图    1, 有向图 : ");scanf("%d", &type);printf("输入顶点个数: ");scanf("%d",&n);memset(edge,0,sizeof(edge));memset(degree,0,sizeof(degree));  //无向图的度数memset(in,0,sizeof(in));          //有向图的入度memset(out,0,sizeof(out));        //有向图的出度while(true){int a,b;                      //边集scanf("%d %d",&a,&b);if(!(a||b))                   //  0 0 break{break;}edge[a][b] = 1;in[b]++;out[a]++;if(!type)                     // 如果是无向图{edge[b][a] = 1;degree[a]++;                   //无向图的度数degree[b]++;}}if(judge()){printf("\n一条欧拉回路: ");if(type)DFS_first(0,0);elseDFS_two(0,0);for(int i =0; i<top; i++){printf("%d",stack[i]);if(i+1!=top)printf(" -> ");}putchar('\n');}else{printf("\n不存在欧拉回路!\n");}return 0;
}

本文标签： 欧拉回路 欧拉通路 欧拉回路图