图论之欧拉图

蔚落 2023-08-17 16:26 297阅读 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 欧拉回路 ***非常经典重要的一道题

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

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

uva 10054

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

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 51
  4. int G[maxn][maxn],du[maxn],m;
  5. int ans[1001][2];//存u,v 
  6. int sum=0; 
  7. void dfs(int u)
  8. {
  9.     for(int i=1;i<=50;i++)
  10.     {
  11.         if(G[u][i]==0)
  12.         continue;
  13.         G[u][i]--;G[i][u]--;
  14.         dfs(i);
  15.         sum++;
  16.         ans[sum][0]=u;
  17.         ans[sum][1]=i;
  18.     }
  19. }
  20. void solve(int t)
  21. {
  22.     int u,v;
  23.     sum=0;
  24.     memset(G,0,sizeof(G));
  25.     memset(du,0,sizeof(du));
  27.     for(int i=1;i<=m;i++)
  28.     {
  29.     scanf("%d %d",&u,&v);
  30.     G[u][v]++;G[v][u]++;
  31.     du[u]++;du[v]++;
  32.     }
  33.     printf("Case #%d\n",t);
  34.     for(int i=1;i<=50;i++)
  35.     {
  36.         if(du[i]%2==1)
  37.         {
  38.         printf("some beads may be lost\n");
  39.         return;
  40.         }
  41.     }
  42.     for(int i=1;i<=50;i++)
  43.     {
  44.         if(du[i])
  45.         {
  46.             dfs(i);
  47.             break;
  48.         }    
  49.     }
  50.     if(sum!=m)
  51.     {
  52.         printf("some beads may be lost\n");
  53.         return;
  54.     }
  55.     for(int i=sum;i>=1;i--)
  56.     printf("%d %d\n",ans[i][0],ans[i][1]);
  57. }
  58. int main()
  59. {
  60.     int T;
  61.     scanf("%d",&T);
  62.     for(int t=1;t<=T;t++)
  63.     {
  64.         scanf("%d",&m);
  65.         solve(t);
  66.         if(t!=T)
  67.         printf("\n");
  68.     }
  69. }

poj 2230—-简单题

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

ContractedBlock.gif ExpandedBlockStart.gif

  1. //#include <bits/stdc++.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<cstdio>
  6. using namespace std;
  7. #define maxn 10006
  8. struct node{
  9.     int v,vis,p;
  10. }G[maxn*10];
  11. int m,n,head[maxn*10],cnt=0,sum=0,ans[maxn*10];
  12. void add(int u,int v)
  13. {
  14.     G[++cnt]=node{v,0,head[u]};
  15.     head[u]=cnt;
  16. }
  17. void dfs(int u)
  18. {
  19.     for(int i=head[u];i!=-1;i=head[u])
  20.     {
  21.         head[u]=G[i].p;
  22.         if(G[i].vis)
  23.         continue;
  24.         G[i].vis=1;
  25.         dfs(G[i].v);
  26.         ans[++sum]=G[i].v;
  27.     }
  28. }
  29. int main()
  30. {
  31.     int u,v;
  32.     scanf("%d%d",&n,&m);
  33.     memset(head,-1,sizeof(head));
  34.     for(int i=1;i<=m;i++)
  35.     {
  36.         scanf("%d%d",&u,&v);
  37.         add(u,v);add(v,u);
  38.     }
  39.     dfs(1);//题目要求开始和结束都为1 
  40.     ans[++sum]=1;    
  41.     if(sum==m*2+1)
  42.     {
  43.     for(int i=1;i<=sum;i++)
  44.     cout<<ans[i]<<endl;
  45.     }    
  46. }

luogu1341 无序字母对

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

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 700
  4. int  inn[maxn],sum=0;
  5. int s[maxn], G[maxn][maxn];
  7. int judge(char x){
  8.     if(x<='z'&&x>='a') return x-'a'+27;
  9.     else return x-'A'+1;
  10. }
  11. void Eular(int x){
  12.     for(int i=1;i<=52;i++)
  13.         if(G[x][i]){
  14.             G[x][i]=G[i][x]=0;
  15.             Eular(i);
  16.         }
  17.     s[++sum]=x;
  18. }
  19. int main(){
  20.     int n,cnt=0;
  21.     cin>>n;
  22.     int u,v;
  23.     char ss[5];
  24.     memset(inn,0,sizeof(inn));
  25.     for(int i=1;i<=n;i++){
  26.         scanf("%s",ss);          
  27.         u=judge(ss[0]);v=judge(ss[1]);
  28.         inn[u]++; inn[v]++;
  29.         G[u][v]=1;G[v][u]=1;
  30.     }
  31.     int p=2e9;//改一下 
  32.     for(int i=1;i<=52;i++){
  33.         if(inn[i]&1){
  34.             p=min(p,i); ++cnt;
  35.         }
  36.     }
  37.     if(cnt!=0 && cnt!=2){
  38.         printf("No Solution\n"); return 0;
  39.     }
  40.     if(cnt==0)
  41.     {
  42.         for(int i=1;i<=52;i++) 
  43.         if(inn[i]){
  44.         p=i; break;
  45.     }
  46.     }
  47.     sum=0; 
  48.     Eular(p);
  49.     for(int i=sum;i>=1;i--) 
  50.     {
  51.         int x=s[i];char ch;
  52.         if(x<=26) ch='A'+x-1;
  53.         else    ch='a'+x-27;
  54.         printf("%c",ch);
  55.     }
  56.     return 0;    
  57. }

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

发表评论

表情：
评论列表 （有 0 条评论，297人围观）

还没有评论，来说两句吧...

相关阅读

    相关 图论之欧拉图

    欧拉路径/欧拉回路 欧拉路径是一条经过图中所有边且只经过一次的路径（类似于一笔画问题）； 欧拉回路的话就是起点和终点相同的欧拉路径 欧拉通路（欧拉路径）：S点到T点的

    蔚落蔚落/ 0 赞/ 298 阅读