胡延忠,葉 波,2

(1.湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,湖北武漢430068;2.十堰職業(yè)技術(shù)學(xué)院汽車系,湖北十堰442000)

圖的直接和的 Hamilton圈研究

胡延忠1,葉 波1,2

(1.湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,湖北武漢430068;2.十堰職業(yè)技術(shù)學(xué)院汽車系,湖北十堰442000)

本文定義了圖的直接和的概念,討論了圖的直接和中 Ham ilton圈的存在性。當(dāng)圖本身存在 Hamilton圈時(shí),它的直接和中的 Hamilton圈也存在;設(shè)圖 G是n階圖,如果它的極大Ham ilton子圈與Cn-1同構(gòu),那么它的直接和存在 Ham ilton圈;本文還研究了極大 Ham ilton子圈同構(gòu)于Cn-2的n階圖并得到了三個(gè)充分條件。本文最后用超立方體Q4為例展示了這些命題的應(yīng)用。

Hamilton圈;直接和;同構(gòu)圖;超立方體

0 導(dǎo)論

無向圖中 Ham ilton圈是遍歷圖中每個(gè)頂點(diǎn)恰好一次又返回起點(diǎn)的圈。確定一個(gè)圖中這樣的圈是否存在就是 Hamilton圈問題,它是一個(gè)NP完全問題。實(shí)際應(yīng)用(特別是計(jì)算機(jī)網(wǎng)絡(luò)中的應(yīng)用)和計(jì)算復(fù)雜性的研究推動(dòng)了 Ham ilton圈問題的研究[1][2][3][4]。Hamilton圈問題的研究由來已久。Dirac于1952就證明了:如果 G是至少有三個(gè)頂點(diǎn)的簡(jiǎn)單圖且每個(gè)頂點(diǎn)的度數(shù)大于等于 n/2存在Hamilton圈;Bondy-Chvátal1972年給出了定理:一個(gè)圖存在 Hamilton圈的充要條件是它的閉包存在 Hamilton圈;Tutte也于1956年證明每一個(gè)4-連通的平面圖存在 Ham ilton圈[5]。宋玉梅在1999年證明:一個(gè)簡(jiǎn)單圖存在 Hamilton圈的充要條件是其 PerGR非零[6]。與此同時(shí),對(duì)一些特殊圖的Hamilton圈問題的研究也很活躍。例如,Fleischner研究了圖的平方中 Hamilton圈問題,并于1974年證明了:如果 G是一個(gè)2-連通的圖,那么G2存在 Hamilton圈[5];Chvátal于1985年研究了旅行商問題中 Hamilton圈[7];Jackson1980年證明了度數(shù)至少為n(G)/3的任意簡(jiǎn)單正則圖存在Hamilton圈[8],這一結(jié)論由Zhu Y.J.、Z.H.Liu和 Z.G.Yu等人進(jìn)行了改進(jìn)[9]。本文討論圖的直接和的Ham ilton圈問題。

1 基礎(chǔ)知識(shí)

集合V 1={1,2,3}和集合V 2={a,b}的笛卡爾積是一個(gè)集合 ,記為 V1×V2={〈1,a〉,〈1,b〉,〈2,a〉,〈2,b〉,〈3,a〉,〈3,b〉}。V1×V2的任意子集合稱為一個(gè)二元關(guān)系,例如,f={〈1,a〉,〈1,b〉,〈2,b〉,〈3,a〉}就是一個(gè)二元關(guān)系。映射是一種特殊的二元關(guān)系。

本文只考慮簡(jiǎn)單連通圖。

圖1 圖 G和它的同構(gòu)圖

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

如圖1所示,存在一個(gè)從圖 G到圖 H的同構(gòu):α={ 〈1,x〉,〈2,y〉,〈3,z〉}。圖 1(a)和圖1(b)分別表示圖 G和它的同構(gòu)圖 H。

圖2是 Petersen圖,它是3-連通的,但是沒有Hamilton圈。

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

顯然,一個(gè)圖到自身的直接和是3-聯(lián)通的,而這正好是一個(gè)圖存在 Ham ilton圈的必要條件。

2 主要定理

當(dāng)圖 G沒有 Hamilton圈時(shí),結(jié)果將會(huì)怎么樣?

例題2.2 Petersen圖沒有 Hamilton圈,然而它的直接和卻存在 Hamilton圈,如圖2所示。

例題2.3 圖5(a)是一個(gè)非 Hamilton圖,它的直接和存在 Hamilton圈,如圖5(b)所示,其中表示同構(gòu)映射(下同)。

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

例題2.4 圖6(a)是一個(gè)非 Ham ilton圖,它的直接和沒有 Hamilton圈,如圖6(b)所示。

問題2.5 一個(gè)圖滿足什么條件時(shí),它的直接和存在 Ham ilton圈呢?充分必要條件也許難以發(fā)現(xiàn),但是下列結(jié)論有很重要的意義。

圖7 極大Hamilton子圈的階數(shù)為n-1

證明:為了方便起見,假設(shè)圖 G的極大 Hamilton子圈為Cn-1且V(G)={1,2,… ,n}。因?yàn)閳DG是連通圖,所以不在Cn-1上的頂點(diǎn)n必和Cn-1某一頂點(diǎn)鄰接,如圖7(a)所示。圖7(b)是包含 G的所有頂點(diǎn)子圖的直接和,路徑:1n f(n)f(1)f(n-1)…f(3)f(2)23…(n-1)1是一條 Hamilton圈。因此圖 G的直接和存在 Hamilton圈。

(1)不在極大Hamilton子圈上的兩頂點(diǎn)是鄰接的。

(2)不在極大 Hamilton子圈上的兩頂點(diǎn)是不鄰接的,但滿足下列條件之一。設(shè)1和2分別是極大Hamilton子圈上的兩頂點(diǎn),x和y是不在極大Hamilton子圈上的兩頂點(diǎn),且分別和1和2鄰接。

a.在頂點(diǎn)1和頂點(diǎn)2之間(順時(shí)針方向)沒有其他頂點(diǎn)。

b.在頂點(diǎn)1和頂點(diǎn)2之間(順時(shí)針方向)具有一個(gè)(或奇數(shù)個(gè))頂點(diǎn),且在頂點(diǎn)2和頂點(diǎn)1之間(順時(shí)針方向)也具有一個(gè)(或奇數(shù)個(gè))頂點(diǎn)。

c.在頂點(diǎn)1和頂點(diǎn)2之間(順時(shí)針方向)具有兩個(gè)(或偶數(shù)個(gè))頂點(diǎn),且在頂點(diǎn)2和頂點(diǎn)1之間(順時(shí)針方向)也具有兩個(gè)(或偶數(shù)個(gè))頂點(diǎn)。

證明:1)為了方便起見,假設(shè)1,2,3是極大Ham ilton子圈上彼此連接的三個(gè)頂點(diǎn),假設(shè)x和y不在極大 Hamilton子圈上且和頂點(diǎn)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 應(yīng)用舉例

例題3.1 超立方體Q4存在 Ham ilton圈。

證明:因?yàn)閳D12(a)存在 Hamilton圈,因此,由定理2.1,圖12(b)也存在 Hamilton圈。因此,利用定理2.1,可知超立方體Q4存在 Hamilton圈,如圖12(c)所示。

圖11 超立方體Q4

4 結(jié)論

給定一個(gè)圖,我們并不是直接討論它的 Hamilton圈的存在性,而是討論它的直接和的 Hamilton圈的存在問題。主要結(jié)果如下:如果圖自身存在Hamilton圈,那么它的直接和的 Hamilton圈肯定存在;如果n階圖 G的極大 Hamilton子圈是Cn-1,那么它的直接和存在 Hamilton圈;我們還研究了n階圖的極大 Hamilton子圈是Cn-2的情況,并得到了三個(gè)充分條件。這種思路有助于我們研究圖自身的 Hamilton圈問題,然而圖的直接和中是否存在Hamilton圈的充分必要條件卻難以找到,它值得我們進(jìn)一步研究。

[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(美).圖論導(dǎo)引[M].北京:人民郵電出版社,2007:122-132.

[3]JDouglas B West(美).圖論導(dǎo)引[M].北京:機(jī)械工業(yè)出版社,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]宋玉梅.關(guān)于 Hamilton圖的充分必要條件[J].長(zhǎng)春大學(xué)學(xué)報(bào),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-),男,湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院教授,研究方向:數(shù)字圖像處理,算法設(shè)計(jì),軟件工程;葉 波(1970-),男,湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院在讀碩士,十堰職業(yè)技術(shù)學(xué)院汽車系副教授。