哈密顿路径问题

定义

哈密顿路径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.

施工中