N維“格子籠”圖的Hamilton問題

唐干武, 王 敏

(1.桂林師范高等專科學校數學與計算機科學系,廣西桂林 541001; 2.煙臺大學數學與信息科學系,山東煙臺 264005)

N維“格子籠”圖的Hamilton問題

唐干武1, 王 敏2

(1.桂林師范高等專科學校數學與計算機科學系,廣西桂林 541001; 2.煙臺大學數學與信息科學系,山東煙臺 264005)

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

n維“格子籠”圖;Hamilton圈;計算機基色;色階

1 基本概念

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

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

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

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

設ri(i=1,2,…,n,n≥2)是大于或等于1的整數,對無向圖G,其頂點集為

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

2 主要結果及證明

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

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

引理2.1[3]一個簡單無向圖為偶圖的充要條件是不含奇圈.

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

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

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

表1 圖G的頂點

(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中也是相鄰的.因為r3是奇數,所以表1排列的頂點共有偶數行,于是易找出G的Hamilton圈.例如,如圖1示意的連接方式就構成G中的一個Hamilton圈.

圖1 Hamilton圈示意圖

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

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

存在Hamilton圈的充要條件是n為奇數.

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

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

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

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

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

[4] 唐干武,王敏.邊數q≥C2p-1-1的(p,q)圖的泛圈性研究[J].江西師范大學學報,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

廣西壯族自治區教育廳科研項目(200807MS032)