《离散数学》课件：4-4-Hamilton图
《《离散数学》课件：4-4-Hamilton图》由会员分享，可在线阅读，更多相关《《离散数学》课件：4-4-Hamilton图（34页珍藏版）》请在文档大全上搜索。
1、沿着正十二面体的棱寻找一条旅行路线，通过每个城沿着正十二面体的棱寻找一条旅行路线，通过每个城市恰好一次又回到出发城市。这便是市恰好一次又回到出发城市。这便是Hamilton回路问回路问题。题。 Hamilton路着眼于无重复地遍历图中诸路着眼于无重复地遍历图中诸点，而点，而 Euler路着眼于无重复地遍历有路着眼于无重复地遍历有向图中诸弧。向图中诸弧。存在存在Euler路，未必存在路，未必存在 H回路。回路。存在存在H回路，未必存在回路，未必存在Euler路。路。定理定理4.4.1 证明：证明：设设C是是G中的中的Hamilton回路，回路，因为在因为在回路中，依次删去一点及与此点相邻的两回路
2、中，依次删去一点及与此点相邻的两条边每次最多只增加一个分支，所以条边每次最多只增加一个分支，所以 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定理定理4.4.2 若若G=(P, L)是有限图，是有限图， 3， /2，则则G是是Hamilton图。其中，图。其中
3、， 表示图表示图G中点数，即中点数，即 =|P(G)|， 表示表示G中点的最小中点的最小度。度。反证法，反证法，若若G不是不是Hamilton图，则我们证明在图，则我们证明在G中一定中一定能找到其度能找到其度 /2的顶点的顶点,从而推出矛盾从而推出矛盾,因而假设不成立因而假设不成立的方法证明本定理结论的方法证明本定理结论 。证明过程如下证明过程如下:若若G不是极大非不是极大非Hamilton图，则可以不断地向图，则可以不断地向G增加若增加若干条边，把干条边，把G变成极大非变成极大非Hamilton图图G0，若若G是极大非是极大非Hamilton图图, ,则令则令G0=G，显然，对任意点显然，对
4、任意点v P(G)，dG(v) dG0(v)，那么，如果在那么，如果在G0中能找到度中能找到度 /2的点，的点，在在G中也一定能找到。中也一定能找到。 设设u, v是是G0中不相邻的两点，于是，中不相邻的两点，于是，G0uv是是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
5、相邻，则把相邻，则把vj在在L中前一个顶点放入中前一个顶点放入S中中) ；T= vi | viv L(G0), i=1, ,2, , 。 显然，显然，d(u)=d(v1) = |S|， d(v)=d(v ) = |T|对点集对点集S和和T，可以证明可以证明ST= ，否则，若否则，若ST，设设vj ST，则则vj+1与与v1相邻，于是相邻，于是(v1,v2,vj,v ,v -1,vj+1,v1)是是G0中一条不通过中一条不通过边边uv(即即v1v )的的Hamilton回路，回路，与与G0不是不是Hamilton图矛盾。图矛盾。 因为因为 v ST，故故 |ST| 。于是，。于是， d(u)+d
6、(v) = |S|+|T| = |ST| 故故d(u)，d(v)中至少有一个小于中至少有一个小于 /2，这与，这与 /2矛盾。故矛盾。故G是是Hamilton图。图。 设设G是有限图，是有限图，u, v是是G中不相邻的两点，并且中不相邻的两点，并且满足：满足：d(u)+d(v) 则则G是是Hamilton图的充要条件是图的充要条件是Guv是是Hamilton图。图。证明：证明：必要性显然。必要性显然。充分性充分性，若若Guv是是Hamilton图，而图，而G不是，不是，仿照定理仿照定理4.4.2的证明，得到的证明，得到d(u)+d(v) ，矛盾。矛盾。 设设G是有限图。反复连接是有限图。反复连
7、接G中不相邻的并且中不相邻的并且其度之和不小于其度之和不小于 的点对，直到没有这样的点对，直到没有这样的点对为止。最后所得的图称为的点对为止。最后所得的图称为G的闭合的闭合图，记为图，记为C(G)。 afedcb有限图有限图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
