哈密顿通路:G经过图中每个顶点一次且仅一次的通路

哈密顿回路:G经过图中每个顶点一次且仅一次的回路

哈密顿图:存在哈密顿图

哈密顿图的特性:

1 一定是连通图

2 是初级通路,初级回路 (通路(回路)中所有结点不同,边也不同)

3 存在哈密顿回路一定有哈密顿通路,反之不一定

哈密顿图的必要条件:

P(G-V1) <= |V1| 减去V1个顶点的连通分支小于等于V1顶点的个数

推论:有割点的图一定不是哈密顿图

无向图哈密顿涂的充分条件:

设G是n(n>=3)的无向简单图,对于G中一对不相邻的顶点u,v均有

d(u)+d(v) >= n-1 则G中存在哈密顿通路, 又若

d(u)+d(v) >= n , 则G中存在哈密顿回路

推论: G是n(n>=3)阶无向简单图,如果任一顶点V>=n/2,则G是哈密顿图

注意这是充分条件,不满足充分条件任然可以是哈密顿图,如 正六边形

其他判定方法:

方法一 删除高度数点,必要条件判定

方法二 反证法

方法3 AB标记法

有向图中哈密顿通路:

n>=2阶的有向图中,如果略去所有方向,所得无向图中含生成子图Kn,则D中存在哈密顿图