转：http://imlazy.ycool.com/post.2072698.html
Dirac 定理：设一个无向图中有 N 个节点，若所有节点的度数都大于等于 N/2，则汉密尔顿回路一定存在。注意，“N/2” 中的除法不是整除，而是实数除法。如果 N 是偶数，当然没有歧义；如果 N 是奇数，则该条件中的 “N/2” 等价于 “⌈N/2⌉”。
证明起来不难。首先可以证明图一定是连通的。设 d(v) 表示节点 v 的度数。对于任意两个节点 u、 v，若它们不相邻，则可能和它们相邻的节点共有 N - 2 个，而 d(u) + d(v) ≥ N/2 + N/2 ≥ N，那么根据鸽巢原理，肯定存在一个节点与 u 和 v 都相邻。即证，任何两个节点之间都是连通的。
接下来，证明汉密尔顿回路存在的过程其实就是构造这条回路的过程，分成以下几个步骤：
| 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。 |
在整个构造过程中，如果说每次到步骤 4 算是一轮的话，那么由于每一轮当中，至少有一个节点被加入到路径 S → T 中来，所以总的轮数肯定不超过 N 轮。实际上，不难看出该算法的复杂度就是 O(N2)，因为总共扩展了 N 步路径，每步扩展最多枚举所有的节点。
Source Code
Problem: 2438 User: 1013101127
Memory: 848K Time: 141MS
Language: C++ Result: Accepted
Source Code
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 410;
int mp[N][N];
int ans[N];
int vis[N];
int start;
int end;
int n,m;
int cnt;
void init()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)mp[i][j]=0;
else mp[i][j]=1;
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
cnt=0;
}
void Reverse(int s,int e)
{
while(s<e)
{
swap(ans[s],ans[e]);
s++;
e--;
}
}
void kuozhan()
{
while(1)
{
int flag=0;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&mp[end][i])
{
ans[cnt++]=i;
end=i;
vis[i]=1;
flag=1;
break;
}
}
if(!flag)
break;
}
}
void hamiltun()
{
start=1;
for(int i=1;i<=n;i++)
if(mp[1][i]){
end=i;break;
}
vis[start]=1;
vis[end]=1;
ans[0]=start;
ans[1]=end;
cnt=2;
while(1)
{
kuozhan();
Reverse(0,cnt-1);
swap(start,end);
kuozhan();
int mid=0;
if(!mp[start][end])
{
for(int i=1;i<cnt-2;i++)
{
if(mp[ans[i]][end]&&mp[ans[i+1]][start])
{
mid=i+1;
break;
}
}
Reverse(mid,cnt-1);
end=ans[cnt-1];
}
if(cnt==n)break;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
int j;
for(j=1;j<cnt-1;j++)
if(mp[ans[j]][i])
{mid=j;break;}
if(mp[ans[mid]][i]){
end=i;mid=j;break;
}
}
}
start=ans[mid-1];
Reverse(0,mid-1);
Reverse(mid,cnt-1);
ans[cnt++]=end;
vis[end]=1;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n&&!m)break;
n*=2;
int u,v;
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
mp[u][v]=mp[v][u]=0;
}
hamiltun();
cout<<ans[0];
for(int i=1;i<cnt;i++)
printf(" %d",ans[i]);
cout<<endl;
}
return 0;
}