欧拉图 学习笔记

发表于 | 分类于 | | + s

模板及讲解

定义

欧拉路：能从无向图的一个点出发走一条路径，每条边恰好经过一次，这样的路叫欧拉路。
欧拉回路：能从无向图任意一个点出发走一条路径，每条边恰好经过一次，并且回到该点，这样的路叫欧拉路。
欧拉图：具有欧拉回路的图称为欧拉图，具有欧拉路而无欧拉回路的图称为半欧拉图

性质

至多有两个奇点(度数为奇数)的无向图一定存在欧拉路

当有两个奇点时欧拉路必然从一个奇点到另一个奇点
当有没有奇点时欧拉路必然是一个欧拉回路

欧拉图中所有点都是偶点并且所有点连通。

一笔画：
连通分量是一个孤立的点, 只需要0笔可以完成
连通分量是一个欧拉图或半欧拉图, 只需要1笔可以完成
否则需要奇点数目/2笔可以完成
简单证明为一个联通分量中两个奇点(非欧拉图/半欧拉图)就要有一条笔画划过，如果没有奇点(就是一个欧拉图)也要用一条笔画划过，结论得证
HDU 3018

题目

判断是否有欧拉回路/欧拉路

Hdu 1878
题意：欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
解：欧拉图中所有点都是偶点并且所有点连通。用并查集判连通，记录度数即可。

代码：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, m, de[1005], f[1005];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void clean() {}
int solve() {
    clean();
    for (int i = 1; i <= n; i++) de[i] = 0, f[i] = i;
    for (int x, y, i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        de[x]++, de[y]++;
        int u = find(x), v = find(y);    
        if (u != v) f[u] = v;
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) find(i);
    for (int i = 1; i <= n; i++) ans1 += (f[i] == i), ans2 += ((de[i] % 2) ? 0 : 1);
    if (ans1 != 1) return printf("0\n"), 0;
    if (ans2 != n) return printf("0\n"), 0;
    return printf("1\n"), 0;
}
int main() {
    while (scanf("%d%d", &n, &m) == 2 && n && m) solve();
    return 0;
}

欧拉路存在条件(图连通)：
有向图：有一个点入度等于出度加一，有一个点出度等于入度加一，其余所有点入度等于出度
无向图：至多有两个奇点(无向图中奇点个数为奇数)
欧拉回路存在条件(图连通)：
有向图：所有点入度等于出度
无向图：没有奇点

找欧拉回路/欧拉路

poj 2230
题意：在有向图中从1点找出一条欧拉回路并输出经过点。
解：直接搜索标记边是否访问即可。无向图类似，只是标记边一次标两次就行了
代码：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct edge {
    int v, vis;
}ed[100000 + 5];
int n, m, en;
vector<int> G[100000 + 5];
void ins(int x, int y) {
    ed[++en] = (edge){y, 0}, G[x].push_back(en); 
    ed[++en] = (edge){x, 0}, G[y].push_back(en);
}
void clean() {
    en = 0;
    for (int i = 0; i <= 100000; i++) G[i].clear();
}
void dfs(int u) {
    for (int i = 0; i < (int)G[u].size(); i++) {
        edge &a = ed[G[u][i]];
        if (!a.vis) a.vis = 1, dfs(a.v);
    }
    printf("%d\n", u);
}
int solve() {
    clean();
    for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y);
    dfs(1);
    return 0;
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}

混合图欧拉回路

常见题型

1、判断是否有欧拉回路
2、找欧拉回路/欧拉路

------ 本文结束 ------