《离散数学》课件：4-4-Hamilton图.ppt

§4.4 Hamilton图图 Ø沿沿着着正正十十二二面面体体的的棱棱寻寻找找一一条条旅旅行行路路线线，，通通过过每每个个城城市恰好一次又回到出发城市这便是市恰好一次又回到出发城市这便是Hamilton回路问题回路问题 §§4.4 Hamilton图图 Ø定义定义4.4.1 设设G=(P, L)是有限图，是有限图，(v1, … , vn)是是G中一条路如果中一条路如果G中每点恰在此路中出现中每点恰在此路中出现一次，则称此路为一次，则称此路为Hamilton路；如果路；如果G中每点，中每点，除除v1外，恰在此路中出现一次，而外，恰在此路中出现一次，而v1=vn，，则此则此路称为路称为Hamilton回路Ø定义定义4.4.2 设设G=(P, L)是有限图，如果是有限图，如果G中有中有一条一条Hamilton回路，则称回路，则称G为为Hamilton图 §§4.4.1 Hamilton路及必要条件路及必要条件 比较比较H路、路、H回路与回路与Euler路路Ø Hamilton路着眼于无重复地遍历图中诸路着眼于无重复地遍历图中诸点，而点，而 Euler路着眼于无重复地遍历有向路着眼于无重复地遍历有向图中诸弧。

图中诸弧Ø存在存在Euler路，未必存在路，未必存在 H回路Ø存在存在H回路，未必存在回路，未必存在Euler路1. 若图若图G中有一点的度为中有一点的度为1，则无，则无Hamilton回路2. 若若图图G中中有有一一点点的的度度为为0，，则则既既无无Hamilton路路，，又无又无Hamilton回路3. 设设图图G中中有有一一点点的的度度为为2，，若若有有Hamilton回回路路，，则以此点为端点的两条边均出现在此回路中则以此点为端点的两条边均出现在此回路中4. 设设图图G中中有有一一点点的的度度大大于于2，，若若有有Hamilton回回路，则只用其中的两条边路，则只用其中的两条边 关于关于Hamilton路和路和Hamilton回路的一些性质回路的一些性质关于关于Hamilton路和路和Hamilton回路的性质回路的性质Ø5. 若图中有若图中有n个点，则个点，则Hamilton路恰有路恰有n-1条边，条边，Hamilton 回路恰有回路恰有n条边Ø6. Hamilton路是图路是图G的支撑子树，的支撑子树，Hamilton回路是图回路是图G的支撑子图的支撑子图必要条件必要条件Ø定理定理4.4.1 如果图如果图G=(P, L)是是Hamilton图，则图，则对对P(G)的任一非空子集的任一非空子集S，，都有都有W(G-S)   |S|其中其中 |S| 表示集合表示集合S的元素数，的元素数，G-S表示在表示在G中中删除删除S中的点以及以中的点以及以S中的点为端点的所有边中的点为端点的所有边而剩下的图，而剩下的图，W(G-S)表示图表示图G-S的连通分支的连通分支数。

数 必要条件必要条件证明：证明：设设C是是G中的中的Hamilton回路，回路，因为在因为在回路中，依次删去一点及与此点相邻的两回路中，依次删去一点及与此点相邻的两条边每次最多只增加一个分支，所以条边每次最多只增加一个分支，所以 W(C-S)   |S|因为因为C是是G的支撑子图，所以的支撑子图，所以C-S是是G-S的的支撑子图故支撑子图故W(G-S)   W(C-S)，，故故W(G-S)   |S| 例：例：将图中点将图中点A，，B，，C的集合记为的集合记为S，，于是，删去于是，删去S，，剩下的图的剩下的图的分支数是分支数是4，而，而|S|=3由定理由定理4.4.1知，该图不知，该图不是是Hamilton图 ABCABC例：例：定义定义 设图设图G是非是非Hamilton图，若在图，若在G中增加任中增加任意一条边意一条边uv，，G∪∪{uv}就变成就变成Hamilton图，则图，则G称为极大非称为极大非Hamilton图 §§4.4.2 Hamilton图的充分条件图的充分条件 定理定理4.4.2 若若G=(P, L)是有限图，是有限图，   3，，     /2，，则则G是是Hamilton图。

其中，图其中， 表示图表示图G中点数，即中点数，即  =|P(G)|，， 表示表示G中点的最小中点的最小度充分条件充分条件反证法，反证法，若若G不是不是Hamilton图，则我们证明在图，则我们证明在G中一定中一定能找到其度能找到其度< /2的顶点的顶点,从而推出矛盾从而推出矛盾,因而假设不成因而假设不成立的方法证明本定理结论立的方法证明本定理结论 证明过程如下证明过程如下:若若G不不是是极极大大非非Hamilton图图，，则则可可以以不不断断地地向向G增增加加若若干干条条边边，，把把G变变成成极极大大非非Hamilton图图G0，，若若G是是极极大大非非Hamilton图图, ,则则令令G0=G，，显显然然，，对对任任意意点点v P(G)，，dG(v) dG0(v)，，那那么么，，如如果果在在G0中中能能找找到到度度< /2的的点点，，在在G中也一定能找到中也一定能找到 证明：证明：设设u, v是是G0中不相邻的两点，于是，中不相邻的两点，于是，G0∪∪{uv}是是Hamilton图，且其中每条图，且其中每条Hamilton回路都要通过回路都要通过边边uv。

因此，因此，G0中有起点为中有起点为u，，终点为终点为v的的Hamilton路路L: L=(v1,v2, … ,v -1, v )其中其中v1=u, v =v令令S={vi | v1vi+1 L(G0),i=1, ,2,…,…, -1}，，(即如果即如果v1,…,,…,v 中某中某vj与与v1相邻，则把相邻，则把vj在在L中前一个顶点放入中前一个顶点放入S中中) ；；T={ vi | viv  L(G0), i=1, ,2,…,…, } 显然，显然，d(u)=d(v1) = |S|，， d(v)=d(v ) = |T|证明：证明：对点集对点集S和和T，，可以证明可以证明S∩∩T= ，，否则，若否则，若S∩∩T，，设设vj S∩∩T，，则则vj+1与与v1相邻，于是相邻，于是(v1,v2,…,vj,v ,v -1,…,vj+1,v1)是是G0中一条不通过中一条不通过边边uv(即即v1v )的的Hamilton回路，回路，与与G0不是不是Hamilton图矛盾 因为因为 v    S∪∪T，，故故 |S∪∪T|     。

于是，于是， d(u)+d(v) = |S|+|T| = |S∪∪T|    故故d(u)，，d(v)中至少有一个小于中至少有一个小于  /2，这与，这与     /2矛盾故G是是Hamilton图 证明：证明：引理引理1 设设G是有限图，是有限图，u, v是是G中不相邻的两点，并且满中不相邻的两点，并且满足：足：d(u)+d(v)    则则G是是Hamilton图的充要条件是图的充要条件是G∪∪{uv}是是Hamilton图证明：证明：必要性显然必要性显然充分性充分性，，若若G∪∪{uv}是是Hamilton图，而图，而G不是，不是，仿照定理仿照定理4.4.2的证明，得到的证明，得到d(u)+d(v)    ，，矛盾 定义定义4.4.3 闭合图闭合图设设G是有限图反复连接是有限图反复连接G中不相邻的并且中不相邻的并且其度之和不小于其度之和不小于   的点对，直到没有这样的点对，直到没有这样的点对为止最后所得的图称为的点对为止最后所得的图称为G的闭合的闭合图，记为图，记为C(G) 例：例：afedcb引理引理2 有限图有限图G的闭合图的闭合图C(G)是唯一确定的。

是唯一确定的Ø证明：证明：设在设在G中增加边中增加边l1,…,ln后得闭合图后得闭合图C1(G)，， 在在G中增加边中增加边f1,…,fm后得闭合图后得闭合图C2(G)往证：往证：C1(G)= C2(G)只需证：只需证：{ l1,…,,…,ln}={f1,…,,…,fm}；；即证即证{l1,…,ln} {f1,…,fm}并且并且{f1,…,fm} { l1,…,ln}先证先证{l1,…,ln} {f1,…,fm}引理引理2 反反证证法法，，假假设设lk+1=uv是是第第一一个个(从从左左向向右右看看)不不在在{f1,…,fm}中的边，令中的边，令H=G∪∪{l1, … , lk} (1)因因为为H是是C2(G)的的子子图图，，而而lk+1不不在在C2(G)中中，，所以，所以，dH(u)+dH(v)< ；；(2) 因为因为G∪∪{l1,…,ln}是是G的闭合图，所以的闭合图，所以dH(u)+dH(v)，，矛盾所以不存在所以不存在li   {f1,…,fm} (i=1, …… , m) ，，即即{ l1,…,ln}   {f1,…,fm}；；同理，同理，{f1,…,fm} { l1,…,ln}故故 { l1,…,ln}={f1,…,fm} ,即即C1(G)= C2(G)定理定理4.4.3 有限图有限图G是是Hamilton图的充要条件是闭合图图的充要条件是闭合图C(G)是是Hamilton图。

图 证证明明：：设设图图G加加入入边边序序列列{l1, … , lm}后后，，得得闭闭合合图图C(G)由引理由引理1知，知，G是是Hamilton图图G∪∪{l1}是是Hamilton图 G∪∪{l1}∪∪{l2}是是Hamilton图  … G∪∪{l1,…,lm}是是Hamilton图因此，因此，G是是Hamilton图当且仅当图当且仅当C(G) 是是Hamilton图 推论推论设设G是有限图，若是有限图，若C(G)是完全的，则是完全的，则G是是Hamilton图 定理定理4.4.4 设有限图设有限图G的度序列的度序列(即即G的各点的度，按大小顺的各点的度，按大小顺序排成的序列序排成的序列)为为(d1, d2, … , d )，，其中其中d1   d2   …   d ，，    3如果不存在这样的如果不存在这样的m, m   /2 ，，并使得并使得dm   m , d -m     -m则则G是是Hamilton图 证明：证明： 往证往证G的闭合图的闭合图C(G)是完全图。

用是完全图用d(u)记点记点u在在G中的度，用中的度，用d’(u)记点记点u在在C(G)中的度反证法，反证法，假设假设C(G)不是完全的，设不是完全的，设u, v是是C(G)中中使得使得d’ (u) +d’ (v)为最大的两个不相邻的点不为最大的两个不相邻的点不妨设妨设d’ (u)  d’ (v)由由C(G)的性质，显然，的性质，显然，d’ (u)+d’ (v)     令令S={x | x P(G)并且并且x在在C(G)中与中与v不相邻不相邻} T={x | x P(G)并且并且x在在C(G)中与中与u不相邻不相邻} 显然，显然，|S|=  -d’(v) ，， |T| =  -d’(u) 注意，点注意，点u与自己算做不相邻与自己算做不相邻 证明：证明： 因因为为u T，，v S，，但但是是d’ (u)  d’ (v)，，所所以以，，由由u，，v的的取取法法知知，，S-{v}中中点点的的最最大大度度为为d’(u)，，T中中点的最大度为点的最大度为d’(v)令令d’(u)=m于是，于是，(C(G)中其度中其度 m的点数的点数)   S-{v}中的点数中的点数=|S|-1= -d’(v)-1-( -d’(u))-1=d’(u)-1=m-1即即C(G)中至少有中至少有m个点，其度个点，其度 m。

证明：证明： 同理，同理，(C(G)中其度中其度 d’(v)的点数的点数)   |T| =  -d’(u) =  -m又因又因d’(v)   -d’(u)=  -m所以所以C(G)中至少有中至少有 -m个点，其度个点，其度< -m综综上上，， C(G)中中至至少少有有m个个点点，，其其度度 m；； C(G)中至少有中至少有 -m个点，其度个点，其度< -m证明：证明： 因为因为G是是C(G)的子图，所以在的子图，所以在G中也至少有中也至少有m个个点，其度点，其度 m；； 至少有至少有 -m个点，其度个点，其度< -m所以，在所以，在G的度序列的度序列(d1, d2, …,d )中有中有 dm m，，d -m< -m由由d’(u)+d’(v)< ，，知知d’(u)< /2，，所所以以m< /2，，即存在这样的即存在这样的m与已知条件与已知条件矛盾 故假设不成立，故假设不成立，C(G)是完全图，所以是完全图，所以G是是Hamilton图。

图定义定义Ø定义定义4.4.4 实数序列实数序列(p1, …, pn)称为由实数称为由实数序列序列(q1, …, qn)所增大，如果所增大，如果pi qi, i=1, … , n Ø定义定义4.4.5 设设G，，H是有限图是有限图G称为被称为被H度增大，如果度增大，如果|P(G)|=|P(H)|，，并且并且G的不减的不减度序列被度序列被H的不减度序列所增大的不减度序列所增大 定义定义Ø定义定义4.4.6 设设G，，H是两个无公共点的有是两个无公共点的有限图将G的每个点和的每个点和H的每个点都用边连的每个点都用边连接起来得到的图，称为接起来得到的图，称为G与与H的连接图，记的连接图，记为：为： GH定义定义Ø定义定义4.4.7 设设G，，H是两个有限图，如果是两个有限图，如果P(G)=P(H)，，并且对并且对G，，H中任意两点中任意两点u、、v，，u和和v在在G中相邻当且仅当它们在中相邻当且仅当它们在H中不相中不相邻，则称邻，则称G是是H的补图，的补图，H是是G的补图，可的补图，可以将以将G记为记为Hc，，也可将也可将H记为记为Gc 用用Km表示由表示由m个点组成的完全图。

将如下三个个点组成的完全图将如下三个图：图： KmcKmKn-2m1  m  n/2 从左到右顺序连接起来构成的连接图记为从左到右顺序连接起来构成的连接图记为Cm,n 例：例：下图下图6给出的是给出的是 C2,7的具体图的具体图 K2cK2K3引理引理3Ø若若1   m   n/2 ，，则图则图Cm,n 是非是非Hamilton图证证明明：：图图Cm,n中中Km部部分分有有m个个点点，，令令S是是这这m个个点组成的集合于是点组成的集合于是 W(Cm,n-S)=W(Kmc)+W(Kn-2m) =m+1故故 W(Cm,n-S)   |S|由定理由定理4.4.1知，知，Cm,n是非是非Hamilton图 定理定理4.4.5Ø若若G为为非非Hamilton图图，，    3，，则则G由由某某个个Cm,  所度增大其中所度增大其中 是是P(G)的元数证明：证明：设设G的不减度序列为（的不减度序列为（d1, d2, … , d ）由由定理定理4.4.4知，存在知，存在m   /2 ，，使得使得dm   m , d -m     -m 。

故（故（d1, d2, … , d ））由序列：由序列：(m, … , m,  -m-1, … ,  -m-1,  -1, … ,  -1)m个个 -2m个个m个个所增大显然，后一个序列正是图显然，后一个序列正是图Cm,  的度序列，故的度序列，故G由由Cm,  所度增大所度增大。