哈密顿图的应用

哈密顿通路（回路）与哈密顿图（Hamilton图）通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）。下面总结四个定义，帮助大家理解。

一、哈密顿图定义

通过图中所有顶点一次且仅一次的通路称为哈密顿通路。

通过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图。

具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。

（1）哈密顿通路

设G=《V，E》为一图（无向图或有向图）.G中经过每个顶点一次且仅一次的通路称作哈密顿通路

（2）哈密顿回路

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

（3）哈密顿图

若G中存在哈密顿回路，则称它是哈密顿图

（4）定义详解：

（1）存在哈密顿通路（回路）的图一定是连通图；

（2）哈密顿通路是初级通路，哈密顿回路是初级回路；

（3）若G中存在哈密顿回路，则它一定存在哈密顿通路，反之不真

（4）只有哈密顿通路，无哈密顿回路的图不交哈密顿图；

二、性质

设G=<V ,E>是哈密顿图，则对于V的任意非空真子集V1，均有p(G -V1)≤|V1|。其中p(x)为 x 的连通分支数。

推论：设G=<V ,E>是半哈密顿图，则对于V的任意非空真子集V1，均有p(G -V1)≤|V1|+1 。其中p(x)为 x 的连通分支数。

完全图K2k+1(k≥1)中含 k 条边不重的哈密顿回路，且这 k 条边不重的哈密顿回路含K2k+1中的所有边。

完全图K2k(k≥2)中含k-1条边不重的哈密顿回路，从K2k中删除这k-1条边不重的哈密顿回路后所得图含 k 条互不相邻的边。

三、充分条件

设G是n(n≥2)的无向简单图，若对于G中任意不相邻的顶点，均有，则G中存在哈密顿通路。

推论 1：设G是n(n≥3)的无向简单图，若对于G中任意不相邻的顶点，均有，则G中存在哈密顿回路，从而G为哈密顿图。

推论 2：设G是n(n≥3)的无向简单图，若对于G中任意顶点，均有，则G中存在哈密顿回路，从而G为哈密顿图。

设D为n(n≥2)阶竞赛图，则D具有哈密顿通路。

若D含n(n≥2)阶竞赛图作为子图，则D具有哈密顿通路。

强连通的竞赛图为哈密顿图。

若D含n(n≥2)阶强连通的竞赛图作为子图，则D具有哈密顿回路。