Hexo
0%

欧拉图

Posted on In ,
Symbols count in article: 1.6k Reading time ≈ 1 mins.

欧拉图

欧拉回路：通过图中每条边恰好一次的回路

欧拉通路：通过图中每条边恰好一次的通路

欧拉图：具有欧拉回路的图

半欧拉图：具有欧拉通路但不具有欧拉回路的图

欧拉图中所有顶点的度数都是偶数

  • 无向图是欧拉图当且仅当：

    • 非零度顶点是连通的

    • 顶点的度数都是偶数

  • 无向图是半欧拉图当且仅当：

    • 非零度顶点是连通的

    • 恰有 2 个奇度顶点

  • 有向图是欧拉图当且仅当：

    • 非零度顶点是强连通的

    • 每个顶点的入度和出度相等

  • 有向图是半欧拉图当且仅当：

    • 非零度顶点是弱连通的

    • 至多一个顶点的出度与入度之差为 1

    • 至多一个顶点的入度与出度之差为 1

    • 其他顶点的入度和出度相等

求欧拉回路

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
86
87
88
89
90
91
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int ans[200];
int top;
int N,M;
int mp[200][200];
void dfs(int x)
{
    int i;
    top++;
    ans[top]=x;
    for (i=1; i<=N; i++)
    {
        if(mp[x][i]>0)
        {
            mp[x][i]=mp[i][x]=0;///删除此边
            dfs(i);
            break;
        }
    }
}

void fleury(int x)
{
    int brige,i;
    top=1;
    ans[top]=x;///将起点放入Euler路径中
    while(top>=0)
    {
        brige=0;
        for (i=1; i<=N; i++) /// 试图搜索一条边不是割边（桥）
        {
            if(mp[ans[top]][i]>0)///存在一条可以扩展的边
            {
                brige=1;
                break;
            }
        }
        if (!brige)/// 如果没有点可以扩展，输出并出栈
        {
            printf("%d ", ans[top]);
            top--;
        }
        else     /// 否则继续搜索欧拉路径
        {
            top--;///为了回溯
            dfs(ans[top+1]);
        }
    }
}

int main()
{
    int x,y,deg,num,start,i,j;
    scanf("%d%d",&N,&M);
    memset(mp,0,sizeof (mp));
    for(i=1;i<=M; i++)
    {
        scanf("%d%d",&x,&y);
        mp[x][y]=1;
        mp[y][x]=1;
    }
    num=0;
    start=1;///这里初始化为1
    for(i=1; i<=N; i++)
    {
        deg=0;
        for(j=1; j<=N; j++)
        {
            deg+=mp[i][j];
        }
        if(deg%2==1)///奇度顶点
        {
            start=i;
            num++;
        }
    }
    if(num==0||num==2)
    {
        fleury(start);
    }
    else
    {
        puts("No Euler path");
    }
    return 0;
}