N維“格子籠”圖的Hamilton問(wèn)題

唐干武, 王 敏

(1.桂林師范高等專科學(xué)校數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,廣西桂林 541001; 2.煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)系,山東煙臺(tái) 264005)

N維“格子籠”圖的Hamilton問(wèn)題

唐干武1, 王 敏2

(1.桂林師范高等?？茖W(xué)校數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,廣西桂林 541001; 2.煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)系,山東煙臺(tái) 264005)

對(duì)n維“格子籠”圖的Hamilton性進(jìn)行了研究,得到了判定n維“格子籠”圖是Hamilton圖的一個(gè)非常簡(jiǎn)潔的充分必要條件.

n維“格子籠”圖;Hamilton圈;計(jì)算機(jī)基色;色階

1 基本概念

在計(jì)算機(jī)色彩設(shè)置中,紅、綠、藍(lán)是色彩設(shè)置中的三種基色,它們可分有0～255個(gè)一共256色階,我們可以用一個(gè)三維向量(R,G,B),(R,G,B為整數(shù)且0≤R,G,B≤255)來(lái)描述一種顏色.人們提出一個(gè)有趣的問(wèn)題:能否從(0,0,0)開始,把所有顏色一一顯示出來(lái),要求任意相鄰兩種顏色的色階之差為1,并最終回到(0,0,0).即若記Ci=(Ri,Gi,Bi),(Ri,Gi,Bi取0～255間的整數(shù)),要確定一個(gè)序列

C0(0,0,0),C1(R1,G1,B1),C2(R2,G2,B2),…,C2553(R2553,G2553,B2553),C0(0,0,0),

使得對(duì)序列中的任意相鄰兩個(gè)元素Ci(Ri,Gi,Bi)與Cj(Rj,Gj,Bj),有

這樣的問(wèn)題可以歸結(jié)為:對(duì)于一個(gè)這樣的圖G,其頂點(diǎn)集為向量(x,y,z)的集合,其中x,y,z分別是0到255之間的整數(shù).當(dāng)表示兩頂點(diǎn)的向量(xi,yi,zi),(xj,yj,zj)的差的模為1時(shí),這兩頂點(diǎn)相鄰接(即存在邊),這樣的圖是否存在Hamilton圈的問(wèn)題.文[1]將這樣的圖稱為“格子籠”圖,并在文中證明了這樣的圖存在Hamilton圈.文[2]討論了當(dāng)x,y,z取值的上界各不相同時(shí)所構(gòu)成的“格子籠”圖的Hamilton圈存在性問(wèn)題.本文將三維“格子籠”圖推廣到n維“格子籠”圖(n≥2),并得到n維“格子籠”圖存在Hamilton圈的充分必要條件.

設(shè)ri(i=1,2,…,n,n≥2)是大于或等于1的整數(shù),對(duì)無(wú)向圖G,其頂點(diǎn)集為

對(duì)于給定的ri(i=1,2,…,n,n≥2),圖G=(V,E)稱為n維“格子籠”圖.這樣的n維“格子籠”圖是否存在Hamilton圈,是一個(gè)有趣的問(wèn)題.下面我們來(lái)具體討論.

2 主要結(jié)果及證明

定理2.1 n維“格子籠”圖G存在Hamilton圈的充要條件是ri(i=1,2,…,n,n≥2)中至少有一個(gè)為奇數(shù).

定理的必要性證明要用到下面兩個(gè)引理.

引理2.1[3]一個(gè)簡(jiǎn)單無(wú)向圖為偶圖的充要條件是不含奇圈.

引理2.2[3]若G=(V,E)是一個(gè)Hamilton圖,則對(duì)于頂點(diǎn)集V的每一個(gè)非空子集S,均有

這里ω(G-S)表示子圖(G-S)的連通分支數(shù).

定理的證明 充分性的證明.若ri(i=1,2,…,n,n≥2)中至少有一個(gè)為奇數(shù)時(shí),不妨設(shè)r3是奇數(shù),此時(shí)只需在n維“格子籠”圖G中找出一個(gè)Hamilton圈即可.現(xiàn)將G的頂點(diǎn)列成表1.

表1 圖G的頂點(diǎn)

(0,0,0,r4,0,…,0)(1,0,0,r4,0,…,0),(2,0,0,r4,0,…,0),…,(r1,0,0,r4,0,…,0)…………(0,0,0,r4,r5,…,rn)(1,0,0,r4,r5,…,rn),(2,0,0,r4,r5,…,rn),…,(r1,0,0,r4,r5,…,rn) (0,1,0,r4,r5,…,rn)(1,1,0,r4,r5,…,rn),(2,1,0,r4,r5,…,rn),…,(r1,1,0,r4,r5,…,rn)…………(0,r2-1,0,r4,r5,…,rn)(1,r2-1,0,r4,r5,…,rn),(2,r2-1,0,r4,r5,…,rn),…,(r1,r2-1,0,r4,r5,…,rn) (0,r2,0,r4,r5,…,rn)(1,r2,0,r4,r5,…,rn),(2,r2,0,r4,r5,…,rn),…,(r1,r2,0,r4,r5,…,rn) (0,r2,1,r4,r5,…,rn)(1,r2,1,r4,r5,…,rn),(2,r2,1,r4,r5,…,rn),…,(r1,r2,1,r4,r5,…,rn) (0,r2-1,1,r4,r5,…,rn)(1,r2-1,1,r4,r5,…,rn),(2,r2-1,1,r4,r5,…,rn),…,(r1,r2-1,1,r4,r5,…,rn)…………(0,1,1,r4,r5,…,rn)(1,1,1,r4,r5,…,rn),(2,1,1,r4,r5,…,rn),…,(r1,1,1,r4,r5,…,rn) (0,0,1,r4,r5,…,rn)(1,0,1,r4,r5,…,rn),(2,0,1,r4,r5,…,rn),…,(r1,0,1,r4,r5,…,rn)…………(0,r2,r3,r4,r5,…,rn)(1,r2,r3,r4,r5,…,rn),(2,r2,r3,r4,r5,…,rn),…,(r1,r2,r3,r4,r5,…,rn) (0,r2-1,r3,r4,r5,…,rn)(1,r2-1,r3,r4,r5,…,rn),(2,r2-1,r3,r4,r5,…,rn),…,(r1,r2-1,r3,r4,r5,…,rn)…………(0,1,r3,r4,r5,…,rn)(1,1,r3,r4,r5,…,rn),(2,1,r3,r4,r5,…,rn),…,(r1,1,r3,r4,r5,…,rn) (0,0,r3,r4,r5,…,rn)(1,0,r3,r4,r5,…,rn),(2,0,r3,r4,r5,…,rn),…,(r1,0,r3,r4,r5,…,rn)

顯然,表1中任意相鄰的兩個(gè)頂點(diǎn)在圖G中也是相鄰的.因?yàn)閞3是奇數(shù),所以表1排列的頂點(diǎn)共有偶數(shù)行,于是易找出G的Hamilton圈.例如,如圖1示意的連接方式就構(gòu)成G中的一個(gè)Hamilton圈.

圖1 Hamilton圈示意圖

必要性的證明.若所有ri(i=1,2,…,n)為偶數(shù),則n維“格子籠”圖G的頂點(diǎn)數(shù)(r1+1)(r2+1)…(rn+1)為奇數(shù).又由于n維“格子籠”圖G不存在奇圈,所以由引理3.1知G是偶圖.設(shè)此偶圖的二分類為{S1,S2}.因|S1|+|S2|=(r1+1)(r2+1)…(rn+1)為奇數(shù),于是不妨設(shè)|S1|＞|S2|,由偶圖的性質(zhì)知G-S2=S1是G的獨(dú)立集,所以ω(G-S2)=|S1|＞|S2|.根據(jù)引理3.2,n維“格子籠”圖G不是Hamilton圖,即G不存在Hamilton圈.

推論1 三維“格子籠”圖G=(V,E),其中

存在Hamilton圈的充要條件是n為奇數(shù).

推論2 三維“格子籠”圖G=(V,E),其中

存在Hamilton圈的充要條件是ni(i=1,2,3)中至少有一個(gè)為奇數(shù).

[1] 郭常忠,王敏.一種基于RGB三基色的計(jì)算機(jī)色彩的有序顯示算法[J].計(jì)算機(jī)研究與發(fā)展,1997,34(4)：312-315.

[2] 李政,王敏.“格子籠”圖的Hamilton圈問(wèn)題[J].大學(xué)數(shù)學(xué),2007,23(1)：147-150.

[3] Bondy J A,Murty U S R.Graph theory with applications[M].New York：MacMillan Press,1976.

[4] 唐干武,王敏.邊數(shù)q≥C2p-1-1的(p,q)圖的泛圈性研究[J].江西師范大學(xué)學(xué)報(bào),2006,30(6)：556-559.

Hamilton Problem onn-Dimensional Cube Graph

TA N G Gan-w u1, WA N G Min2
(1.Department of Mathematics and Computer Science,Guilin Normal College,Guilin 541001,China; 2.Department of Mathematics and Information Science,Yantai University,Yantai 264005,China)

We study the Hamilton properties ofn-dimensional cube graph and give the very simple necessary and sufficient conditions such thatn-dimensional cube graph is a Hamilton graph.

n-dimensional cube graph;Hamilton graph;computer color;levels

O157.6

A

1672-1454(2010)03-0116-04

2007-10-08

廣西壯族自治區(qū)教育廳科研項(xiàng)目(200807MS032)