必威体育Betway必威体育官网
当前位置:首页 > IT技术

欧拉图知识点详解

时间:2019-10-13 21:43:19来源:IT技术作者:seo实验室小编阅读:76次「手机版」
 

欧拉图

讲的比较好的博客:https://www.cnblogs.com/zdblog/articles/3725858.html

文章目录

    • 预备知识点
    • 无向图
      • 定理
      • 推论
    • 有向图
      • 定理
      • 推论
    • 模板
      • 题目链接
      • 题意
      • 题解
      • 代码

预备知识点

欧拉通路: 通过图中每条边且只通过一次,并且经过每一顶点的

欧拉回路: 通过图中每条边且只通过一次,并且经过每一顶点的

有向图的基图:忽略有向图所有边的方向,得到的无向图称为该有向图的基图

具有欧拉回路的无向图G成为欧拉图


无向图

定理

无向图G存在欧拉通路的充要条件是:G为连通图,并且G仅有个奇度结点或者奇度结点。

推论

  1. 当G是仅有两个奇度结点的连通图时,G的欧拉通路必以此两个结点为端点;
  2. 当G是无奇度结点的连通图时,G必有欧拉回路;
  3. G为欧拉图(存在欧拉回路)的充分必要条件是 G为无奇度结点的连通图;

有向图

定理

有向图D存在欧拉通路的充要条件是:D为有向图,D的基图连通,并且所有顶点的出度与入度相等;或者除两个顶点外,其余顶点的出度与入度都相等,而这两个顶点中一个顶点的出度与入度之差为1,另一个顶点的出度与入度之差为-1.

推论

  1. 当D除出、入度之差为1,-1的两个顶点之外,其余顶点的出度与入度相等时,D的有向欧拉通路必以出、入度之差为1的顶点作为始点,以出、入度之差为-1的顶点作为终点;
  2. 当D的所有顶点的出、入度都相等时,D中存在有向欧拉回路;
  3. 有向图D为有向欧拉图的充要条件是 D的基图为连通图,并且所有顶点的出、入度都相等。

有向图和无向图大体一致,核心点都在于入读为奇数的点的个数为0或2。

模板题

题目链接

洛谷 P1341

题意

给定一个无向图,要求一个字典序最小的欧拉回路。

如果不存在欧拉通路,输出“No Solution”。

题解

根据这是一个无向图,直接用邻接矩阵存图,然后计算每个顶点的度。

如果存在欧拉通路的话,那么度数为奇的点数量肯定为0或2。

0的情况:整张图是一个环,直接让起点的字典序相对小即可;

2的情况: 出发点只有可能是2个,那么这2个点字典序哪个小就从哪开始。

求欧拉通路序列的方法:dfs遍历,走过的边删边处理即可(详情见代码)。


代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 505;

int n,m,cnt[maxn],g[maxn][maxn],a,b;
string s;
vector<int> e[maxn],path;
bool v[maxn],flag;

bool check() {
    int res = 0;
    for(int i=1;i<=52;i++) {
        if(cnt[i]&1) res++;
    }
    if(res==2) {
        for(int i=1;i<=52;i++) {
            flag = 0;
            if(cnt[i]&1) {
                a = i;
                break;
            }
        }
    }
    if(res==0) {
        for(int i=1;i<=52;i++) {
            flag = 1;
            if(cnt[i]) {
                a  = i;
                break;
            }
        }
    }
    if(res==2 || res==0) return true;
    return false;
}

void dfs(int x) {
    for(int i=1;i<=52;i++) {
        if(g[x][i]) {
            g[x][i] = g[i][x] = 0;
            dfs(i);
        }
    }
    path.push_back(x);
}

char exec(int x) {
    if(x>=1 && x<=26)
        return 'A'+x-1;
    return 'a' + (x-26) -1;
}

int main() {
    cin>>m;
    for(int i=0;i<m;i++) {
        cin>>s;
        int x,y;
        if(s[0]>='a' && s[0]<='z') {
            x = s[0]-'a' + 26;
        }
        else {
            x = s[0]-'A';
        }
        if(s[1]>='a' && s[1]<='z') {
            y = s[1]-'a' + 26;
        }
        else {
            y = s[1]-'A';
        }
        x++, y++;
        g[x][y] = g[y][x] = 1;
        cnt[x]++, cnt[y]++;
    }
    if(!check()) {
        cout<<"No Solution"<<endl;
        return 0;
    }
    dfs(a);
    reverse(path.begin(),path.end());
    for(int i=0;i<path.size();i++) {
        cout<<exec(path[i]);
    }
    return 0;
}

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读