zhanyeye's learning log

(^～^)

0%

欧拉回路和欧拉路径

Posted on Edited on In
概述

若图 G 中存在这样一条路径，使得它恰好通过 G 中每条边一次，则称该路径为 欧拉路径。若该路径是一个环路，则称为 欧拉（Euler）回路。

具有欧拉回路的图称称为 欧拉图。

具有欧拉路径但不具有欧拉回路的图称为 半欧拉图。

有关欧拉路的重要性质

无向图

  1. 一个无向图 G 存在欧拉路径当且仅当无向图 G 是连通图，且该图中有两个奇度顶点（度数为奇数）或者无奇度顶点。
  2. 当无向图 G 是包含两个奇度顶点的连通图时，G 的欧拉路径必定以这两个奇度顶点为端点。
  3. 一个无向图 G 存在欧拉回路当且仅当无向图 G 连通且不存在奇度顶点。

有向图

  1. 一个有向图 G 存在欧拉路径当且仅当 G 是弱连通的有向图（将有向边全部看成无向边后该图是连通图），且满足以下两个条件之一：
    • 所有顶点的入度和出度相等；
    • 有一个顶点的出度与入度之差为 1，一个顶点的出度与入度之差为 -1，其余顶点的入度和出度相等。
  2. 当有向图 G 包含两个入度和出度不相同的顶点且有欧拉路径时，欧拉路径必定以这两个入度出度不相同的顶点为端点。
  3. 一个有向图 G 存在欧拉回路当且仅当图 G 是连通的有向图，且所有顶点的入度和出度相等。
性质 图
没有奇度顶点的无向连通图 欧拉图
有且仅有两个奇度顶点的无向连通图 半欧拉图
所有顶点入度和出度相等的有向弱连通图 欧拉图
有且仅有两个顶点入度与出度不等且一个入度与出度差为 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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100;
const int M = 10000;

struct edge {
    int v, next;
    edge() {}
    edge(int _v, int _next):v(_v), next(_next) {}
} E[N];

int p[N], eid;

void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}

void insert(int u, int v) {
    E[eid] = edge(v, p[u]);
    p[u] = eid++;
}

void insert2(int u, int v) {
    insert(u, v);
    insert(v, u);
}

int cnt;
bool vis[N];
int n, m;
int degree[N];

void dfs(int u) {
    vis[u] = true;
    cnt++;
    for (int e = p[u]; e != -1; e = E[e].next) {
        int v = E[e].v;
        if (!vis[v]) {
            dfs(v);
        }
    }
}

void eulor() {
    memset(vis, false, sizeof vis);
    dfs(1); // dfs判断该图是否连通
    if (cnt != n) {
        cout << "It doesn't have an eulor path" << endl;
        return;
    }
    int cnt_odd = 0;
    for (int i = 1; i <= n; i++) { //统计奇度顶点的个数
        if (degree[i] % 2 == 1) {
            cnt_odd++;
        }
    }

    //根据奇度顶点来判断
    if (cnt_odd == 0) {
        cout << "It has an eulor circuit!" << endl;
    } else if (cnt_odd == 2) {
        cout << "It has an eulor path!" << endl;
    } else {
        cout << "It doesn't have an euler path!" << endl;
    }
}

int main() {
    init();
    memset(degree, 0, sizeof degree);
    cin >> n >> m;
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        insert2(u, v);
        degree[u]++;
        degree[v]++;
    }
    eulor();
    return 0;
}

判断有向图的欧拉回路和欧拉路径

我们让euler函数返回一个int类型的值表示如果存在欧拉回路或欧拉路径，起始点是哪一个，如果不存在，我们让它返回值为 0，如果是欧拉回路，我们就取点 1 作为起始点，如果是欧拉路径，我们应该取入度与出度差为 -1 的点为起始点。

为了判断方便，我们可以声明两个变量 first和last来记录入度与出度差为 -1 的点和 1 的点是哪个点，如果不存在这样的点，值为 0。

现在我们来声明euler函数，声明变量first和last，并写下循环框架，我们将会遍历每个点的入度和出度差进行判断，如果遇到一个点的入度和出度之差小于 -1 或者大于 1 了，那么该图肯定没有欧拉路径，我们进行输出并返回 0。

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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100;
const int M = 10000;

struct edge {
    int v, next;
    edge() {}
    edge(int _v, int _next): v(_v), next(_next) {}
} E[N];

int p[N], eid;

void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}

void insert(int u, int v) {
    E[eid] = edge(v, p[u]);
    p[u] = eid++;
}

int degree[N];
int n, m;

int euler() {
    int first = 0, last = 0;
    for (int i = 1; i <= n; i++) {
        if (degree[i] < -1 || degree[i] > 1) {
            cout << "It doesn't have an euler path!" << endl;
            return 0;
        } else if (degree[i] == -1) {
            if (first != 0) {
                cout << "It doesn't have an euler path!" << endl;
                return 0;
            } else {
                first = i;
            }
        } else if (degree[i] == 1) {
            if (last != 0) {
                cout << "It doesn't have an euler path!" << endl;
                return 0;
            } else {
                last = i;
            }
        }
    }

    if (first == 0 && last == 0) {
        cout << "It has an euler circuit!" << endl;
        return 1;
    } else if (first != 0 && last != 0) {
        cout << "It has an euler path" << endl;
        return first;
    } // 剩下的情况不可能存在,因为有向图中入度和出度的总和一定是一样的
}

int main() {
    init();
    cin >> n >> m;
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        insert(u, v);
        degree[u]--;
        degree[v]++;
    }
    euler();
    return 0;
}
无向图欧拉路径

计算无向图的欧拉路经可以用“套圈法”、基于深度优先搜索来实现。

从一个合适的顶点出发进行深度优先搜索。当搜到一个顶点 u 时：

  1. 如果此时没有顶点与该顶点相连，那么就将 u 加入路径中并回溯；
  2. 如果有顶点 v 与顶点 u 相连，那么就删除无向边 <u, v>，并继续搜索顶点 v 。将所有和 u 相邻的顶点遍历完之后，将 u 加入路径中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int MAX_N = 100;
int mat[MAX_N][MAX_N];
int match[MAX_N];  // 表示顶点剩余的度
int n;  // 顶点个数
void solve(int u) {
    if (match[u] > 0) {
        for (int i = 0; i < n; ++i) {
            if (mat[u][i]) {
                mat[u][i]--;
                mat[i][u]--;
                solve(i);
            }
        }
    }
    // 将u加入路径中
}
有向图欧拉路经

计算有向图的欧拉路经同样可以用“套圈法”。和无向图唯一不同的是，在记录方案的时候将顶点编号插入栈中，并在最后将栈中的元素依次输出。也就是说，将之前输出的顺序逆置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int MAX_N = 100;
const int MAX_M = 10000;
int mat[MAX_N][MAX_N];
int match[MAX_N];  // 表示顶点剩余的度
int n;  // 顶点个数
int stk[MAX_M], top = 0;  // 用数组 stk 来模拟一个栈
void solve(int u) {
    if (match[u] > 0) {
        for (int i = 0; i < n; ++i) {
            if (mat[u][i]) {
                mat[u][i]--;
                solve(i);
            }
        }
    }
    stk[top++] = u;  // 将顶点 u 插入栈中
}

如果存在欧拉回路，”套圈法” 可以从任意点开始搜索。如果是欧拉路径，需要找到一个起点，然后再套用 “套圈法”。

而访问一个点以后我们为什么不先输出，而是等这个点搜索完成以后再输出呢。可以看下面这个反例。如果从 11 开始搜索，先搜索 1,2,3,61,2,3,6，那么可能最后输出的路径为 1,2,3,6,1,4,5,3，而这个路径是错误的，而后输出的路径为 1,6,3,5,4,3,2,1，才是正确的欧拉回路。

例题：De Bruijin 序列

De Bruijin 序列是指这样一个序列：对于一个包含 n 个元素的字符集，生成一个仅包含 n 种字符的字符串，使得这个字符串中 $k^n$ 种长度为 k 的子串均恰好出现一次。

例如，对于 n=2,k=2,S={0,1} 的 De Bruijin 序列，有如下满足要求的一个字符串：

1
2
3
4
5
00110
00
 01
  11
   10

解析：

我们可以把这个问题转化为图论问题：图中的顶点代表每种长度为 k-1 的子串，每条边代表一个子串增加一个字符后的转移，如下图所示：

对于 n=2, k=2, S={0,1} 的情况，0增加一个字符0后，变成00，最后 k-1 位是0，所以从0连向0一条边00；0增加一个字符1后，变成01，最后 k-1 位是1；以此类推。

我们用 n=2,k=3,S={0,1} 来进一步理解这个建模：

img

图中的每条边都对应着一个长度为 k 的子串，而每走一条边，就意味着在整个字符串的最后增加一个字符。这样，图中的一个欧拉路径就对应着一个满足要求的完整字符串。例如上图中，一个欧拉路径01 11 11 10 01 10 00 00 01就对应着字符串0111010001，其中恰好包含 $2^3=8$ 种不同的子串，且每种子串刚好出现一次

有向图求欧拉路径代码

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
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

// 求有向图的欧拉路径

const int N = 100;
const int M = 10000;

struct edge {
    int v, next;
    edge() {}
    edge(int _v, int _next): v(_v), next(_next) {}
} E[M];

int p[N], eid;

void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}

void insert(int u, int v) {
    E[eid] = edge(v, p[u]);
    p[u] = eid++;
}

int n, m;
int degree[N];

int euler() {
    int first = 0, last = 0;
    for (int i = 1; i <= n; i++) {
        if (degree[i] > 1 || degree[i] < -1) {
            return 0;
        } else if (degree[i] == -1) {
            if (first != 0) {
                return 0;
            } else {
                first = i;
            }
        } else if (degree[i] == 1) {
            if (last != 0) {
                return 0;
            } else {
                last = i;
            }
        }
    }
    if (first == 0 && last == 0) {
        return 1;
    } else if (first != 0 && last != 0) {
        return first;
    } else {
        return 0;
    }
}

stack<int> path;
void dfs(int u) {
    while(p[u] != -1) {
        int v = E[p[u]].v; // 拿到和u相邻的点v
        p[u] = E[p[u]].next; // 删除边<u, v>
        dfs(v);
    }
    path.push(u);
}

bool euler_find() {
    int start = euler();
    if (start == 0) {
        return false;
    } else {
        dfs(start);
        return path.size() == m + 1;
    }
}

int main() {
    cin >> n >> m;
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        insert(u, v);
        degree[u]--;
        degree[v]++;
    }
    if (!euler_find()) {
        cout << "It doesn't have an euler path!" << endl;
    } else {
        while (!path.empty()) {
            cout << path.top() << endl;
            path.pop();
        }
    }
    return 0;
}