一、定义
1.哈密顿通路
设G=
为一图（无向图或有向图）.G中
经过每个顶点一次且仅一次的通路称作哈密顿通路。与欧拉通路类似，一个是通过点，一个是通过边。
2.哈密顿回路
G中经过每个顶点一次且仅一次的回路称作哈密顿回路。哈密顿回路图，与欧拉回路图正好互相呼应，欧拉回路要求通过每条边一次且仅仅一次，而哈密顿回路图则要求通过每个顶点一次且仅仅一次。哈密顿回路图有一个重要的问题：traveling salesperson problem,TSP，就是所谓的 *货郎担* 的问题–>要求在图中发现经过所有顶点且总距离最短的路线。（这里说的距离是路径上所有边的权的总和。而不是路的长度）
3.哈密顿图
若G中存在哈密顿回路，则称它是哈密顿图
4.定义关系：
（1）存在哈密顿通路（回路）的图一定是连通图；
（2）哈密顿通路是初级通路，哈密顿回路是初级回路；
（3）若G中存在哈密顿回路，则它一定存在哈密顿通路，反之不真
（4）只有哈密顿通路，无哈密顿回路的图不交哈密顿图；
二、判定定理
注意：目前没有找到哈密顿图的简单的充要条件
（1）设无向图G=
为哈密顿图，V1是V的任意真子集，则 p(G-V1)<=|V1|
其中，p(G-V1)为G中删除V1后的所得图的联通分支数目，|V1|为V1集合中包含的顶点个数。【哈密顿图存在的必要条件】推论：有割点的图一定不是哈密顿图。设v是图中的割点，则p(G-v)>=2,由上述定理知G不是哈密顿图
（2）设G是n(n>=3)阶无向简单图，若对于G中的每一对不相邻的顶点u,v,均有d(u)+d(v)>=n-1则G中存在哈密顿通路。又若d(u)+d(v)>=n则G中存在哈密顿回路，即G为哈密顿图。【哈密顿图存在的充分条件，不是必要条件】其中d(u),d(v)分别代表顶点u,v的度数。
推论：设G是n(n>=3)阶无向简单图，若G的最小度>=n/2,则G是哈密顿图。
由推论知，对于完全图Kn,当n>=3时，是哈密顿图，完全二部图Kr,s当r==s>=2时是哈密顿图。
（3）在n(n>=2)阶有向图D=
中，如果略去所有有向边的方向，所得无向图中含生成子图Kn,则D中存在哈密顿通路。
推论：n(n>=3)阶有向完全图是哈密顿图。
常用方法判断是哈密顿图：
（1）若能通过观察找出图G中的一条哈密顿回路，则G当然是哈密顿图。
（2）若一个无向图G满足上述（2）中的条件，一个有向图D满足上述（3）的推论的条件，则G、D都是哈密顿图。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208859.html原文链接：https://javaforall.net
