国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

平面圖的動態(tài)著色

2010-02-09 11:25:00趙克文
關(guān)鍵詞:連通分支種顏色平面圖

林 越, 趙克文

(瓊州學(xué)院數(shù)學(xué)系 海南三亞572022)

平面圖的動態(tài)著色

林 越, 趙克文

(瓊州學(xué)院數(shù)學(xué)系 海南三亞572022)

研究平面圖的動態(tài)著色數(shù),通過定義一個算法得到強(qiáng)導(dǎo)出圖.利用顏色對換的思想來研究平面圖動態(tài)著色的上界問題,得到結(jié)論:若G是平面圖,則χd(G)≤5.

算法;強(qiáng)導(dǎo)出圖;動態(tài)著色

0 引言

圖的著色理論在圖論中占有重要地位,其結(jié)論有著廣泛的應(yīng)用.關(guān)于圖G=(V,E),v∈V(G)的頂點(diǎn)度定義為圖G中與v關(guān)聯(lián)的邊的數(shù)目,記為dG(v),v的鄰域記為N(v).圖G的正常k頂點(diǎn)著色,簡稱圖的k頂點(diǎn)著色,用k種顏色對G的各頂點(diǎn)進(jìn)行著色,使得任意相鄰的2點(diǎn)著不同的顏色.若G至少有1個正常k頂點(diǎn)著色,就稱G是正常k點(diǎn)可著色的.使G是k點(diǎn)可著色的數(shù)k的最小值稱為圖G的色數(shù),記為χ(G)= k,則稱G為k色圖.圖G的動態(tài)k著色是一個映射c:V(G)→C(k)={1,2,…,k},滿足:①如果uv∈E(G),則c(u)≠c(v);②對?v∈V(G),|c(N(v))|≥m in{2,dG(v)}.可以正常(k,2)著色的最小k為G的動態(tài)著色數(shù),記為χd(G).本文所研究的圖除特別說明外,均為簡單有限連通圖,文中沒給出的定義或術(shù)語可參考文獻(xiàn)[1].

文獻(xiàn)[2]首次提出了動態(tài)著色的概念;文獻(xiàn)[3]中討論了一些關(guān)于動態(tài)著色的性質(zhì),并證明一般圖的χd(G)≤Δ+3;文獻(xiàn)[4]研究了Pseudo-Halin圖的動態(tài)著色;文獻(xiàn)[5]研究了單圈圖和雙圈圖的動態(tài)色數(shù),并得到它們的動態(tài)色數(shù)是3或4;文獻(xiàn)[6]研究了沒有分支和C5同構(gòu)的圖的動態(tài)著色.本文主要討論平面圖動態(tài)著色的上界問題,得到定理1,即若G是平面圖,則χd(G)≤5.

1 預(yù)備知識

在經(jīng)典“平面圖是5可頂點(diǎn)著色的”證明過程中,先找圖G的i色頂與j色頂?shù)膶?dǎo)出子圖Gi,j:i色與j色交替出現(xiàn)的一條軌道,然后對換該導(dǎo)出子圖的i色與j色,不影響圖G的正常著色.

把這一思想運(yùn)用到“平面圖是5可動態(tài)著色的”中來,首先找圖G的i色頂與j色頂強(qiáng)導(dǎo)出圖Hi,j:從任一著i色頂點(diǎn)v1開始,檢查其鄰域N(v1),若存在著j色的頂v2,那么把v1,v2看成Hi,j的2個頂點(diǎn),把v1, v2看成Hi,j的一條邊,接著繼續(xù)檢查v2的鄰域N(v2),重復(fù)下去,直到對于vk(vk著i色或者j色之一,不妨設(shè)vk著j色)來說,在其鄰域N(vk)中已經(jīng)不存在與其相鄰并且著i色頂點(diǎn),否則可以繼續(xù)重復(fù)下去,又因為本身著j色,當(dāng)然也不存與其相鄰并且著j色頂點(diǎn).這時檢查vk鄰域中的任一點(diǎn)vl,若滿足在NG(vl)-vk中任一頂點(diǎn)都著i色,連接其中著i色的一點(diǎn)vk+1,把vk+1并入Hi,j已有的頂點(diǎn)集,把vkvk+1并入Hi,j已有的邊集,然后又從vk+1開始檢查其鄰域,直到不能進(jìn)行下去為止.顯然,Hi,j也是i色與j色交替出現(xiàn)的一條軌道.

根據(jù)以上思想,給出強(qiáng)導(dǎo)出圖算法具體步驟如下:

若已存在=G(V,E)的一個頂點(diǎn)著色c,記c(i)={v|c(v)=i,v∈G}.

Step1設(shè)Hi,j=(V′,E′),V′=?,E′=?.

Step2設(shè)v0∈c(i),若不存在與其相鄰并且著j色的頂點(diǎn),轉(zhuǎn)Step3;若存在與其相鄰且著j色的頂點(diǎn)v1,V′∶=V′∪{v0,v1},E′∶=E′∪{v0v1},i∶=j,重復(fù)Step2直到不存在這樣的頂點(diǎn),結(jié)束.這時把最后一個并入V的頂點(diǎn)記為vk,vk著i色或者j色之一,不妨設(shè)vk著j色.

Step3若不存在頂點(diǎn)vl,滿足在NG(vl)-vk中任一頂點(diǎn)都著i色,結(jié)束.若存在這樣的頂點(diǎn)vl,V′∶= V′∪{v′l},E′∶=E′∪{vkv′l},其中v′l為NG(vl)-vk中著i色的任一頂點(diǎn).轉(zhuǎn)Step2.

通過以上作法得到的圖稱為i色頂和j色頂?shù)膹?qiáng)導(dǎo)出圖,記為Hi,j.在Step3中,選取的v′l為NG(vl)-vk中著i色的任一頂點(diǎn),那么很顯然Hi,j不唯一.

命題1如果圖G是平面圖,那么構(gòu)造Hi,j時添加的邊得到G′仍然是平面圖.

證明由構(gòu)造Hi,j的作法,所添加的邊是vkv′l,其中v′l為NG(vl)-vk中都著i色的任一頂點(diǎn),只需考慮添加的邊是否會破壞圖G的平面性即可.若存在NG(vl)-vk中的某一頂點(diǎn)與vk在同一個圈的內(nèi)部,那么添加邊vkv′l后,不破壞圖G的平面性.若NG(vl)-vk全都在有一個圈C內(nèi)部,而vk在這個圈的外部,可以斷定vl位于圈C上,所以必還有一頂v′l位于圈C上,又假設(shè)vk位于C的外部,所以添加邊vkv′l后也不會破壞圖G的平面性,G′=G+{vkv′l}仍然是平面圖.證畢.

命題2若已對平面圖G進(jìn)行動態(tài)著色,對換圖Hi,j中i,j兩種顏色不影響圖G的動態(tài)著色.

證明由Hi,j的作法,Hi,j是一i色與j色交替出現(xiàn)的子圖,且由Step3可知,交換后能保證每個頂點(diǎn)的鄰域至少能著2種顏色的動態(tài)著色性質(zhì)不變.證畢.

2 定理1的證明

現(xiàn)在證明引言中提出的定理1.

證明設(shè)G是連通平面圖,對G的頂點(diǎn)數(shù)n進(jìn)行歸納證明.

當(dāng)n≤5時,定理顯然成立.假設(shè)n≤k-1時定理1已成立,只要證明n=k時定理也成立即可.

由于G是平面圖,δ≤5,設(shè)d(v0)≤5.

記G1=G-v0+xy,其中,x,y分別為N(v0)中的任意2個頂點(diǎn),若已存在這樣的一條邊則不再連接.

若d(v0)≤4,由歸納假設(shè)χd(G1)≤5,即G1中已用5種顏色動態(tài)著色,再把v0與它在G中的鄰域集(不超過4個)相異的顏色著色,可知,對于v0點(diǎn)也滿足動態(tài)著色的定義,其他點(diǎn)不影響,所以d(v0)≤5.

若d(v0)=5,設(shè)v1,v2,v3,v4,v5是v0的鄰頂點(diǎn),不妨設(shè)v1,v2,v3,v4,v5依順時針排列(不然重新對這5個頂點(diǎn)編號).由歸納假設(shè)χd(G1)≤5,設(shè)G1已用5種顏色1,2,3,4,5動態(tài)著色,且v1,v2,v3,v4,v5在G1中上的色分別是1,2,3,4,5,考慮H1,3.

(1)若v1與v3分別居于2個連通分支中,在含v1的連通分支中交換1色和3色,由命題2知不影響動態(tài)著色,在G中把v0上1色即得G的用5種顏色的動態(tài)著色,所以d(v0)≤5.

(2)若v1與v3同在一個H1,3的連通分支中,則在G1中存在軌P(v1,v3),此軌道上的1色與3色交替出現(xiàn).考慮H2,4,若v2與v4分屬于2個連通分支中,與(1)相似,可得d(v0)≤5.而v2與v4不會出現(xiàn)在H2,4的同一個連通分支中,不然存在軌P(v2,v4),其上的頂2色與4色交替出現(xiàn),但在G中,有一個圈C0:v0v1P (v1,v3)v3v1.于是P(v1,v3)與P(v2,v4)必有公共頂點(diǎn),這個公共頂點(diǎn)P(v1,v3)要求它是1色或者3色,而P(v2,v4)要求它是2色或者4色,這是不可能的.證畢.

3 結(jié)束語

動態(tài)著色是正常著色的一種“衍生物”,它有著廣泛的應(yīng)用.幾類特殊圖和平面圖的動態(tài)著色的上界已經(jīng)研究清楚了,而一般圖的動態(tài)著色的上界到目前為止還沒有明確的結(jié)論,這也是動態(tài)著色問題的難點(diǎn)之一.

參考文獻(xiàn):

[1] Bondy J A,M urty U SR.Graph Theory with App lications[M].Macmillan:North-Holland Elservie,1976.

[2] Montgomery B.Dynamic colo ring[D].West Virginia:West Virginia University,2001:25-37.

[3] Lai H J,Montgomery B,Poon H.Upper bounds of dynamic chromatic number[J].A rs Combinatoria,2003,68(3): 193-201.

[4] Meng X Y,M iao L Y,Su B T,et al.The dynamic coloring numbers of Pseudo-Halin graphs[J].A rs Combincto ria, 2006,79:3-10.

[5] 秦健,張巖.單圈圖和雙圈圖的動態(tài)色數(shù)[J].山東大學(xué)學(xué)報:理學(xué)版,2007,42(10):37-40.

[6] Akbari S,Ghanbari M,Jahanbekam S.On the list dynamic coloring of graphs[J].Discrete App lied Mathematics,2009, 157(14),3005-3007.

Dynam ic Coloring for Planar Graph

L IN Yue, ZHAO Ke-w en
(Department of M athem atics,Qiongzhou University,Sanya 572022,China)

A dynamic coloring fo r p lanar graph is mainly discussed.An induced graph,obtained by defining an algorithm,is used to study the upper bounds of dynamic chromatic number of the p lanar graph.And,the conclusion is:if G is p lanar,thenχd(G)≤5.

algo rithm;induced graph;dynam ic colo ring

TP 301.5

A

1671-6841(2010)03-0034-03

2010-04-01

海南省自然科學(xué)基金資助項目,編號10501.

林越(1981-),男,助教,碩士,主要從事圖論與算法研究,E-mail:linyue_306@163.com;通訊聯(lián)系人:趙克文(1964-),男,教授,主要從事圖論研究,E-mail:kewen.zhao@yahoo.com.cn.

猜你喜歡
連通分支種顏色平面圖
偏序集的序連通關(guān)系及其序連通分支
關(guān)于圖的距離無符號拉普拉斯譜半徑的下界
《別墅平面圖》
《別墅平面圖》
觀察:顏色數(shù)一數(shù)
孩子(2019年10期)2019-11-22 08:06:01
《景觀平面圖》
平面圖的3-hued 染色
一個圖論問題的簡單證明
新課程(下)(2015年9期)2015-04-12 09:23:30
交換環(huán)的素譜與極大譜的連通性
迷人的顏色
娃娃畫報(2009年11期)2009-12-07 03:38:20
云和县| 南京市| 高邑县| 获嘉县| 柞水县| 台北县| 二连浩特市| 林芝县| 海城市| 利辛县| 平乐县| 锦屏县| 万全县| 永寿县| 綦江县| 公安县| 古田县| 宁城县| 永仁县| 梁山县| 怀来县| 永德县| 卢湾区| 德江县| 新巴尔虎左旗| 集安市| 灵宝市| 博客| 郑州市| 方山县| 青岛市| 来凤县| 雷州市| 昭觉县| 浪卡子县| 高碑店市| 张家口市| 香河县| 嵩明县| 婺源县| 沧州市|