定义
哈密顿路径Hamiltonian path,指只经过图中所有点一次的路径。
判定
Dirac定理(充分条件):有n个顶点的无向图,若所有顶点的度数大于等于\lceil\frac{n}{2}\rceil则哈密顿路径存在。
可使用抽屉原理证明。
最短哈密顿路径
NPC问题,容易想到暴力做法是有n!种走法,对每种走法求哈密顿路径再取min,时间复杂度O(n*n!)。
这里介绍用的最多的状压dp做法(O(n^2*2^n)好恐怖)。
首先用二进制压缩所有走的情况,如此一来对走法的枚举只需要2^n。然后在枚举的时候使用dp去更新最短路径,用之前走过的点加上走过的点到要走的点之间的路径长度去更新。
#include<iostream>
#include<cstring>
using namespace std;
const int N=20,M=1<<N;
int f[M][N],w[N][N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>w[i][j];
memset(f,0x3f,sizeof f);
f[1][0]=0;
for(int i=0;i<1<<n;i++)
for(int j=0;j<n;j++)
if(i&1<<j)
for(int k=0;k<n;k++)
if(i&1<<k)
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
cout<<f[(1<<n)-1][n-1];
return 0;
}
其实容易想到,在两次枚举时只枚举包含在i的情况中的点就可以了,可以缩小那个n^2,但是写起来有点烦。使用lowbit思想。
竞赛图上构造哈密顿路径
竞赛图Tournament Graph:一个有向图满足任何两点间均有边连接。
CF上做到了这个的裸题。
定理:N阶(N\geqslant 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)两点之间的弧为<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)的弧为<V(k+1),V(i)>,则构造哈密顿路径V(k+1), V1, V2, …, Vk.
Q.E.D.
Comments | NOTHING