欧拉图&哈密顿图详解

欧拉图

• 存在欧拉回路的无向图被称为欧拉图。
• 有欧拉通路,但无欧拉回路的图被称为半欧拉图。
• 欧拉回路：若存在一条从起点S出发的路径，每条边恰好只走一次，最终回到起点S。
• 欧拉路径：若存在一条从起点S出发的路径，经过每条边一次，但是不要求回到起点S。(类似一笔画)

欧拉回路和欧拉路径的判断

根据顶点的度数来判断（关于顶点的度数讲拓扑排序的时候已经说了—>拓扑排序）

• 有向图的欧拉回路：每个点的入度和出度都要相等
• 有向图的欧拉路径：起点度-1 终点度是1 其余点 为0
• 无向图的欧拉回路：每个点的度都是偶数
• 无向图的欧拉路径：只有两个点的度是奇数

前提：图是连通的。 

如果题中没有要求输出欧拉路径，那么只根据

                                                                                       图连通+节点度数判断   

来判断欧拉图是否存在。 

比如POJ-1386

有向图度数判断的简单示范，这个不算是模板，具体题目，具体分析。

数组out，in 来存节点的入度和出度，if来判断。

/* 欧拉路径 题意：盘子上都写了个字，盘子必须按照一定的顺序排列，排序的规则是每个单词的开头与上一个单词的结尾字母相同 要判断所有的盘子是否能按照上述的规则排序 并查集+欧拉路 判断 ps:并查集判断连通性 这里构造图看成有向图 -----> 有向图判断存在欧拉回路或欧拉通路的条件是 只存在这样两个点：一个点入度等于出度+1，另一个点入度=出度-1，其他每个点入度都等于出度，或者每个点入度都等于出度。 */ #include 
  
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         
        
       
      
     
    
  

求欧拉回路的方法

       使用深度优先搜索dfs。如果某条边被搜索到，则标记这条边为已选择，并且即使回溯也不能将当前边的状态改回未选择，每次回溯时，记录回溯路径。深度优先搜索结束后，记录的路径就是欧拉回路，最后反向输出。

比如：POJ-2337

/* 连通+存在欧拉路(每个节点入度=出度 或者 除两个节点(入度-出度=-1 入度-出度=1)外，其他节点入度=出度) 如果满足 in-out == -1 的话 就一定是顶点 因为这道题需要输出字典序最小的，那么得先给他排序，按照字典序从小到大排，这样就能保证在 条件都满足的情况下 的输出顺序 */ #include 
  
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define ll long long #define inf 0x3f3f3f3f #define Max 1020 using namespace std; string str[Max]; int vis[Max],ans[Max]; int in[30],out[30],head[30]; int t,n,u,v,cnt,tot,st; struct Node { int to,nex; int index; }edge[Max]; void init() { cnt=0,tot=0; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(head,-1,sizeof(head)); memset(ans,0,sizeof(ans)); memset(vis,0,sizeof(vis)); } //注意是反向建边 void add_edge(int u,int v,int index) { edge[tot].to=v; edge[tot].nex=head[u]; edge[tot].index=index; head[u]=tot++; } //dfs 欧拉回路输出 void dfs(int u) { for(int v=head[u];~v;v=edge[v].nex) { if(!vis[v]) { vis[v]=1; dfs(edge[v].to); ans[cnt++]=edge[v].index; } } } int main() { ios::sync_with_stdio(false); cin>>t; while(t--) { init(); cin>>n; for(int i=0;i 
        
          >str[i]; sort(str,str+n); st=inf; //这里是反向存储 则反反得正 for(int i=n-1;i>=0;i--) { int len=str[i].length(); u=str[i][0]-'a',v=str[i][len-1]-'a'; in[v]++,out[u]++; add_edge(u,v,i); st=min(u,v);//针对欧拉回路 } int cnt1=0,cnt2=0,num=0; for(int i=0;i<26;i++) { if(!in[i]&&!out[i]) continue; if(in[i]!=out[i]) num++;//统计入度!=出度的点的个数 用于回路和路径的区别 if(in[i]-out[i]==1) //进-出-> 1 终点 { cnt1++;} else if(in[i]-out[i]==-1) // 进-出-> -1 起点 { cnt2++; st=i; } } //st 必须只改变一次 且为最小 if(num>0) { //不是欧拉回路 也不是 欧拉路径 if(!(cnt1==1&&cnt2==1&&num==2)) { cout<<"*"< 
         
           =0;i--) { cout< 
           
          
         
        
       
      
     
    
  

为什么要排序呢？因为链式向前星存储是按照你排好的顺序存储，而且遍历的时候也是按照顺序遍历。

真不懂看看下边，再不懂复习链式向前星https://blog.csdn.net/_/article/details/#comments

有关欧拉图的其他题：

HDU-1878

/* 欧拉回路 无向图 判断 连通+度数为偶数 !!!!!注意初始化…… */ #include 
  
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define Max 1002 #define ll long long using namespace std; // int vis[Max]; int deg[Max]; int fa[Max]; int n,m,u,v; void init() { // memset(vis,0,sizeof(vis)); memset(deg,0,sizeof(deg)); for(int i=1;i<=n;i++) fa[i]=i; } int Find(int x) { if(x==fa[x]) return x; else return fa[x]=Find(fa[x]); } void mix(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx!=fy) { fa[fx]=fy; } } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); ios::sync_with_stdio(false); while(cin>>n){ if(n==0) break; init(); //remember cin>>m; for(int i=0;i 
        
          >u>>v; deg[u]++,deg[v]++; mix(u,v);//合并 } int flag=false; int cnt=0; //判断连通性 for(int i=1;i<=n;i++) { if(fa[i]==i) cnt++; //祖先数量 if(deg[i]%2!=0) { flag=true; } } if(flag||cnt!=1) cout<<"0"< 
          
         
        
       
      
     
    
  

//DFS判断连通 #include 
  
    #include 
   
     #define Max 1002 using namespace std; int mapp[Max][Max]; int vis[Max]; int deg[Max]; int n,m,u,v; void init() { memset(mapp,0,sizeof(mapp)); memset(vis,0,sizeof(vis)); memset(deg,0,sizeof(deg)); } void dfs(int u) { vis[u]=1; for(int v=1;v<=n;v++) { if(mapp[u][v]&&!vis[v]) { dfs(v); } } } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); ios::sync_with_stdio(false); while(cin>>n) { if(n==0) break; init(); cin>>m; for(int i=0;i 
    
      >u>>v; mapp[u][v]=mapp[v][u]=1; deg[u]++,deg[v]++; } dfs(1); bool flag=false; for(int i=1;i<=n;i++) { if(!vis[i]) { flag=true; break; } if(deg[i]%2!=0) { flag=true; break; } } if(flag) cout<<"0"< 
      
     
    
  

HDU-3018

/* They intend to visit every road , and every road must be visited for exact one time. No two roads will be the same,and there is no road connecting the same town. 目标：访问每一个城镇，并且每条路(边)经过一次且路只有一条 一个大组被分成几个小组 来访问城镇 求至少分几个组，才能实现目标 就比如：一笔画问题：需要几笔才能把所有边都画完 hint:没有一条路与某一结点相连接，小蚂蚁就会忘记这个结点 ans=欧拉路的个数+连通图中度数为奇的个数/2 why? https://blog.csdn.net/u0/article/details/ */ #include 
  
    #define Max using namespace std; int n,m,u,v,cnt; int deg[Max],odd[Max],fa[Max]; int vis[Max]; vector 
   
     vec;//存储父节点 可以判断有多少个连通块 void init() { vec.clear(); for(int i=1;i<=n;i++) fa[i]=i; memset(deg,0,sizeof(deg)); memset(odd,0,sizeof(odd)); memset(vis,0,sizeof(vis)); } int Find(int x) { if(fa[x]==x) return x; return fa[x]=Find(fa[x]); } void mix(int x,int y) { int fx=Find(x); int fy=Find(y); if(fx!=fy) { fa[fx]=fy; } } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); ios::sync_with_stdio(false); while(cin>>n>>m) { init(); for(int i=0;i 
    
      >u>>v; deg[u]++,deg[v]++; mix(u,v); } //找连通块 for(int i=1;i<=n;i++) { int fi=Find(i); if(!vis[fi]) { vec.push_back(fi);// 有几个祖先就有几个连通块 vis[fi]=1; } if(deg[i]%2) odd[fi]++; // 存储祖先是fi的图中的奇度数的点 } cnt=0; vector 
     
       ::iterator it; for(it=vec.begin();it!=vec.end();it++){ // cout<<"-> "<<(*it)< 
       
      
     
    
  

POJ-1041

/* the best way to do it was to travel through each street of town only once. Naturally, he wanted to finish his trip at the same place he started, 经过每个街道且一次，最后回到原点 Assume that Johnny lives at the junction ending the street appears first in the input with smaller number. 以第一个输入的最小的junction作为起点 If there was more than one such round trip, he would have chosen the one which, when written down as a sequence of street numbers is lexicographically the smallest. 如果有多个 就输出 字典序 最小的街道号序列 题目保证是 无向连通图 x和y构成了边z,问是否构成欧拉回路，如果存在，就输出字典序最小的那条欧拉回路 */ #include 
  
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #define Maxn 66 #define Maxm 2222 using namespace std; int n,m,x,y,z,cnt,st; int deg[Maxn],vis[Maxm],ans[Maxm]; struct Node { int u,v; }edge[Maxm]; void init() { cnt=0,n=0,m=0,cnt=0,st=0; memset(deg,0,sizeof(deg)); memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); } void dfs(int s) { for(int i=1;i<=m;i++) { if(!vis[i]&&((edge[i].u==s)||(edge[i].v==s))) { vis[i]=1; dfs(edge[i].u+edge[i].v-s); //!减去一个相同的 剩下的就是需要继续搜的 ans[cnt++]=i;//存的是边的编号 } } } // if(!vis[i]&&(edge[i].u==s)) // { // vis[i]=1; // dfs_fleury(edge[i].v); // ans[cnt++]=i; // } // if(!vis[i]&&(edge[i].v==s)) // { // vis[i]=1; // dfs_fleury(edge[i].u); // ans[cnt++]=i; // } int main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); // ios::sync_with_stdio(false); while(scanf("%d%d",&x,&y)&&x&&y) { init(); st=min(x,y); do{ scanf("%d",&z); edge[z].u=x,edge[z].v=y; deg[x]++,deg[y]++; m++;//边 n=max(n,max(x,y));//顶点 }while(scanf("%d%d",&x,&y)&&x&&y); bool flag=false; for(int i=1;i<=n;i++) { if(deg[i]%2){flag=true;break;} } if(flag) { printf("Round trip does not exist.\n"); continue; } dfs(st); for(int i=cnt-1;i>=0;i--) { printf("%d",ans[i]); if(i!=0) cout<<" "; else cout< 
           
          
         
        
       
      
     
    
  

哈密顿图

• 1、哈密顿回路：除了经过初始结点两次以外，通过图G的每个节点一次且仅一次的回路
• 2、哈密顿通路：通过图G的每个节点一次且仅一次 的 通路
• 3、哈密顿图：含有哈密顿回路的图
• 4、竞赛图：有向完全图，(任意两个顶点之间恰好有一条有向边.)

算法一:
在Dirac定理的前提下构造哈密顿回路

过程：

1:任意找两个相邻的节点S和T,在其基础上扩展出一条尽量长的没有重复结点的路径.即如果S与结点v相邻,而且v不在路径S -> T上,则可以把该路径变成v -> S -> T,然后v成为新的S.从S和T分别向两头扩展,直到无法继续扩展为止,即所有与S或T相邻的节点都在路径S -> T上.　　

2:若S与T相邻,则路径S -> T形成了一个回路.　　

3:若S与T不相邻,可以构造出来一个回路.设路径S -> T上有k+2个节点,依次为S, v1, v2, …, vk, T.可以证明存在节点vi(i属于[1, k]),满足vi与T相邻,且vi+1与S相邻.找到这个节点vi,把原路径变成S -> vi -> T -> vi+1 ,即形成了一个回路.　　

4:到此为止,已经构造出来了一个没有重复节点的的回路,如果其长度为N,则哈密顿回路就找到了.如果回路的长度小于N,由于整个图是连通的,所以在该回路上,一定存在一点与回路之外的点相邻.那么从该点处把回路断开,就变回了一条路径,同时还可以将与之相邻的点加入路径.再按照步骤1的方法尽量扩展路径,则一定有新的节点被加进来.接着回到路径2.

模板题：

HDU-4337

/* 题意：n个点m条无向边,输出一条哈密顿回路 every knight has at least (N + 1) / 2 other knights as his close friends.这句话其实是保证了哈密顿回路的存在性 基于定理Dirac：当所有点相连的点的个数大于N/2时，一定可以构造出一条哈密顿回路 STEP1:先找两个相邻点s-t，扩充出一条链直到到不能扩充为止。 STEP2:这时如果s-t不相邻，在链上找一点vi满足s与next[vi]相邻并且vi与t相邻，链转化为s-vi-t-next[vi]-s STEP3:如果链中的点不足N个，就在环上开一个新口继续加点，重复STEP1~3即可。 */ #include 
  
    #define Max 202 using namespace std; int n, m; int mp[Max][Max],vis[Max]; int S, T, cnt, ans[Max]; //转置 void _reverse(int l,int r) { while (l 
   
     "< 
    
      "< 
     
       "< 
      
        >n>>m) { memset(mp, 0, sizeof mp); for (int i = 1, u, v; i <= m; i++) { scanf("%d %d",&u, &v); mp[u][v] = mp[v][u] = 1; } hamiltun(1); for (int i = 0; i < cnt; i++) printf("%d%c", ans[i], i==cnt-1?'\n':' '); } return 0; } 
       
      
     
    
  

dfs:

/* every knight has at least (N + 1) / 2 other knights as his close friends.这句话其实是保证了哈密顿回路的存在性 基于定理Dirac：当所有点相连的点的个数大于N/2时，一定可以构造出一条哈密顿回路 */ #include 
  
    #define Max 202 using namespace std; int vis[Max],mapp[Max][Max],ans[Max]; int n,m,u,v,flag; void dfs(int u,int cnt) { if(flag) return ; if(cnt==n) { if(mapp[1][ans[n-1]]) { for(int i=0;i 
   
     >n>>m) { memset(vis,0,sizeof(vis)); memset(mapp,0,sizeof(mapp)); memset(ans,0,sizeof(ans)); for(int i=0;i 
    
      >u>>v; mapp[u][v]=mapp[v][u]=1; } flag=0; ans[0]=1; vis[1]=1; dfs(1,1); if(!flag) cout<<"no solution"< 
      
     
    
  

算法二:
N(N>=2)阶竞赛图构造哈密顿通路

方法思路：其实就是找点加点的过程。

竞赛图构造哈密顿路时的算法同以下证明过程.à

数学归纳法证明竞赛图在n >= 2时必存在哈密顿路:

(1)n = 2时结论显然成立；

(2)假设n = k时,结论也成立,哈密顿路为V1, V2, V3, …, Vk;

  设当n = k+1时,第k + 1个节点为V(k+1),考虑到V(k+1)与Vi(1<=i<=k)的连通情况,可以分为以下两种情况.

    1:Vk与V(k+1)两点之间的弧为<Vk, V(k+1)>,则可构造哈密顿路径V1, V2,…, Vk, V(k+1).

    2:Vk与V(k+1)两点之间的弧为
Vk>,则从后往前寻找第一个出现的Vi(i=k-1,i>=1,–i),满足Vi与V(k+1)之间的弧为<Vi,V(k+1)>,则构造哈密顿路径V1, V2, …, Vi, V(k+1), V(i+1), …, V(k).若没找到满足条件的Vi,则说明对于所有的Vi(1<=i<=k)到V(k+1)的弧为
i)>,则构造哈密顿路径V(k+1), V1, V2, …, Vk.

模板题：

POJ-1776

#include 
  
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #define ll long long #define Max 1002 using namespace std; int mapp[Max][Max],ans[Max]; int n; inline void read(int& a) { char c; while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0'; while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0'; } //插入 void Insert(int arv[],int &len,int index,int key) { if(index>len) index=len; len++; for(int i=len-1;i>=0;i--) { if(i!=index&&i) { arv[i]=arv[i-1]; }else { arv[i]=key; return ; } } } /* 假设两个点已经构成哈密顿，现在加入第三个点， 由竞赛图知道，第三个点与前面两个点肯定可以构成哈密顿，然后第四个点，，，，就这样做完所有点。 */ void Hamilton(int n) { int ansi=1; ans[ansi++]=1;//第一个点加入哈密顿图序列中 for(int i=2;i<=n;i++)//遍历尚未加入哈密顿图的点 { //if(mapp[i][ans[ansi-1]]==1) //第一种情况,直接把当前点添加到序列末尾 if(mapp[ans[ansi-1]][i]==1) //倒过来也可以 { ans[ansi++]=i; }else{ int flag=0; //当前序列(哈密顿图的遍历序列)从后往前找第一个满足条件的点j,使得存在 
          
            且 
           
             for(int j=ansi-2;j>0;j--) { // if(mapp[i][ans[j]]==1) if(mapp[ans[j]][i]==1) { flag=1; Insert(ans,ansi,j+1,i); break; } } //否则说明所有点都邻接自点i,则把该点直接插入到序列首段 if(!flag) { Insert(ans,ansi,1,i); } } } } int main() { while(scanf("%d",&n)!=EOF) { memset(mapp,0,sizeof(mapp)); memset(ans,0,sizeof(ans)); int op; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { // scanf("%d",&op); //TLE read(op); if(op) mapp[i][j]=1; } } printf("%d\n%d\n",1,n); Hamilton(n); for(int i=1;i<=n;i++){ printf(i==1?"%d":" %d",ans[i]); } printf("\n"); } return 0; } 
            
           
          
         
        
       
      
     
    
  

HDU-3414

/* then go to every scenic spots once and only once and finally return to the starting spot. 要求：经过所有景点一次且仅一次，最后回到原点--->哈密顿回路 路径输出 any two scenic spots have been connected by ONE road directly 任意两个景点直接被一条路连接->(竞赛图哦) 注意：竞赛图中一定存在哈密顿路径，不一定存在哈密顿回路 任务：安排旅游路线，满足游客要求 方法：枚举所有起点，构造哈密顿路径，然后判断起点和终点是否相同 */ #include 
  
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #define Max 1002 int mapp[Max][Max]; int ans[Max],n,cnt; int nex[Max]; //另一种写法可以改变起点 int Hamilton(int st) { cnt=1; memset(nex,-1,sizeof(nex)); int head=st,tail=st; for(int i=1;i<=n;i++) { if(i==st) continue; if(mapp[i][head])//直接插入 { nex[i]=head; head=i; }else { //找到合适的位置插入 int pre=head,pos=nex[head]; while(pos!=-1&&mapp[pos][i]){ pre=pos; pos=nex[pos]; } //pre->i>pos nex[pre]=i; nex[i]=pos; if(pos==-1) tail=i; } } if(mapp[tail][head]) { for(int i=head;~i;i=nex[i]) ans[cnt++]=i; return true; } return false; } bool solve() { for(int i=1;i<=n;i++) if(Hamilton(i)) return true; return false; } int main() { while(scanf("%d",&n),n){ memset(mapp,0,sizeof(mapp)); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ // read(mapp[i][j]); scanf("%d",&mapp[i][j]); } } bool flag=solve(); if(n==1){ printf("1\n"); }else { if(flag) { for(int i=1;i<=n;i++) { if(i!=1) printf(" "); printf("%d",ans[i]); } printf("\n"); }else printf("-1\n"); } }return 0; } 
          
         
        
       
      
     
    
  

好的 晚安；