提示：本文主要介绍哈密顿图和半哈密顿图的定义以及判定条件，文中的图片来源于杨映雪老师的ppt。

1.哈密顿路：给定无向图G中，通过图中每个结点一次而且仅一次的路径。 2.哈密顿回路：给定无向图G中，通过图中每个结点一次而且仅一次的回路。 3.哈密顿图：具有哈密顿回路的图。 4.半哈密顿图：有哈密顿路径而没有哈密顿回路的图。哈密尔顿图和半哈密尔顿图是连通图。 哈密顿图和欧拉图联系：两者都是遍历问题，但是欧拉图考虑的是边，而哈密顿考虑的是结点。同时判定欧拉图具有充要条件。但是哈密顿图没有简单的充要条件，只有必要条件和充分条件。

必要条件用于判定一个图不是半/哈密顿图。（p59）

定理1.设无向图G=是哈密顿图，S是V的任意的非空真子集， ==w(G-S)≤|S| ==其中，w(G-S)为从G中删除S(删除S中各顶点及关联的边)后所得到的图的连通分支数。

证明：设C是G的一条哈密顿回路，C是G的子图，在回路C中每删去S的一个结点，最多增加一个连通分支，且删去S中的第一结点时分支数不变，所以有w(C-S)≤|S|。又因为C是G的生成子图，所有C-S是G-S的生成子图，且w(G-S)≤w(C-S),因此w(G-S)≤|S|

推论：设无向图G=是半哈密顿图，则对于结点集V的任意非空真子集S均有w(G-S)≤|S| +1。

证明：设P是G中起始于u终止于v的哈密顿图，令G’=G∪(u,v) （在G的结点u，v之间添加新边），易知G’为哈密顿图。所以有 w(G-S)≤|S| ，则： w(G-S) = w(G’ - S - (u,v) ) ≤ w(G’-S) + 1 ≤ |S| +1

一般情况下，设二部图G(V1,V2,E),|V1|≤|V2|,且|V1|≥2，|V2|≥2，由上述定理以及推论有： 1.若G是哈密顿图，则|V1| = |V2|; 2.图G是半哈密顿图，则|V2| = |V1| +1； 3.若|V2| ≥ |V1| +2，则图G既不是哈密顿图，也不是半哈密顿图。

定理2：无向简单图G中任意两个不相邻的 结点度数之和 ≥ n-1，则图G中存在一条哈密顿路。图G是半哈密顿图。 例题2： 定理3：图G具有n个结点的无向简单图，如果图G中任意一对不相邻结点的度数之和 ≥ n，则G是哈密顿图

证明：由上述定理2知，图G一定是半哈密顿图，即存在一条哈密顿路F = V1V2V3…Vn。如果V1和Vn相邻，则F是哈密顿回路。如果不相邻，由定理2可知图G一定存在一条包含V1V2V3…Vn的回路，这个回路是哈密顿回路。所有图G是哈密顿图。

例题：

闭包： 竞赛图：

竞赛图中每对不同的顶点通过单个有向边连接，即每对顶点间都有一条有向边。设 D 为 n 阶有向简单图，若 D 的基图为 n 阶无向完全图，则 D 为 n 阶竞赛图。简单来说，竞赛图就是将完全无向图的无向边给定了方向。