吳偉琦

(1．廣西工業(yè)職業(yè)技術(shù)學院建筑工程系, 中國 南寧 530001；2．桂林師范高等專科學校數(shù)學與計算機科學系,中國 桂林 541001；3．百色學院科研處，中國 百色 533000)

在計算機視頻監(jiān)示器和電視機視頻顯示中的色彩是通過紅(R)、綠(G)、藍(B)3種基色來具體體現(xiàn)的，每種基色各有0～255共256種色階，3種基色的色階的每種組合代表一種顏色，改變視頻監(jiān)視器中某個顏色寄存器的值,在監(jiān)視器中即可產(chǎn)生出相應的可顯示顏色.

隨著視頻顯示技術(shù)的不斷發(fā)展,視頻顯示器上所能顯示的顏色也將會越來越多,基色的種數(shù)也將不局限于3種,各種基色的色階的取值范圍也將不局限在0～255之間.

文獻[1]討論了三基色的色彩的有序平滑顯示算法,且只研究了每種基色取值范圍都是0～255的情形，文獻[2]討論了三基色的基色色階的取值范圍不同時的有序平滑顯示算法．本文利用圖論的方法從理論上討論基色種數(shù)為4種且每種基色的色階取值范圍不同的情形下的有序平滑顯示算法.

1 基本概念

類似于文獻[1]給出下列基本概念：

定義1稱C(g1,g2,g3,g4)為色彩函數(shù)，其中g(shù)1,g2,g3,g4為色彩的4種基色的色階,C(g1,g2,g3,g4)是由4種基色G1,G2,G3,G4的取值組合成的色彩值. 稱C(g1,g2,g3,g4)組成的集合為色彩集,記作

C={C(g1,g2,g3,g4)|0≤gj≤rj,(gj,rj是正整數(shù),j=1,2,3,4)}.

定義2對于色彩集C中的任意兩個不同的元素Cx=Cx(g1x,g2x,g3x,g4x)和Cy=Cy(g1y,g2y,g3y,g4y),定義函數(shù)關(guān)系：Φ(Cx,Cy)=|g1x-g1y|+|g2x-g2y|+|g3x-g3y|+|g4x-g4y|,若Φ(Cx,Cy)=1,則稱色彩值Cx和Cy是1-相鄰的, 此時稱Φ為色彩值1-相鄰規(guī)則.

對于色彩集C,根據(jù)色彩值1-相鄰規(guī)則,可以構(gòu)造一個色彩值1-相鄰點對集：

D(C)={(Cx,Cy)|Cx,Cy∈C,且Cx≠Cy,Φ(Cx,Cy)=1}.

定義3對于任意的Cx,Cy∈D(C),構(gòu)造一條邊連結(jié)Cx,Cy兩點,記為e(Cx,Cy),稱e(Cx,Cy)為色彩值1-相鄰規(guī)則Φ下的色彩相鄰邊.

顯然,所有色彩相鄰邊e(Cx,Cy)可構(gòu)成一集合,記為E,即E={e(Cx,Cy)|Cx,Cy∈D(C)且Cx≠Cy}.

由以上三定義,可得到一種特殊的圖的定義.

定義4由色彩集C,色彩相鄰邊集E以及色彩值1-相鄰規(guī)則Φ構(gòu)成的三元有序數(shù)組G=(C,E,Φ)稱為基于G1,G2,G3,G4的四基色的色彩圖,簡稱色彩圖.

顯然，以上定義的色彩圖與圖論中圖的概念是完全一致的，相應的色彩顯示問題就轉(zhuǎn)換成了圖論上著名的Hamilton圈存在性問題，也即在色彩圖上是否存在Hamilton圈. 于是，對于以上定義的色彩圖,若在其上存在Hamilton圈，則存在一個全部色彩的計算機平滑循環(huán)顯示算法.

本文以G1,G2,G3,G4為坐標軸構(gòu)造四維空間坐標系,設g1,g2,g3,g4的取值范圍分別為: 0≤gj≤rj,(j=1,2,3,4),由此構(gòu)造一個四維立方體,對該立方體施以長為1的劃分,則可形成一個四維立體圖G,由于色彩函數(shù)值C(g1,g2,g3,g4)與四基色G1,G2,G3,G4的取值是一一對應的,于是可將四維立方體上的點(g1,g2,g3,g4),(0≤gj≤rj,j=1,2,3,4),與色彩值C(g1,g2,g3,g4)相對應,顯然,四維立方體圖G與色彩圖是同構(gòu)的,從而討論色彩圖的Hamilton圈的存在性,只需討論四維立方體圖G的Hamilton圈的存在性.

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

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

引理2[3]若G是Hamilton圖,則對V(G)的每個非空真子集S,均有ω(G-S)≤|S|. 其中ω(G-S)是圖(G-S)的連通分支數(shù).

定理1設四維立方體圖G=(C,E,Φ)中的頂點(g1,g2,g3,g4)各分量的取值范圍為: (0≤gj≤rj,j=1,2,3,4),則G存在Hamilton圈的充要條件是r1,r2,r3,r4中至少有一個為奇數(shù).

證必要性的證明，因為四維立方體圖G=(C,E,Φ)的頂點數(shù)等于(r1+1)(r2+1) (r3+1)(r4+1). 如果所有rj(j=1,2,3,4)為偶數(shù),則(r1+1)(r2+1) (r3+1)(r4+1) 為奇數(shù).又由于四維立方體圖G=(C,E,Φ)不存在奇圈,所以由引理3.1知它是偶圖,設此偶圖的二分類為{S1,S2},因|S1|+|S2|=(r1+1)(r2+1) (r3+1)(r4+1) 為奇數(shù),于是不妨設|S1|>|S2|,由偶圖的性質(zhì)知G-S2=S1是G的獨立集,所以ω(G-S2)=|S1|>|S2|,根據(jù)引理3.2,四維立方體圖G=(C,E,Φ)不是Hamilton圖.

充分性的證明,若ri(i=1,2,3,4)中至少有一個為奇數(shù),不妨設r3是奇數(shù),此時只需在四維立方體圖G中找出一個Hamilton圈即可.現(xiàn)將G的頂點列成表1.

表1 四維立方體圖G的頂點

續(xù)表

續(xù)表

圖1 G中的一個Hamilton圈示意圖

顯然,表中任意相鄰的兩個頂點在圖G中也是相鄰的.因為r3是奇數(shù),所以表1排列的頂點共有偶數(shù)行,于是易找出四維立方體圖G的Hamilton圈,例如,如圖1所示的連接方式就構(gòu)成四維立方體圖G中的一個Hamilton圈.

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

V={(r,g,b)|0≤r,g,b≤n且r,g,b和n是整數(shù),n≥1}

E={((rx,gx,bx),(ry,gy,by))||rx-ry|+|gx-gy|+|bx-by|=1}

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

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

V={(r,g,b)|0≤r≤n1,0≤g≤n2,0≤b≤n3且r,g,b和ni是整數(shù),ni>1(i=1,2,3)},

E={((rx,gx,bx),(ry,gy,by))||rx-ry|+|gx-gy|+|bx-by|=1}.

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

3 結(jié)束語

顯示技術(shù)從最初的單基色顯示、雙基色顯示到現(xiàn)今普遍使用的三基色顯示，且隨著科學技術(shù)的發(fā)展而不斷提高．目前對多基色顯示技術(shù)也在廣泛討論和研究，像四基色，六基色的LED顯示已開始應用了，本文討論的四基色平滑顯示算法為多基色技術(shù)提供了一個平滑顯示的理論依據(jù)．

參考文獻：

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

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

[3] BONDY J A, MURTY U S. Graph theory with applications[M]. London: Mac Millan Press, 1976.

[5] 唐干武, 唐高華, 王 敏. Erd?s-Sos猜想的一個結(jié)果[J]. 西南師范大學自然科學學報, 2009, 34(1): 24-27.

[6] WANG M, FANG X G. Parking a pair of graphs {(p,p-1),(p,p)} and slater’s problems[J]. J Chinese Syst Sci Math Sci, 1989, 9(2): 133-137.

[7] 唐干武，王 敏.包裝(p,p-2)圖和不含K3的(p,p+1)圖[J]. 江西師范大學自然科學學報,2005, 29(3): 220-223.

[8] YIN J H, LI J S. The Erd?s-Sòs conjecture for graphs whose complements contain noC4[J]. Acta Math Appl Sinica, 2004, 20(3): 397-400.

[9] WANG M, LI G J. On the a tree of orderpwith a (p,p+1)-graph[J]. J Syst Sci Comp, 2003, 16(1): 122-132.

[10] 方新貴, 王 敏. 包裝{(p,p-1),(p,p)}圖對和Slater問題[J]. 系統(tǒng)科學與數(shù)學, 1989, 9(2): 133-137.

[11] 唐干武, 王 敏. 一類圖的哈密頓分類[J]. 純粹數(shù)學與應用數(shù)學, 2009, 4(25): 711-715.

[12] 張智勇, 張遠平. 一些具有非固定步循環(huán)圖中生成樹的個數(shù)[J]. 湖南師范大學自然科學學報, 2007, 30(3): 18-21.