隨機圖的點魔幻全染色算法

宋 晨, 李敬文, 張蕎君

(蘭州交通大學(xué)電子與信息工程學(xué)院, 蘭州 730070)

圖染色問題一直是圖論[1]中的一個經(jīng)典課題,許多學(xué)者圍繞它進(jìn)行了一系列的研究和探索.近年來,信息技術(shù)的蓬勃發(fā)展有力地推動了圖論的進(jìn)步,許多新的概念被相繼提出,如點可區(qū)別全染色[2-3],邊魔幻全標(biāo)號以及點魔幻邊染色等等．

基于上述所提到的點魔幻標(biāo)號[13]和點可區(qū)別染色[14]等概念,本文提出了一種全新的染色——點魔幻全染色.通過借鑒點魔幻邊染色算法的核心思想并結(jié)合文獻(xiàn)[15],設(shè)計出一種新型的點魔幻全染色算法,得到了14個點以內(nèi)的路圖、星圖、扇圖、友誼圖、風(fēng)箏圖以及這些特殊圖組合得到的聯(lián)圖的結(jié)果,最后通過對實驗結(jié)果的分析,總結(jié)出若干定理及證明．

1 基本概念

定義2設(shè)圈圖Cm的頂點集為{u1,u2,…,um},星圖Sn的頂點集為{w0,w1,…,wn}.如果Cm和Sn有中心節(jié)點,分別用u1和w0表示,其中w0表示星心,Cm↑Sn表示將Sn的星心w0連接到Cm的任意一個頂點后得到的圖,則有V(Cm↑Sn)=V(Cm)∪V(Sn),E(Cm↑Sn)=E(Cm)∪E(Sn),|V(Cm↑Sn)|=|V(Cm)|+|V(Sn)|-|w0|,|E(Cm↑Sn)|=|E(Cm)|+|E(Sn)|．

圖1為頂點數(shù)為m的圈圖Cm和星圖Sn連接得到的聯(lián)圖Cm↑Sn(m≥4,n≥2且m-n=2)的示例．

圖1 Cm↑SnFig.1 Cm↑Sn

定義3風(fēng)箏圖(Kite):(n,t)-K是圈圖Cn中任意頂點與長度為t的路圖Pt端點相連接的圖,示例如圖2所示．

圖2 (n,t)-KFig.2 (n,t)-K

定義4n個C3組成的圖稱為友誼圖,記為T(2,n)(n≥2),示例如圖3所示．

圖3 T(2,n)Fig.3 T(2,n)

2 VMTC算法

根據(jù)點魔幻全染色的定義,本文提出了VMTC算法,先預(yù)處理輸入的鄰接矩陣,然后通過調(diào)整函數(shù)逐步破壞平衡,再利用平衡函數(shù)進(jìn)行判斷并建立新的平衡,慢慢趨向最優(yōu)解,完成對圖的染色過程．

2.1 函數(shù)設(shè)計

1) 預(yù)處理函數(shù)process()

① 輸入圖的鄰接矩陣．

② 計算出圖G(p,q)的點數(shù)p,邊數(shù)q,每個點的度degree以及最大度數(shù)maximumdegree．

③ 從鄰接矩陣右上角三角形開始,對點數(shù)和邊數(shù)逐個增加,并且保證色數(shù)要連續(xù)．

④ 使色和要接近最大度的色和或者等于,若不滿足,則返回第③步．

⑤ 輸出預(yù)處理后的鄰接矩陣．

2) 調(diào)整函數(shù)adjustment2()

① 讀取預(yù)處理后的圖的鄰接矩陣．

② 計算此時圖G(p,q)的點數(shù)p,邊數(shù)q,各個點的色和數(shù)sum．

③ 從右上角三角形開始,從左到右,從上到下依次進(jìn)行調(diào)整,每次增加1,且滿足色和數(shù)差值小于等于1．

④ 判斷色數(shù)是否連續(xù),若是,則執(zhí)行下一函數(shù),否則循環(huán)第③步．

3) 平衡函數(shù)balance()

① 判斷所有點色和是否相同,若是執(zhí)行下一個函數(shù),否則回到調(diào)整函數(shù)adjustment2()．

4) 輸出函數(shù)output()

① 判斷是否到達(dá)最大色數(shù)．

② 若達(dá)到,且滿足平衡函數(shù)balance(),則具有點魔幻全染色.若未達(dá)到,則循環(huán)調(diào)整函數(shù)adjustment2()與平衡函數(shù)balance(),在循環(huán)后達(dá)到最大色數(shù).但不滿足平衡函數(shù)balance()時,則判定此圖不具有點魔幻全染色．

③ 輸出符合的平衡矩陣．

2.2 函數(shù)流程

預(yù)處理過程流程圖如圖4所示．

圖4 預(yù)處理過程Fig.4 Pretreatment process

VMTC算法總流程如下．

Input:圖G(p,q)的鄰接矩陣

Output:滿足VMTC的圖的鄰接矩陣

Begin

1) 先預(yù)處理,讀取處理后的鄰接矩陣AdjaMatrix

2) getp,q,degree,maximumdegree

3) calculate sum

4) for(i=min;i

5) while(點色數(shù)不連續(xù))

6) if(色數(shù)值差大于1 || 所有點色和不同)

7) Adjustment2(AdjaMatrix)

8) else

9) Output(BalanceMatrix)

10) end if

11) end while

12) end for

13) 輸出最終滿足點魔幻全染色的鄰接矩陣AdjaMatrix

14) end

2.3 算法結(jié)果

結(jié)果統(tǒng)計條形圖如圖5至圖8所示,展示了6個點到9個點不同邊數(shù)的圖總數(shù)中點魔幻全染色圖數(shù)的情況,其中藍(lán)色表示各個點相對應(yīng)邊數(shù)的非同構(gòu)圖的總數(shù)量,灰黃色表示相應(yīng)具有點魔幻全染色圖的數(shù)量．

圖5 六個點統(tǒng)計圖Fig.5 Six vertex statistical graph

圖6 七個點統(tǒng)計圖Fig.6 Seven vertex statistical graph

圖7 八個點統(tǒng)計圖Fig.7 Eight vertex statistical graph

圖8 九個點統(tǒng)計圖Fig.8 Nine vertex statistical graph

圖9給出了部分圖的點魔幻全染色示例．

圖9 點魔幻全染色示例Fig.9 VMTC example

3 定理及證明

定理1對于路圖Pn(n≥3),有

χVMTC(Pn)=n+1(n≥3).

(1)

證明設(shè)路圖的點集V(Pn)={v1,v2,v3,…,vn},對點進(jìn)行染色:

f(v1)=n+1;

f(vn)=n;

f(vi)=(n-i)+1 (2≤i

對邊進(jìn)行染色:f(v1v2)=1;

f(vn-1vn)=2;

f(vivi+1)=[(i+1)+[1+

(-1)i]/2]/2 (2≤i≤n-2).

對v1求色和Sum(v1)=n+1+1=n+2,對vn求色和Sum(vn)=n+2,對路圖中i=2,3,…,n-1的任意一個頂點求色和Sum(vi)=(n-i)+1+[i+[1+(-1)i-1]/2+i+1+[1+[1+(-1)i]/2]/2]/2．

當(dāng)i≡0(mod 2)時,Sum(vi)=(n-i)+1+(i+i+1+1)/2=n+2．

當(dāng)i≡1(mod 2)時,Sum(vi)=(n-i)+1+(i+1+i+1+0)/2=n+2．

即

Sum(vi)=n+2.

(2)

因此,Sum(v1)=Sum(vi)=Sum(vn)=n+2,路圖中所有頂點的色和相同,滿足點魔幻全染色,有χVMTC(Pn)=n+1 (n≥3),證畢．

定理2對于星圖Sn(n≤3),當(dāng)n≤3時有χVMTC(Sn)=n(n+1)/2;當(dāng)n≥4時不存在χVMTC(Sn)．

證明設(shè)星圖的點集V(Sn)={v0,v1,v2,v3,…,vn},對點進(jìn)行染色:

f(v0)=1;

f(v1)=n(n+1)/2;

f(vi)=f(v1)=(i-1)=n(n+1)/2-i+1.

對邊進(jìn)行染色:

f(v0vi)=i(i=1,2,3).

對v0求色和Sum(v0)=1+n+n(n-1)/2=1+(n2+n)/2,對v1求色和Sum(v1)=1+n(n+1)/2=1+(n2+n)/2,對v2求色和Sum(v2)=2+n(n+1)/2-2+1=1+(n2+n)/2,對v3求色和Sum(v3)=3+n(n+1)/2-3+1=1+(n2+n)/2.因此,Sum(v0)=Sum(v1)=Sum(v2)=Sum(v3)=1+(n2+n)/2,星圖中所有頂點的色和相同,滿足點魔幻全染色,有χVMTC(Sn)=n(n+1)/2 (n≤3).當(dāng)n≥4時,無論如何對點和邊進(jìn)行染色,都會出現(xiàn)色數(shù)不連續(xù)或所有點色和不相同的情況,無法滿足點魔幻全染色的定義,因此找不到滿足點魔幻全染色的星圖,χVMTC(Sn)不存在,證畢.

定理3對于扇圖Fn(n≥3),有

(3)

證明設(shè)扇圖的點集V(Fn)={v0,v1,v2,v3,…,vn},對扇圖分奇偶性進(jìn)行討論.

情況1當(dāng)n≡0(mod 2)時,

對點進(jìn)行染色:f(u0)=n+1;

f(u1)=n;

f(ui)=n-(i-1) (2≤i≤n-1);

f(un)=n/2+1.

對邊進(jìn)行染色:f(u0ui)=1 (i=1,2,3,…,n);

f(u1u2)=n;

f(u2u3)=1.

對u0求色和Sum(u0)=n+1+n=2n+1,對u1求色和Sum(u1)=n+1+n=2n+1,對un求色和Sum(un)=n/2+1+1+n+(i-1)/2,又因為i=n-1,所以Sum(un)=n/2+1+1+n+(n-2)/2=2n+1.對扇圖中i=2,3,…,n-1的任意一個頂點求色和Sum(ui)．

當(dāng)i≡1(mod 2)時,Sum(ui)=1+n-(i-1)+n+(i-1)/2+1+(i-1-2)/2=2n+1;

當(dāng)i≡0(mod 2)時,Sum(ui)=1+n-(i-1)+1+(i-2)/2+n+(i-1-1)/2=2n+1.

即

Sum(ui)=2n+1.

(4)

因此,Sum(u0)=Sum(u1)=Sum(un)=Sum(ui)=2n+1,扇圖中所有頂點的色和相同,滿足點魔幻全染色,有χVMTC(Fn)=(3n-2)/2,證畢．

情況2當(dāng)n≡1(mod 2)時,

對點進(jìn)行染色:f(u0)=n+1;

f(u1)=n;

f(ui)=n-(i-1) (2≤i≤n-1);

f(un)=5+[(n-1)/2-1]×3.

對邊進(jìn)行染色:f(u0ui)=1 (i=1,2,3,…,n);

f(u1u2)=n;

f(u2u3)=1;

對u0求色和Sum(u0)=n+1+n=2n+1,對u1求色和Sum(u1)=n+1+n=2n+1,對un求色和Sum(un)=1+5+3×[(n-1)/2-1]+1+(i-2)/2,因為i=n-1,所以Sum(un)=2n+1.同理,對ui求色和,按照奇偶性進(jìn)行討論,可得Sum(ui)=2n+1．

因此,Sum(u0)=Sum(u1)=Sum(un)=Sum(ui)=2n+1,扇圖中所有頂點的色和相同,滿足點魔幻全染色,有χVMTC(Fn)=(3n+1)/2,證畢.

定理4對于友誼圖T(2,n)=2n(n≥2),有

χVMTC(T(2,n))=2n(n≥2).

(5)

證明設(shè)友誼圖的點集為V=V(T(2,n))={v0,v1,v2,v3,…,v2n},對點進(jìn)行染色:

f(v0)=2;

f(v1)=2n;

f(vi)=2n-(i-1)/2 (2≤i≤2n).

對邊進(jìn)行染色:f(v0vi)=1 (i=1,2,3,…,2n);

f(vivi+1)=(i+1)/2 (i=1,3,5,…,2n-1).

對v0求色和Sum(v0)=2+2n,對友誼圖中i=2,3,…,2n的任意一個頂點求色和Sum(vi)=1+(i+1)/2+2n-(i-1)/2．

當(dāng)i≡1(mod 2)時,Sum(vi)=2n+1+(i+1)/2-(i-1)/2=2n+2;

當(dāng)i≡0(mod 2)時,Sum(vi)=2n+2.

即

Sum(vi)=2n+2.

(6)

因此,Sum(v0)=Sum(vi)=2n+2,友誼圖中所有頂點的色和相同,滿足點魔幻全染色,有χVMTC(T(2,n))=2n,證畢．

如圖10所示,為n=4,5,6時,滿足VMTC的友誼圖部分染色結(jié)果．

圖10 友誼圖示例Fig.10 Friendship graoh example

定理5對于聯(lián)圖Cm↑Sn(m≥4,n≥2且m-n=2),有

χVMTC(Cm↑Sn)=m(m≥4,n≥2且m-n=2).

(7)

證明設(shè)聯(lián)圖點集V=V(Cm)∪V(Sn)={u1,u2,…,um,w0,w1,…,wn},其中u1=w0,對點進(jìn)行染色:

f(v1/w0)=1;

f(u2)=2;

f(u3)=1 (m≥5);

f(um)=m-1;

f(um-1)=3 (m≥5);

f(um-2)=1 (m≥7);

f(ui)=m-i(4≤i

f(um-3)=[(m-2)+[1+(-1)m-3]/2]/2(m≥9);

f(wi)=m(1≤i≤n).

對邊進(jìn)行染色:f(u1u2)=1;

f(u1um)=1;

f(w0wi)=1 (i=1,2,…,n);

f(u2u3)=n;

f(u3u4)=2;

f(uiui+1)=[(i+1)+[1+(-1)i]/2]/2

(m-5≤i≤m-4且m≥8);

f(um-2um-1)=n-1 (m≥6);

f(um-3um-2)=3 (m≥7);

f(um-1um)=1.

對u1求色和Sum(u1)=3+n,對u2求色和Sum(u2)=1+2+n=n+3,對w3求色和Sum(w3)=1+m,因為m-n=2所以Sum(w3)=n+3,對um求色和Sum(um)=1+1+m-1=n+3,對ui求色和Sum(ui)=m-i+[(2i+1)+[1+(-1)i]/2+[1+(-1)i-1]/2]/2．

當(dāng)i≡0(mod 2)時,Sum(ui)=m-i+(2i+1+1)/2=m-i+i+1=m+1=n+3;

當(dāng)i≡1(mod 2)時,Sum(ui)=m+1=n+3.

即

Sum(ui)=n+3.

(8)

因此,Sum(u1)=Sum(u2)=Sum(w3)=Sum(um)=Sum(ui)=n+3,聯(lián)圖中所有頂點的色和相同,滿足點魔幻全染色,有χVMTC(Cm↑Sn)=m,證畢．

如圖11所示為m=6,n=4;m=8,n=6;m=9,n=7時,滿足VMTC的聯(lián)圖部分染色結(jié)果．

圖11 滿足VMTC聯(lián)圖示例Fig.11 Linkage graph satisfies VMTC example

定理6對于風(fēng)箏圖(n,t)-K(n≥4,t≥3且n-t=1),有

χVMTC(n,t)-K=n(n≥4,t≥3且n-t=1).

(9)

證明設(shè)(n,t)-K點集為V=V(Cn)∪V(Pt)={u1,u2,…,un,v1,v2,…,vt},其中u1=v1,對點進(jìn)行染色:

f(u1/v1)=t;

f(v2)=t;

f(vt)=n;

f(vi)=(t-i)+2 (2≤i≤t-2);

f(vt-1)=[(n+1)+[1+(-1)n]/2]/2;

f(u2)=3;

f(un)=n;

f(ui)=i+[1+(-1)i]/2 (2≤i≤n-1).

對邊進(jìn)行染色:f(u1u2)=f(u1un)=f(un-1un)=1;

f(vt-1vt)=2;

f(vivi+1)=[(i+1)+[1+(-1)i]/2]/2

(1≤i≤t-2).

當(dāng)n≡0(mod 2)時,f(vivi+1)=[(i+1)+[1+(-1)i]/2]/2 (1≤i≤t-2);

當(dāng)n≡0(mod 2)時,

f(uiui+1)=

當(dāng)n≡1(mod 2)時,

f(uiui+1)=

對u1求色和Sum(u1)=1+1+1+t=3+t,對un求色和Sum(un)=n+1+1=t+3,對vt求色和Sum(vt)=n+2=t+3．

對ui求色和Sum(ui),分四種情形進(jìn)行討論．

情形1當(dāng)n≡0(mod 2)且i≡1(mod 2)時,Sum(ui)=i+[1+(-1)i]/2+1+n-(i-1)=n+2,又因為n=t+1,所以Sum(ui)=t+3．

情形2當(dāng)n≡0(mod 2)且i≡0(mod 2)時,Sum(ui)=i+[1+(-1)i]/2+n-i+1=n+1+1=t+3.

情形3當(dāng)n≡1(mod 2)且i≡0(mod 2)時,Sum(ui)=i+[1+(-1)i]/2+n-i+1=n+1+1=t+3．

情形4當(dāng)n≡1(mod 2)且i≡1(mod 2)時,

Sum(ui)=i+[1+(-1)i]/2+1+n-i+1=
n+2=t+3．

即

Sum(ui)=t+3.

(10)

對un-1求色和Sum(un-1),對其分奇偶性討論．

當(dāng)n≡1(mod 2)時,Sum(un-1)=1+1+i+[1+(-1)i]/2=1+1+n-1+(1+1)/2=n+2=t+3．

當(dāng)n≡0(mod 2)時,Sum(un-1)=1+i+[1+(-1)i]/2+n-i=n+1+[1+(-1)i]/2=n+2=t+3．

即

Sum(un-1)=t+3.

(11)

對vi求色和Sum(vi),對其分奇偶性討論．

當(dāng)i≡0(mod 2)時,Sum(vi)=(t-i)+2+[(i+1)+[1+(-1)i]/2]/2+[i+[1+(-1)i-1]/2]/2=t-i+2+(2i+1+1-1)i]/2]/2+[i+[1+(-1)i-1]/2]/2=t-i+2+(2i+1+1+0)/2=t-i+2+t+1=t+3．

當(dāng)i≡1(mod 2)時,Sum(vi)=t+3．

即

Sum(vi)=t+3.

(12)

因此,Sum(u1)=Sum(un)=Sum(vt)=Sum(ui)=Sum(un-1)=Sum(vi)=t+3,風(fēng)箏圖中所有頂點的色和相同,滿足點魔幻全染色,有χVMTC(n,t)-K=n,證畢．

如圖12所示,為n=4,t=3;n=5,t=4;n=7,t=6時,滿足VMTC的風(fēng)箏圖部分染色結(jié)果．

圖12 滿足VMTC的風(fēng)箏圖Fig.12 Kite graph satisfies VMTC

4 結(jié)語

本文在已有的點魔幻標(biāo)號和點可區(qū)別染色研究基礎(chǔ)之上,提出了圖的點魔幻全染色新概念,針對該染色設(shè)計了一種新的VMTC算法,該算法對路、星、扇等特殊圖以及隨機圖的染色進(jìn)行研究,給出了6個定理及證明.從算法效率看,VMTC算法可快速完成一些點數(shù)較小的圖集染色,但當(dāng)頂點數(shù)較大時仍然會花費較多的時間.從算法結(jié)果看,目前只是對特殊圖和一小部分聯(lián)圖進(jìn)行了結(jié)果分析,關(guān)于其他隨機圖的點魔幻全染色還需要進(jìn)一步研究,希望各位讀者在以后能給予改進(jìn)．