图论课件--度极大非哈密尔顿图与TSP问题

《图论课件--度极大非哈密尔顿图与TSP问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其应用应用数学学院1本次课主要内容(一)、度极大非哈密尔顿图(二)、TSP问题度极大非哈密尔顿图与TSP问题21、定义(一)、度极大非哈密尔顿图定义1图G称为度极大非H图，如果它的度不弱于其它非H图。2、Cm,n图定义2对于1≦m

2、S

3、=m,所以，由H图的性质知，G是非H图。4、度极大非H图的特征4定理1(Chvátal,1972)若G是n≧3的非H单图，则G度弱于某个Cm,n图。证明：设G是度序列为(d

4、1,d2,…,dn)的非H单图，且d1≦d2≦…≦dn,n≧3。由度序列判定法：存在m

5、的Cm,n图族，则G是H图。G的度序列是(2,3,3,4,4),优于C1,5的度序列(1,3,3,3,4)和C2,5的度序列(2,2,2,4,4)。所以可以断定G是H图。例如：G推论设G是n阶单图。若n≧3且7则G是H图；并且，具有n个顶点条边的非H图只有C1,n以及C2,5.证明:(1)先证明G是H图。若不然，由定理1，G度弱于某个Cm,n,于是有：这与条件矛盾！所以G是H图。8(2)对于C1,n,有：除此之外，只有当m=2且n=5时有：这就证明了(2)。注：推论的条件是充分而非必要的。例如：在C1,7的任意不相邻顶点间连一边后可得H图：9但是，在下图中，尽管C2,7+uv的边数不满足推论不

6、等式，可它是H图。C1,7+eeuvC2,7+uv10例1设G是度序列为(d1,d2,…,dn)的非平凡单图，且d1≦d2≦…≦dn。证明：若G不存在小于(n+1)/2的正整数m，使得：dm

7、立方体。如果它从一角上开始，然后依次走向未吃的立方体，问吃完时是否可以到达中心点？解：如果把每个子立方体模型为图的顶点，且两个顶点连线当且仅当两个子立方体有共同面。那么，问题转化为问该图中是否存在一条由角点到中心点的H路。如果起点作为坐标原点，那么27个子立方体可以编码为：(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(1,3,1),…,(3,3,3)12容易知道：G是偶图，且如果(1,1,1)在X中，则中心点(2,2,2)必在Y中。又容易知道：

8、X

9、=14,

10、Y

11、=13.G中不存在由点(1,1,1)到点(2,2,2)的H路。否则，将(1,1,

12、1)和(2,2,2)连线后得到的图G1有H圈。但是，G1不能是H图。因为在G1中，取S=Y,则可得到：14=ω(G1-S)>

13、S

14、=13.故，老鼠最后不能到达中心点。13例3对m条边的n阶图G，若G的每两个顶点都由一条H路连接着，称G是哈密尔顿连通图。(1)证明：若G是H连通图且n≧4,则(2)对于n≧4,构造一个H连通图G,使得：证明：(1)可以证明，δ(G)≧3.于是有：事实上,若存在v，有d(v)=2,设v1与v2分别是v的两个邻接点，则由n≧4知，不存在v1为起点v2为终点的H路，与条件矛盾。14(2)下面构造一个H连通图G,使得：n为偶数时n为奇数时15例4写出下列问题的一个好算法：

15、(1)构作一个图的闭包；(2)若某图的闭包是完全图，求该图的H圈。解：(1)构作一个图的闭包。根据图的闭包定义，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点对间添边得到。据此设计算法如下：图的闭包算法：1)令G0=G,k=0;2)在Gk中求顶点u0与v0，使得：163)如果，则转4);否则，停止，此时得到G的闭包；4)令Gk+1=Gk+u0v0,k=k+1,转2).复杂性分析：在第k