图论之欧拉图

蔚落 2023-08-17 16:26 164阅读 0赞

### 欧拉路径/欧拉回路 ###

欧拉路径是一条经过图中所有边且只经过一次的路径（类似于一笔画问题）；

欧拉回路的话就是起点和终点相同的欧拉路径

**欧拉通路（欧拉路径）**：S点到T点的路径经过图中所有的边，有且仅有一次

**欧拉回路**：就是起点和终点相同的欧拉路径

**欧拉图**：通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路

下图p1,p2都不是欧拉图：因为不存在有一条路径能通过所有边且边只经过一次

![1445562-20190826183530310-1672693621.png][]

而下图可以被称为欧拉图：

![1445562-20190826183704231-1939220854.png][]

**性质**  
1.无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)；

2.无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点；

3.有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度；

4.有向连通图 D 含有欧拉通路，当且仅当该图为连通图且 D 中除两个结点外，其余每个结点的入度=出度，且此两点满足 deg-(u)-deg+(v)=±1 。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的

入度=出度）；

5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环；

6.如果图G是欧拉图且 H = G-uv，则 H 有奇数个 u,v-迹仅在最后访问 v ；同时，在这一序列的 u,v-迹中，不是路径的迹的条数是偶数。

**求法**

对于**无向图**满足以下条件说明该图为**无向欧拉图**

1.图中的所有边的度数都为偶数

2.路径边的数目为图中边的数目

**求法：**

第一步：输入点的数目，边的数目，输入每条边的起点和终点，记录两个点的度数，边的信息

第二步：判断每个点的度数是否为奇数，若存在奇数该图不可能为欧拉图，不存在则继续判断

第三步：找到一个有边的点，从该点作为路径的起点进行dfs

第四步：dfs：进行前向星的遍历，回溯之后记录答案

第五步：判断路径边的数目是否和图中边的数目相等，若不相等该图不为欧拉图，相等则输出欧拉路径

对于**有向图**满足以下条件说明该图为**有向欧拉图**

1.图中的所有点的入度数等于出度数

2.路径边的数目为图中边的数目

**求法：**

第一步：输入点的数目，边的数目，输入每条边的起点和终点，记录该点的入度数，出度数，边的信息

第二步：判断每个点的入度数是否不等于出度数，若存在不相等该图不可能为欧拉图，都相等则继续判断

第三步：找到一个有边的点，从该点作为路径的起点进行dfs

第四步：dfs：进行前向星的遍历，回溯之后记录答案

第五步：判断路径边的数目是否和图中边的数目相等，若不相等该图不为欧拉图，相等则输出欧拉路径

**例题**

### [UOJ 117 欧拉回路][UOJ 117]    \*\*\*非常经典重要的一道题 ###

题意：求有向图与无向图的欧拉回路，如果存在，**输出欧拉回路（边的序号）**，注意题目中给出的无向图的输出方式

1 //#include<bits/stdc++.h>
      2 #include<iostream>
      3 #include<string>
      4 #include<cstring>
      5 inline int read()   ///快速读入
      6 {
      7     int X=0,w=0;
      8     char ch=0;
      9     while(!isdigit(ch))
     10     {
     11         w|=ch=='-';
     12         ch=getchar();
     13     }
     14     while(isdigit(ch))
     15         X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
     16     return w?-X:X;
     17 }
     18  
     19 int op,n,m;//图的标记，图中点的数目，边的数目 
     20 struct node
     21 {
     22     int e;//终点 
     23     int p;//边的编号 
     24     int vis;///标记这条边是否被访问过
     25 } load[400005];
     26 int head[100005],sign,cnt;//前向星，sign记录此时存图中边数组load存到的边的数目，cnt记录此时存路径点的数组ans存到的边的数目 
     27  
     28 void add_edge(int s,int e) //添加起点s终点e的边 
     29 {
     30     load[++sign]=node{e,head[s],0};
     31     head[s]=sign;
     32 }
     33  
     34 void init()//初始化 
     35 {
     36     cnt=sign=0;
     37     memset(head,-1,sizeof(head));
     38 }
     39  
     40 int ans[200005];//答案数组
     41  
     42 void dfs_unedge(int s)//无向图 
     43 {
     44     for(int i=head[s]; i!=-1; i=head[s])
     45     {
     46         ///目的是为了优化，因为每一条边只访问一次/
     47         ///可以将这条边删除掉，可以降低时间复杂度（否则会T）
     48         head[s]=load[i].p;
     49         
     50         int e=load[i].e;
     51         if(load[i].vis)     ///访问过的边不会再次访问
     52             continue;
     53         ///因为储存的双向边，两条边都需要标记
     54         load[i].vis=1;//标记第一条边
     55         (i&1)?load[i+1].vis=1:load[i-1].vis=1;//标记第二条边 
     56         
     57         dfs_unedge(e);
     58         ans[++cnt]=(i+1)/2; ///回溯(说明已经找到了解)后储存答案
     59         if((i&1)==0)        ///反向走的边变为负值  i是边的序号  无向图存边正向的边序号都是奇数，反向边是在正向边之后存的（所以序号为偶数） 
     60         ans[cnt]*=-1;
     61     }
     62 }
     63  
     64 void solve_unedge()   //无向图欧拉回路
     65 {
     66     int de[100005],s,e;//记录每个点的度数 
     67     memset(de,0,sizeof(de));
     68     n=read();//点的数目 
     69     m=read();//边的数目 
     70     for(int i=1; i<=m; i++)
     71     {
     72         s=read();
     73         e=read();
     74         de[s]++;
     75         de[e]++;
     76         ///建立双向边
     77         add_edge(s,e);
     78         add_edge(e,s);
     79     }
     80     ///对于无向图来说度数为奇数的点个数为0
     81     for(int i=1; i<=n; i++)
     82     {
     83         if(de[i]&1)
     84         {
     85             printf("NO\n");
     86             return ;
     87         }
     88     }
     89     for(int i=1; i<=n; i++)
     90     {
     91         if(de[i])//找一条有边的点去找欧拉回路 
     92         {
     93             dfs_unedge(i);
     94             break;
     95         }
     96     }
     97     if(cnt!=m)//路径边的数目不等于图中所有的边 
     98     {
     99         printf("NO\n");
    100         return ;
    101     }
    102     printf("YES\n");
    103     ///逆序输出，因为方向正负已经决定了
    104     for(int i=cnt; i>=1; i--)//输出图中的欧拉回路
    105         printf("%d ",ans[i]);
    106 }
    107  
    108 void dfs_diredge(int s)  //有向图欧拉回路
    109 {
    110     for(int i=head[s]; i!=-1; i=head[s])
    111     {
    112         head[s]=load[i].p;
    113         int e=load[i].e;
    114         if(load[i].vis)
    115             continue;
    116         load[i].vis=1;
    117         dfs_diredge(e); 
    118         ans[++cnt]=i;//回溯后存答案
    119     }
    120 }
    121  
    122 void solve_diredge()   ///有向图欧拉回路
    123 {
    124     int in[100005],out[100005];
    125     n=read();
    126     m=read();
    127     for(int i=1; i<=n; i++)
    128     in[i]=out[i]=0;
    129     int s,e;
    130     for(int i=1; i<=m; i++)
    131     {
    132         s=read();
    133         e=read();
    134         out[s]++;//起点的出度 
    135         in[e]++;//终点的入度 
    136         add_edge(s,e);
    137     }
    138     ///对于有向图来说每个点的入度必须等于出度。
    139     for(int i=1; i<=n; i++)
    140     {
    141         if(in[i]-out[i])//说明入度出度不相等 
    142         {
    143             printf("NO\n");
    144             return ;
    145         }
    146     }
    147     for(int i=1; i<=n; i++)//找到第一个有边的点 
    148     {
    149         if(head[i]!=-1)
    150         {
    151             dfs_diredge(i);
    152             break;
    153         }
    154     }
    155     if(cnt!=m)//路径里的边的数目不等于图中边的数目 
    156     {
    157         printf("NO\n");
    158         return ;
    159     }
    160     printf("YES\n");
    161     for(int i=cnt; i>=1; i--)//输出图中的欧拉回路 
    162     printf("%d ",ans[i]);
    163 }
    164  
    165 int main()
    166 {
    167     init();///初始化
    168     op=read();//图的种类  1为无向图，2为有向图 
    169     op==1?solve_unedge():solve_diredge();
    170     return 0;
    171 }

** uva 10054**

思路：判断给出的边是否构成欧拉回路，由于点可以重复，且点的数量（<=50）比较小，所以我们直接用50\*50的图去存边的情况

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    #define maxn 51
    int G[maxn][maxn],du[maxn],m;
    int ans[1001][2];//存u,v 
    int sum=0; 
    void dfs(int u)
    {
        for(int i=1;i<=50;i++)
        {
            if(G[u][i]==0)
            continue;
            G[u][i]--;G[i][u]--;
            dfs(i);
            sum++;
            ans[sum][0]=u;
            ans[sum][1]=i;
        }
    }
    void solve(int t)
    {
        int u,v;
        sum=0;
        memset(G,0,sizeof(G));
        memset(du,0,sizeof(du));
        
        for(int i=1;i<=m;i++)
        {
        scanf("%d %d",&u,&v);
        G[u][v]++;G[v][u]++;
        du[u]++;du[v]++;
        }
        printf("Case #%d\n",t);
        for(int i=1;i<=50;i++)
        {
            if(du[i]%2==1)
            {
            printf("some beads may be lost\n");
            return;
            }
        }
        for(int i=1;i<=50;i++)
        {
            if(du[i])
            {
                dfs(i);
                break;
            }    
        }
        if(sum!=m)
        {
            printf("some beads may be lost\n");
            return;
        }
        for(int i=sum;i>=1;i--)
        printf("%d %d\n",ans[i][0],ans[i][1]);
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int t=1;t<=T;t++)
        {
            scanf("%d",&m);
            solve(t);
            if(t!=T)
            printf("\n");
        }
    }

** poj 2230---简单题**

**思路：构建有向图，判断是否为欧拉图**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//#include <bits/stdc++.h>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    #define maxn 10006
    struct node{
        int v,vis,p;
    }G[maxn*10];
    int m,n,head[maxn*10],cnt=0,sum=0,ans[maxn*10];
    void add(int u,int v)
    {
        G[++cnt]=node{v,0,head[u]};
        head[u]=cnt;
    }
    void dfs(int u)
    {
        for(int i=head[u];i!=-1;i=head[u])
        {
            head[u]=G[i].p;
            if(G[i].vis)
            continue;
            G[i].vis=1;
            dfs(G[i].v);
            ans[++sum]=G[i].v;
        }
    }
    int main()
    {
        int u,v;
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        dfs(1);//题目要求开始和结束都为1 
        ans[++sum]=1;    
        if(sum==m*2+1)
        {
        for(int i=1;i<=sum;i++)
        cout<<ans[i]<<endl;
        }    
    }

#### luogu1341 无序字母对 ####

找一个无向图中的字典序最小的欧拉路径。我只要做的时候按照字典序去遍历边就好了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 700
    int  inn[maxn],sum=0;
    int s[maxn], G[maxn][maxn];
    
    int judge(char x){
        if(x<='z'&&x>='a') return x-'a'+27;
        else return x-'A'+1;
    }
    void Eular(int x){
        for(int i=1;i<=52;i++)
            if(G[x][i]){
                G[x][i]=G[i][x]=0;
                Eular(i);
            }
        s[++sum]=x;
    }
    int main(){
        int n,cnt=0;
        cin>>n;
        int u,v;
        char ss[5];
        memset(inn,0,sizeof(inn));
        for(int i=1;i<=n;i++){
            scanf("%s",ss);          
            u=judge(ss[0]);v=judge(ss[1]);
            inn[u]++; inn[v]++;
            G[u][v]=1;G[v][u]=1;
        }
        int p=2e9;//改一下 
        for(int i=1;i<=52;i++){
            if(inn[i]&1){
                p=min(p,i); ++cnt;
            }
        }
        if(cnt!=0 && cnt!=2){
            printf("No Solution\n"); return 0;
        }
        if(cnt==0)
        {
            for(int i=1;i<=52;i++) 
            if(inn[i]){
            p=i; break;
        }
        }
        sum=0; 
        Eular(p);
        for(int i=sum;i>=1;i--) 
        {
            int x=s[i];char ch;
            if(x<=26) ch='A'+x-1;
            else    ch='a'+x-27;
            printf("%c",ch);
        }
        return 0;    
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11414357.html

[1445562-20190826183530310-1672693621.png]: /images/20230810/0de5c62d7e2a4f2188e54d81c7a2780c.png
[1445562-20190826183704231-1939220854.png]: /images/20230810/7d9846e043ef4e82bedc1802686a62fe.png
[UOJ 117]: http://uoj.ac/problem/117
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/b85936df71fc4346b92dd8599c5e78e7.png