§4.3Hamilton图.PDF

§4.3Hamilton 图 * 经过图G 的每个顶点恰一次的路称为G 的Hamilton 路。 * 经过图G 的每个顶点恰一次的圈称为G 的Hamilton 圈。 Hamilton 图的研究起源于十二面体的游戏（1856） 十二面体是H 图 Herschel 图不是H 图 与Euler 图不同，目前为止尚没有找到判别一个图是否是Hamilton 图的有效充要条件。 这是图论中未解决的重要难题之一。 本节给出一些经典的充分条件和必要条件。 一、必要条件 定理4.3.1 设G 是一个二部图，且有奇数个顶点，则G 不是H 图。（设G 是二部图，若G 是H 图，则G 必有偶数个顶点） 证明： 留作习题。 *Herschel 图是二部图，但有奇数个顶点，故不是H 图。 定理 4.3.2 若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 |. 证毕。 利用定理4.3.2 可判断下面不是H 图。 但定理4.3.2 不能来判断下列Petersen 图不是H 图。 2. 充分条件 （1）度型条件 ν 定理4.3.3(Dirac, 1952) 若G 是简单图，且ν ≥3 ，δ ≥ ，则G 是Hamilton 图。 2 证明 用反证法：假定定理不真。令 ν A {G | G 的顶点数为ν ≥3 ，δ ≥ ，且G 是非Hamilton 图}。 2 取A 中边最多的一个G 。因ν ≥3 ，故不是完全图（否则G 是Hamilton 图）。设u 和v 是G 的不相邻顶点。由G 的选择，G ＋uv 是Hamilton 图。因G 是非Hamilton 图，故G ＋uv 的H 圈必经过e = uv 。于是G 中存在以u 为起点v 为终点的Hamilton 路v v Lv 。这里v u ， 1 2 ν 1 v v ，令 ν S {v | uv ∈E }和T {v | v v ∈E } 。 i i+1 i i u v v1 v v … v v v … v vv 2 j v-1 3 i i+1 由于vν ∉S UT ，故| S UT |ν ，并且| S IT | 0 （因为若∃vi ∈S IT ，则G 将包含H 圈v v Lv v v Lv v ，矛盾）。 1 2 i ν ν−1 i+1 1 u v v1 v2 v3 … vi vi+1 … vv