欧拉回路和欧拉路径

引入：哥尼斯堡七桥问题

欧拉路径 == 一笔画问题

结论：

  • 欧拉路径
    • 起点终点 度数为奇数
    • 中间顶 度数为偶数
  • 对于无向图，所有边都是连通的
    • 存在欧拉路径的充分必要条件：度数(入读 + 出度)为奇数的点只能由0或2个。
    • 存在欧拉回路的充分必要条件：度数为奇数的点为0个。
  • 对于有向图，所有边都是连通的
    • 存在欧拉路径的充分必要条件：所有点的出度均等于入度 或 除了两个点以外，其余所有点出度等于入度，剩余两个点 一个满足出度比入度多1（起点），一个满足入度比出度多1（终点）
    • 存在欧拉回路的充分必要条件：所有点的出度均等于入度

证明：

  • 左 -> 右：已证明，右边本就是由左边推来的。
  • 左 <- 右：构造一种方案合法，即可证明
    • 直接 DFS ，遇到回路则进去转一圈出来，则一定可以走到终点，最终路径为一条线挂着许多环。

算法实现：

seq数组保存路径，最终的路径是 seq 的逆序。

1
2
3
4
5
6
void dfs(int u)
{
for 从 u 出发的所有边
    dfs() // 扩展
seq <- u
}

欧拉回路的 dfs 遍历时，用边判重(used数组)，会导致时间复杂度较高(平方级别)，优化为 遍历一条边，删去一条边，即可保证为线性的复杂度。

例题： 1124. 骑马修栅栏

思路：欧拉回路找最小字典序即可

如何保证最小字典序，从最小的点开始走。从最小的点开始走，则会最后回溯这个点，如此逆序即为字典序最小的序列。

代码如下：

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

using namespace std;

const int N = 510, M = 2100;

int n = 500, m;
int g[N][N];
int d[N];
int ans[M], cnt;

void dfs(int u)
{
    for (int i = 1; i <= n; i ++ )
        if(g[u][i])
        {
            g[u][i] --, g[i][u] --;
            dfs(i);
        }
    ans[ ++ cnt] = u;
}

int main()
{
    cin >> m;
    
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] ++, g[b][a] ++;
        d[a] ++, d[b] ++;
    }
    
    int start = 1;
    while(!d[start]) start ++;
    for (int i = 1; i <= n; i ++ )
        if(d[i] % 2)
        {
            start = i;
            break;
        }
        
    dfs(start);
    
    for (int i = cnt; i; i -- )
        cout << ans[i] << endl;
    
    return 0;
}