膀蒀哈密顿图判定薇膄①假设是一个哈密顿图,则对的任意非空子集均有羂这里表示从图中删去中的所有顶点以及所关联的边;表示子图的连通分支数。腿证明:因为图是哈密顿图蚇所以必存在哈密顿回路。我们来考察一下两种情况薅(i)中的顶点在中均彼此相邻,则荿(ii)中的顶点在中不相邻,不妨设有并且个顶点不相邻羈则蚇一般情况下,中的顶点在中既有相邻的也有不相邻的。蚂所以肁而是图的生成子图螆所以螇所以,肂证毕蕿这是一个判定哈密顿图的必要条件,但它不充分。如果某一个图不满足,则可以断定它不是哈密顿图。蝿袇②狄拉克定理:如果图是一个具有个顶点的简单图,并且图中每个顶点的度数至少为,那么图是哈密顿图。蒃Dirac’stheorem:IfGisasimplegraphwithnverticeswithn³3suchthatthedegreeofeveryvertexinGisatleastn/2,(Dirac)在1952年给出的一个判定哈密顿图的充分条件。一般来讲都是从简单图讨论。因为对哈密顿图来讲每个顶点只能通过一次,所以如果图中出现自环和平行边,那么对构造哈密顿图是没有什么影响的,因此,只考虑简单图即可。薈证明:假设不是哈密顿图羇在图中连接不相邻的两个顶点,所得到的图仍然满足定理的条件袄(我们知道,当图通过上述方法添加边,最终可以构造出一个完全图,而完全图必定是哈密顿图)蝿因此通过上述方法添加边,总可以使图成为满足条件的极大非哈密顿图。芇这里不妨设就是极大非哈密顿图肆(所谓极大非哈密顿图是指该图本身不是哈密顿图,但是在该图中,任意一对不相邻的顶点之间加上一条边,它就成为哈密顿图。极大非哈密顿图肯定不是完全图)肁从中取两个不相邻的顶点和蒁则必是哈密顿图,并且该哈密顿回路一定包含边肆于是图中一定存在一条从顶点到顶点的哈密顿通路(不是哈密顿回路)膆蒂令,衿即凡是与邻接的顶点的前一个序号的顶点组成的集合,腿芆袃即凡是与邻接的那些顶点组成的集合,薁由该定义可以看出,(分析或者)袈若,并且设芆芄则必有:与给出的是一条通路相矛盾,所以肈所以,且蚇那么莆与图中每个顶点的度数至少为相矛盾蚅所以图必为哈密顿图螀证毕蚀蒆1960年美国著名图论专家奥斯坦·奥勒(OysteinOre)推广了狄拉克的工作,给出了以下的结果,即奥勒定理。螁③奥勒定理:如果图是一个具有个顶点的简单图,并且图中每一对不邻接的顶点和满足,那么图具有哈密顿回路。蒂Ore’stheorem:IfGisasimplegraphwithnverticesw
狄拉克定理奥勒理 来自淘豆网m.daumloan.com转载请标明出处.
