狄拉克定理-奥勒定理.docVIP

哈密顿图判定 ①假设是一个哈密顿图，则对的任意非空子集均有 这里表示从图中删去中的所有顶点以及所关联的边；表示子图的连通分支数。 证明：因为图是哈密顿图 所以必存在哈密顿回路。我们来考察一下两种情况 （i） 中的顶点在中均彼此相邻，则 （ii）中的顶点在中不相邻，不妨设有并且个顶点不相邻 则 一般情况下，中的顶点在中既有相邻的也有不相邻的。 所以 而是图的生成子图 所以 所以， 证毕 这是一个判定哈密顿图的必要条件，但它不充分。如果某一个图不满足，则可以断定它不是哈密顿图。 ②狄拉克定理：如果图是一个具有个顶点的简单图，并且图中每个顶点的度数至少为，那么图是哈密顿图。 Dirac’s theorem：If G is a simple graph with n vertices with n ? 3 such that the degree of every vertex in G is at least n/2,then G has a Hamilton circuit. 狄拉克定理是英国数学家G．A．狄拉克（Dirac）在1952年给出一个充分条件不是哈密顿图 在图中连接不相邻的两个顶点，所得到的图仍然满足定理的条件 （我们知道，当图通过上述方法添加边，最终可以构造出一个完全图，而完全图必定是哈密顿图） 因此通过上述方法添加边，总可以使图成为满足条件的极大非哈密顿图。 这里不妨设就是极大非哈密顿图 （所谓极大非哈密顿图是指该图本身不是哈密顿图，但是在该图中，任意一对不相邻的顶点之间加上一条边，它就成为哈密顿图。极大非哈密顿图肯定不是完全图） 从中取两个不相邻的顶点和 则必是哈密顿图，并且该哈密顿回路一定包含边 于是图中一定存在一条从顶点到顶点的哈密顿通路（不是哈密顿回路） 令 ， 即凡是与邻接的顶点的前一个序号的顶点组成的集合， 即凡是与邻接的那些顶点组成的集合， 由该定义可以看出，（分析或者） 若，并且设 则必有：与给出的是一条通路相矛盾，所以 所以 ，且 那么 与图中每个顶点的度数至少为相矛盾 所以图必为哈密顿图 证毕 1960年美国著名图论专家奥斯坦·奥勒（Oystein Ore）推广狄拉克的工作，以下的结果③奥勒定理：如果图是一个具有个顶点的简单图，并且图中每一对不邻接的顶点和满足，那么图具有哈密顿回路。 Ore’s theorem：If G is a simple graph with n vertices with n ? 3 such that deg(u)+deg(v) ?n for every pair of nonadjacent vertices u and v in G, then G has a Hamilton circuit. 证明：①首先证明图是一个连通图 若图不是一个连通图，则图至少有两个连通分支 取， 因为是个顶点的简单图 所以， 与图中任意两个顶点和满足相矛盾。 所以，图是连通的。 ② 证明图中含有哈密顿回路 假设是图中顶点各不相同的最长的一条通路 显然，通路的长度为 因为是最长的一条通路 所以，与顶点和顶点邻接的顶点都一定在通路上 （如果不是这样，与是最长通路矛盾） 令 与邻接的顶点为 如果都不与邻接（与不邻接） 那么， （与邻接的顶点最多有个） 与题设矛盾 所以，至少存在一个使得与相邻，而与相邻 由此，可以构造一条回路 形成一条长度为的回路 如果 ，则图中必有不在的顶点 由于图是连通的，所以一定与上的某一个顶点相邻接（） 当时，是图中一条长度为的通路 当时，也是中一条长度为的通路 它们都与是最长通路矛盾 所以 因此，上面所产生的回路就是哈密顿回路 证毕