五Euler图和Hamilton图.docVIP

第十五章 Euler 图和 Hamilton图 第二节 Hamilton 图 　 　　经过图 G的每个顶点恰一次的路称为G的Hamilton路。 　　经过图G的每个顶点恰一次的圈称为G的Hamilton圈。 类似可定义有向图中的有向 Hamilton路和有向Hamilton圈。 　　Hamilton 图的研究起源于十二面体的游戏（ 1856） 　　　　与Euler图不同，目前为止尚没有找到判别一个图是否是Hamilton图的有效充要条件。这是图论中未解决的重要难题之一。 　　本节给出一些经典的充分条件和必要条件。 一.必要条件定理 15.7 设 G是一个二部图，且有奇数个顶点，则 G 不是 H 图。 (也可叙述为：设G是二部图，若G是H图，则G必有偶数个顶点) 证明留作练习。 　　*Herschel 图是二部图，但有奇数个顶点，故不是H图。 定理 15.8 若G是H图，则对V(G)的每个非空真子集S，均有 　　　　　W (G－S)≤ | S |。 证明：设 C是 G的 H圈，则对 V (G)的每个非空真子集S，均有 　　　　　W (C－S)≤ | S | 　　　由于 C－S是 G－S的生成子图，故 W (G－S)≤W(C－S)≤ | S |. 　　　证毕。 　　利用定理15.8可判断下面图1不是H 图。但定理15.8不能来判断下列Petersen图(图2) 不是H图。 　　推论 15.2 若图G有Hamilton路，则对V(G)的每个真子集S，都有w(G - S ) ≤ |S|+1。 证明留作练习。 二.充分条件（1） 度型条件定理 15.9 (Dirac, 1952) 若 G是简单图，且 ≥ , δ ≥ n /2，则G是Hamilton图。 证明 用反证法：假定定理不真。令 　　　　　　 A= {G|G的顶点数为 ≥ ， ν ≥δ /2 ，且G是非Hamilton图}。 　　取 A中边最多的一个 G。因 ≥ ，故不是完全图(否则G是Hamilton图)。设u和v是G的不相邻顶点。由G的选择，G＋uv是Hamilton图。因G是非Hamilton图，故G＋uv的H圈必经过e = uv。于是G中存在以u为起点ν为终点的Hamilton路v 1v 2…v ν 。这里 v 1 =u， v ν =v，令 　　S = {v i|uν i +1 ∈ E } 和 T = {v i|v iν ∈ E } 。 　　　　　　　　　　　　　由于v ν ? S ∪ T ，故|S ∪ T | ν ，并且|S ∩T|=0 (因为若 S ∩T ，则G将包含H圈ν1ν2…ν iνn νn -1 …νi+ 1ν1，矛盾)。 　　　　　　　　　　　　　　　故d(u)+d(v)=|S|+|T|=|S ∪ T |+|S ∩T| ν ，这与 ν≥ δ /2的前提矛盾。证毕。 (2) 闭包型条件定理 15.10 (Bondy Chvátal,1974) 设G是简单图，u和v是G中不相邻的顶点，且d(u)+d(v) ν ≥ ，则 G是 Hamilton图当且仅当 G＋ uv 是Hamilton图。 证明：必要性是显然的。 　　　充分性：若 G＋ uv是 Hamilton图而 G不是，则与定理 15.9一样可推出矛盾。 　　　证毕。 定义 15.1 图 G的 闭包 （ closure）是指由如下方法所得之图： 　　反复连接G中度之和不小于 ν 的不相邻顶点对，直到没有这样的顶点对为止。 　　图G的闭包记为C(G)。 定理 15.11　G的闭包C(G)是唯一确定的。 证明：设,是按闭包构成方法所得的两个图。用,, …, 和, , …, f m分别表示在构作,过程中给G添加边的序列。我们来证明每个一定是G 2的边，而每个一定是的边。 假设e= uv 是序列,, …, 中第一条不属于的边，令 　　　　　　H = G + {,, …,}。 　　由的定义知，dH (u)+ dH(v)≥v。但因H是的子图，因此d(u)+ d(v)≥v 。而由+ 1的选择，u、v在中是不相邻的，这与G 2是闭包矛盾。故每条都必是的边。 　　同理可证，每条 f j 一定是G 1的边。这说明图G的闭包是唯一的。 　　证毕。 例： 　　　　前一个图的闭包是它自己，后一个图的闭包是完全图 。 定理 15.12 一个简单图是 Hamilton 图当且仅当它的闭包是 Hamilton 图。 证明：在构作闭包过程中，反复运用定理 15.10 即可。 推论 15.3 设 G 是 ≥ν3 的简单图。若 C (G) 是完全图，则 G 是 Hamilton 图。 推论 15.4 设 G 是