首页 > 代码库 > Hamilton回路的判定与构造
Hamilton回路的判定与构造
定理1：在一个具有n个顶点的无向连通图G中，如果任意两个顶点的度数之和大于n，则G具有Hamilton回路。此条件为充分条件
定理2：设图G = <V,E>，是Hamilton图，则对于v的任意一个非空子集S，若以|S|表示S中元素数目，G-S表示G中删除了S中的点以及与这些点关联的边后得到的子图，则满足G-S的连通分支数W(G-S)<=|S|。此条件为必要条件。
构造Hamilton回路的算法过程，分成以下几个步骤：
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 相邻。证明方法也是根据鸽巢原理，既然与 S 和 T 相邻的点都在该路径上，它们分布的范围只有 v1 ～ vk 这 k 个点， k ≤ N - 2，而 d(S) + d(T) ≥ N，那么可以想像，肯定存在一个与 S 相邻的点 vi 和一个与 T 相邻的点 vj， 满足 j < i。那么上面的命题也就显然成立了。
找到了满足条件的节点 vi 以后，就可以把原路径变成 S → vi+1 → T → vi → S，即形成了一个回路。
4. 现在我们有了一个没有重复节点的回路。如果它的长度为 N，则汉密尔顿回路就找到了。
如果回路的长度小于 N，由于整个图是连通的，所以在该回路上，一定存在一点与回路以外的点相邻。那么从该点处把回路断开，就变回了一条路径。再按照步骤 1 的方法尽量扩展路径，则一定有新的节点被加进来。接着回到步骤 2。
模板题：POJ 2438 or HDU 4337 Childrens Dining
问题是求小朋友围着桌子的座次就是求原图中的一个环，但是要求这个环不能包含所给出的每条边，所以没给出的边却是可以使用的，也就是说本题实际上是在原图的反图上求一个环，即在每两个可以坐在相邻位置的小朋友连一条边，否则不连。使得该环包含所有顶点，即Hamilton回路。
由于有2n个小朋友，且每个小朋友的敌人最多n-1个，所以，每个小朋友可以一起与座的小朋友最少有n+1个，即度数>=n+1，所以任意两个小朋友度数之和d(u)+d(v)>=2n+2 > 2n，所以Hamilton回路存在。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 407 int vis[N],mp[N][N],ans[N]; int n,m; void init() { for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { if(i == j) mp[i][j] = 0; else mp[i][j] = 1; } } memset(ans,0,sizeof(ans)); } void reverse(int ans[N],int s,int t) //将ans数组中s到t的部分倒置 { int tmp; while(s < t) { swap(ans[s],ans[t]); s++; t--; } } void Hamilton() { int s = 1,t; //初始化s取1号点 int k = 2; int i,j,w,tmp; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { if(mp[s][i]) break; } t = i; //取任意连接s的点为t vis[s] = vis[t] = 1; ans[0] = s; ans[1] = t; while(1) { //从t向外扩展 while(1) { for(i=1;i<=n;i++) { if(mp[t][i] && !vis[i]) { ans[k++] = i; vis[i] = 1; t = i; break; } } if(i > n) break; } //将当前得到的序列倒置，s和t互换，从t继续扩展，相当于在原来的序列上从s扩展 w = k - 1; i = 0; reverse(ans,i,w); swap(s,t); //从新的t向外扩展，相当于在原来的序列上从s向外扩展 while(1) { for(i=1;i<=n;i++) { if(mp[t][i] && !vis[i]) { ans[k++] = i; vis[i] = 1; t = i; break; } } if(i > n) break; } if(!mp[s][t]) //如果s和t不相邻，进行调整 { for(i=1;i<k-2;i++) { if(mp[ans[i]][t] && mp[s][ans[i+1]]) //取序列中一点i，使得ans[i]与t相连接且ans[i+1]与s相连 break; } //将从ans[i+1]到t部分的ans[]倒置 w = k - 1; i++; t = ans[i]; reverse(ans,i,w); } //如果当前s和t相连 if(k == n) //如果当前序列中包含n个元素，算法结束 return; //当前序列中的元素个数小于n，寻找点ans[i]，使得ans[i]与ans[]外一点相连 for(j=1;j<=n;j++) { if(vis[j]) continue; for(i=1;i<k-2;i++) if(mp[ans[i]][j]) break; if(mp[ans[i]][j]) break; } s = ans[i-1]; t = j; reverse(ans,0,i-1); //将ans[]中s到ans[i-1]部分的ans[]倒置 reverse(ans,i,k-1); //将ans[]中ans[i]到t的部分倒置 ans[k++] = j; //将点j加入到ans[]的尾部 vis[j] = 1; } } int main() { int i,j; int a,b; while(scanf("%d%d",&n,&m)!=EOF && (n||m)) { n *= 2; init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); mp[a][b] = mp[b][a] = 0; //建立反图 } Hamilton(); printf("%d",ans[0]); for(i=1;i<n;i++) printf(" %d",ans[i]); printf("\n"); } return 0; }