Hamilton图(离散数学).ppt

§4.4 Hamilton图 §4.4 Hamilton图 沿着正十二面体的棱寻找一条旅行路线，通过每个城市恰好一次又回到出发城市。这便是Hamilton回路问题。 §4.4.1 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图。 比较H路、H回路与Euler路 Hamilton路着眼于无重复地遍历图中诸点，而 Euler路着眼于无重复地遍历有向图中诸弧。 存在Euler路，未必存在 H回路。 存在H回路，未必存在Euler路。 关于Hamilton路和Hamilton回路的一些性质 1. 若图G中有一点的度为1，则无Hamilton回路。 2. 若图G中有一点的度为0，则既无Hamilton路，又无Hamilton回路。 3. 设图G中有一点的度为2，若有Hamilton回路，则以此点为端点的两条边均出现在此回路中。 4. 设图G中有一点的度大于2，若有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图。 例： §4.4.2 Hamilton图的充分条件 定义 设图G是非Hamilton图，若在G中增加任意一条边uv，G∪{uv}就变成Hamilton图，则G称为极大非Hamilton图。 充分条件 定理4.4.2 若G=(P, L)是有限图，? ?3，? ? ?/2，则G是Hamilton图。其中，?表示图G中点数，即? =|P(G)|，?表示G中点的最小度。 证明： 反证法，若G不是Hamilton图，则在G中一定能找到其度?/2的顶点。显然，G不是完全图 。 若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是