【算法】欧拉与图的爱恨情仇

请注意,本文编写于 92 天前,最后修改于 92 天前,其中某些信息可能已经过时。

欧拉真是 tql
1736年发表论文《柯尼斯堡的七桥》,解决了七桥问题,提出了一笔画定理,顺便解决了一笔画问题
一般认为:欧拉的研究是图论的开端

Orz

文中大部分内容来自于 维基百科 Eulerian path

一笔画定理

先介绍一些概念:

欧拉图: 若一个图能够遍历完所有的边而没有重复,这样的图称为欧拉图
欧拉路径: 遍历欧拉图每一条边恰好一次的路径
欧拉回路: 起点和终点相同的欧拉路径

定理一

联通无向图 $G$ 有欧拉路径的充要条件是: $G$ 中奇顶点的数量为 $0$ 或 $2$
联通无向图 $G$ 有欧拉环的充要条件是: $G$ 中奇顶点的数量为 $0$

证明:

  • 必要性:如果一个图能一笔画成,那么每个入度 $=$ 出度或者相差一:这时该点必然是起点或者终点
    若起点 $=$ 终点(即欧拉回路)则奇顶点的数目为 $0$
    否则奇顶点的数目为 $2$
  • 充分性:

    • 如果图中没有奇顶点,从任意一个点出发,走出一个环,如果这个环是原图,结束;否则因为原图联通,那么这个环和剩余部分必然有公共顶点,那么从该点出发,在原图的剩余部分中继续此步骤,直到原图被分割为若干个环,而相连的环可以合并为一个环,即欧拉回路
    • 如果有两个奇顶点 $u,v$ ,那么连接 $u,v$ ,即为没有奇顶点情况,最后去掉 $(u,v)$ 即可

定理二

如果连通无向图 $G$ 有 $2k$ 个奇顶点,那么它可以用 $k$ 笔画成,并且至少要用 $k$ 笔画成

证明:

  • 将 $2k$ 个奇顶点两两分组,则得到一个无奇顶点的连通图,必然有一条欧拉回路。然后将 $k$ 条后加入的边删去,得到 $k$ 段路径,所以可以由 $k$ 笔画成
  • 假设全图可以 $q$ 笔画成,也就是说可以看做 $q$ 条欧拉路径,由于每条联众只有不多于两个奇顶点,所以 $2q\ge 2k$ ,即 $q\ge k$ ,所以至少需要 $k$ 笔画成

有向图的一笔画

联通有向图 $G$ 有欧拉路径的充要条件是: $G$ 中最多有一对点出度 $\neq$ 入度,其中中一个点的出度 $=$ 入度 $+1$ ,一个点的入度 $=$ 出度 $+1$
联通有向图 $G$ 有欧拉回路的充要条件是: $G$ 中所有点出度 $=$ 入度

证明类似

模板

UOJ 117 欧拉回路

#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
namespace sol1 {
    struct Edge {int t, n;}e[N << 2];
    int head[N], tot = 1;
    bool vis[N << 1];
    int deg[N], sta[N << 1], top;
    int n, m;
    void dfs(int x) {
        while(head[x]) {
            int i = head[x];
            head[x] = e[i].n;
            if(vis[i >> 1]) continue;
            vis[i >> 1] = 1;
            dfs(e[i].t);
            sta[++ top] = i;
        }
    }
    void work() {
        n = read(); m = read();
        for(int i = 1; i <= m; ++ i) {
            int u = read(), v = read();
            ++ deg[u]; ++ deg[v];
            e[++ tot] = {v, head[u]}; head[u] = tot;
            e[++ tot] = {u, head[v]}; head[v] = tot;
        }
        for(int i = 1; i <= n; ++ i)
            if(deg[i] & 1) {
                puts("NO");
                return ;
            }
        for(int i = 1; i <= n; ++ i) {
            if(deg[i]) {
                dfs(i);
                break;
            }
        }
        if(top != m)
            puts("NO");
        else {
            puts("YES");
            while(top) {
                printf("%d ", sta[top] & 1 ? - (sta[top] >> 1) : (sta[top] >> 1));
                -- top;
            }
            puts("");
        }
    }
}
namespace sol2 {
    struct Edge {int t, n;}e[N << 1];
    int head[N], tot;
    bool vis[N << 1];
    int in[N], out[N], sta[N << 1], top;
    int n, m;
    void dfs(int x) {
        while(head[x]) {
            int i = head[x];
            head[x] = e[i].n;
            dfs(e[i].t);
            sta[++ top] = i;
        }
    }
    void work() {
        n = read(); m = read();
        for(int i = 1; i <= m; ++ i) {
            int u = read(), v = read();
            ++ out[u]; ++ in[v];
            e[++ tot] = {v, head[u]}; head[u] = tot;
        }
        for(int i = 1; i <= n; ++ i)
            if(in[i] != out[i]) {
                puts("NO");
                return ;
            }
        for(int i = 1; i <= n; ++ i) {
            if(in[i]) {
                dfs(i);
                break;
            }
        }
        if(top != m)
            puts("NO");
        else {
            puts("YES");
            while(top)
                printf("%d ", sta[top --]);
            puts("");
        }
        
    }
}
int main() {
    if(read() - 1)
        sol2::work();
    else
        sol1::work();
    return 0;
}
Comments

添加新评论