首页 > 代码库 > 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;
}
View Code