APP下载

N维“格子笼”图的Hamilton问题

2010-11-22唐干武

大学数学 2010年3期
关键词:色阶基色奇数

唐干武, 王 敏

(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)

猜你喜欢

色阶基色奇数
奇数凑20
奇数与偶数
念 旧
关于奇数阶二元子集的分离序列
基色与混合色
猎熊的孩子
巧用Photoshop CC2014反蒙版特效神速制作梦幻大片
猎熊的孩子
数码摄影课程中曝光技术环节教学体会
基于数字存档技术中缩微胶片密度影响因素研究