图的直接和的 Hamilton圈研究

胡延忠,叶 波,2

(1.湖北工业大学计算机学院,湖北武汉430068;2.十堰职业技术学院汽车系,湖北十堰442000)

图的直接和的 Hamilton圈研究

胡延忠1,叶 波1,2

(1.湖北工业大学计算机学院,湖北武汉430068;2.十堰职业技术学院汽车系,湖北十堰442000)

本文定义了图的直接和的概念,讨论了图的直接和中 Ham ilton圈的存在性。当图本身存在 Hamilton圈时,它的直接和中的 Hamilton圈也存在;设图 G是n阶图,如果它的极大Ham ilton子圈与Cn-1同构,那么它的直接和存在 Ham ilton圈;本文还研究了极大 Ham ilton子圈同构于Cn-2的n阶图并得到了三个充分条件。本文最后用超立方体Q4为例展示了这些命题的应用。

Hamilton圈;直接和;同构图;超立方体

0 导论

无向图中 Ham ilton圈是遍历图中每个顶点恰好一次又返回起点的圈。确定一个图中这样的圈是否存在就是 Hamilton圈问题,它是一个NP完全问题。实际应用(特别是计算机网络中的应用)和计算复杂性的研究推动了 Ham ilton圈问题的研究[1][2][3][4]。Hamilton圈问题的研究由来已久。Dirac于1952就证明了:如果 G是至少有三个顶点的简单图且每个顶点的度数大于等于 n/2存在Hamilton圈;Bondy-Chvátal1972年给出了定理:一个图存在 Hamilton圈的充要条件是它的闭包存在 Hamilton圈;Tutte也于1956年证明每一个4-连通的平面图存在 Ham ilton圈[5]。宋玉梅在1999年证明:一个简单图存在 Hamilton圈的充要条件是其 PerGR非零[6]。与此同时,对一些特殊图的Hamilton圈问题的研究也很活跃。例如,Fleischner研究了图的平方中 Hamilton圈问题,并于1974年证明了:如果 G是一个2-连通的图,那么G2存在 Hamilton圈[5];Chvátal于1985年研究了旅行商问题中 Hamilton圈[7];Jackson1980年证明了度数至少为n(G)/3的任意简单正则图存在Hamilton圈[8],这一结论由Zhu Y.J.、Z.H.Liu和 Z.G.Yu等人进行了改进[9]。本文讨论图的直接和的Ham ilton圈问题。

1 基础知识

集合V 1={1,2,3}和集合V 2={a,b}的笛卡尔积是一个集合 ,记为 V1×V2={〈1,a〉,〈1,b〉,〈2,a〉,〈2,b〉,〈3,a〉,〈3,b〉}。V1×V2的任意子集合称为一个二元关系,例如,f={〈1,a〉,〈1,b〉,〈2,b〉,〈3,a〉}就是一个二元关系。映射是一种特殊的二元关系。

本文只考虑简单连通图。

图1 图 G和它的同构图

假设V(G)={v1,v2,v3,…,vn},那么α={〈v1,α(v1)〉,〈v2,α(v2)〉,〈v3,α(v3)〉,…,〈vn,α(vn)〉}。

如图1所示,存在一个从图 G到图 H的同构:α={ 〈1,x〉,〈2,y〉,〈3,z〉}。图 1(a)和图1(b)分别表示图 G和它的同构图 H。

图2是 Petersen图,它是3-连通的,但是没有Hamilton圈。

Petersen图到它自身的直接和如图3所示。

显然,一个图到自身的直接和是3-联通的,而这正好是一个图存在 Ham ilton圈的必要条件。

2 主要定理

当图 G没有 Hamilton圈时,结果将会怎么样?

例题2.2 Petersen图没有 Hamilton圈,然而它的直接和却存在 Hamilton圈,如图2所示。

例题2.3 图5(a)是一个非 Hamilton图,它的直接和存在 Hamilton圈,如图5(b)所示,其中表示同构映射(下同)。

图6 非Hamilton图的直接和不存在Hamilton圈

例题2.4 图6(a)是一个非 Ham ilton图,它的直接和没有 Hamilton圈,如图6(b)所示。

问题2.5 一个图满足什么条件时,它的直接和存在 Ham ilton圈呢?充分必要条件也许难以发现,但是下列结论有很重要的意义。

图7 极大Hamilton子圈的阶数为n-1

证明:为了方便起见,假设图 G的极大 Hamilton子圈为Cn-1且V(G)={1,2,… ,n}。因为图G是连通图,所以不在Cn-1上的顶点n必和Cn-1某一顶点邻接,如图7(a)所示。图7(b)是包含 G的所有顶点子图的直接和,路径:1n f(n)f(1)f(n-1)…f(3)f(2)23…(n-1)1是一条 Hamilton圈。因此图 G的直接和存在 Hamilton圈。

(1)不在极大Hamilton子圈上的两顶点是邻接的。

(2)不在极大 Hamilton子圈上的两顶点是不邻接的,但满足下列条件之一。设1和2分别是极大Hamilton子圈上的两顶点,x和y是不在极大Hamilton子圈上的两顶点,且分别和1和2邻接。

a.在顶点1和顶点2之间(顺时针方向)没有其他顶点。

b.在顶点1和顶点2之间(顺时针方向)具有一个(或奇数个)顶点,且在顶点2和顶点1之间(顺时针方向)也具有一个(或奇数个)顶点。

c.在顶点1和顶点2之间(顺时针方向)具有两个(或偶数个)顶点,且在顶点2和顶点1之间(顺时针方向)也具有两个(或偶数个)顶点。

证明:1)为了方便起见,假设1,2,3是极大Ham ilton子圈上彼此连接的三个顶点,假设x和y不在极大 Hamilton子圈上且和顶点1邻接,如图8所示。路径:1xy f(y)f(x)f(1)…f(3)f(2)23…1是直接和的一条 Hamilton圈。

2)a)路径:1x f(x)f(1)…f(2)f(y)y2…1是一条 Hamilton圈,如图9所示。

2)b)路径:1x f(x)f(1)f(n)n2y f(y)f(2)f(m)m1是一条 Hamilton圈,如图10(a)所示,路径:x f(x)f(1)f(p)pn f(n)f(q)q2y f(y)f(2)f(m)m1是一条 Hamilton圈,如图10(b)所示。

2)c)箭头所示的路径是一条 Hamilton圈,如图11所示。

3 应用举例

例题3.1 超立方体Q4存在 Ham ilton圈。

证明:因为图12(a)存在 Hamilton圈,因此,由定理2.1,图12(b)也存在 Hamilton圈。因此,利用定理2.1,可知超立方体Q4存在 Hamilton圈,如图12(c)所示。

图11 超立方体Q4

4 结论

给定一个图,我们并不是直接讨论它的 Hamilton圈的存在性,而是讨论它的直接和的 Hamilton圈的存在问题。主要结果如下:如果图自身存在Hamilton圈,那么它的直接和的 Hamilton圈肯定存在;如果n阶图 G的极大 Hamilton子圈是Cn-1,那么它的直接和存在 Hamilton圈;我们还研究了n阶图的极大 Hamilton子圈是Cn-2的情况,并得到了三个充分条件。这种思路有助于我们研究图自身的 Hamilton圈问题,然而图的直接和中是否存在Hamilton圈的充分必要条件却难以找到,它值得我们进一步研究。

[1]Lih-Hsing Hsu,Cheng-Kuan Lin.Graph Theo ry and Intrerconnection Networks[J].CRC Press,2008(9):171-221.

[2]Gary Chartrand,Ping Zhang(美).图论导引[M].北京:人民邮电出版社,2007:122-132.

[3]JDouglas B West(美).图论导引[M].北京:机械工业出版社,2006:229-231.

[4]Bondy J A,M urty U S R.Graph Theory w ith App lications[M].Macmillan Press Ltd.,1976:3-5.

[5]Reinhard Diestel.Graph Theory 3rd ed[M].北京 :世界图书出版公司北京公司,2008:275-278.

[6]宋玉梅.关于 Hamilton图的充分必要条件[J].长春大学学报,1999(3):15-16.

[7]Chvátal V,Hamilton cycles.In the Traveling Salesman Problem:A Guided Tour of Combinato rial Op timization[M].Wiley,1985:403-429.

[8]Jackson B.Hamilton cycles in regular 2-connected graphs[M].J.Comb.Th.(B)29(1980):27-46.

[9]Zhu Y J,Z H Liu,Z G Yu.An imp rovement of Jackson’s result on Hamilton cycles in regular 2-connected graphs[M].Proc.Burnaby North-Holland,1985,:237-247.

A Study of Ham ilton Cycles in the D irect Sum of a Graph

HU Y-an zhong1,YEBo1,2
(1.Computer College,Hubei University of Technology,Wuhan 430068,China;2.Dep t.of Automotive Eng.,Shiyan Technical Institute,Shiyan 442000,China)

This paper defines the direct sum of a graph,and discusses the existenceof the Hamilton cycles in the direct sum of a graph.When the graph itself has a Hamilton cycle,the Hamilton cycle also exists in the direct sum of the graph.Let G be a graph of order n,if themaximum Hamilton sub-cycle is isomo rphic to the Cn-1,then its direct sum has a Hamilton cycle;it was also studied that themaximum Hamilton sub-cycle is isomorphic to the Cn-2,fo r a graph of order n,and obtained three sufficient conditions.Finally,the app lication of these p ropositions is illustrated w ith the hypercube Q4 as an examp le.

Hamilton cycle;direct sum;isomorphic graph;hypercube

O157

A

1008-4738(2010)03-0103-04

2010-05-10

胡延忠(1963-),男,湖北工业大学计算机学院教授,研究方向:数字图像处理,算法设计,软件工程;叶 波(1970-),男,湖北工业大学计算机学院在读硕士,十堰职业技术学院汽车系副教授。