無(wú)向雙環(huán)網(wǎng)絡(luò)的強(qiáng)彩虹連通性

劉 杰，陳寶興

(1.閩南師范大學(xué)計(jì)算機(jī)學(xué)院，福建 漳州 363000;2.三明醫(yī)學(xué)科技職業(yè)學(xué)院,福建 三明 365000;3.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000)

令G為一個(gè)非平凡的連通圖，連接圖G中的兩個(gè)頂點(diǎn)u和v的最短路徑的長(zhǎng)度稱為u和v之間的距離，記為d(u,v).圖G中任意兩個(gè)頂點(diǎn)之間距離的最大值稱為圖G的直徑，記作D(G).在G上定義一個(gè)邊染色C：E(G)→{1,2,…,k},k∈N，其中相鄰的邊可能染同種顏色，如果一條路P上的邊分別染不同的顏色，則稱P是一條彩虹路.如果圖G任意兩個(gè)不同頂點(diǎn)之間都有一條彩虹路相連，則稱圖G是彩虹連通的.使得圖G彩虹連通所需要的最少顏色數(shù)稱為G的彩虹連通數(shù)，記為rc(G).如果圖G的任意兩個(gè)不同頂點(diǎn)之間都有一條最短路徑是彩虹路，則稱圖G是強(qiáng)彩虹連通的.使得圖G強(qiáng)彩虹連通所需要的最少顏色數(shù)稱為G的強(qiáng)彩虹連通數(shù)，記為src(G).

圖的染色有廣泛的實(shí)際應(yīng)用，比如說(shuō)學(xué)生選課系統(tǒng)、電路布局、排序問(wèn)題、會(huì)議安排、電路安排、考試安排等，這些問(wèn)題都與圖的染色理論密切相關(guān).雙環(huán)網(wǎng)絡(luò)是一種重要的計(jì)算機(jī)網(wǎng)絡(luò)，它具有對(duì)稱性,且易于擴(kuò)展.與環(huán)狀網(wǎng)絡(luò)比較，它的直徑比較小，且有較好的容錯(cuò)能力.雙環(huán)網(wǎng)絡(luò)在設(shè)計(jì)和構(gòu)建大中型網(wǎng)絡(luò)或者并行處理計(jì)算機(jī)系統(tǒng)中有著廣泛的應(yīng)用.雙環(huán)網(wǎng)絡(luò)的直徑估計(jì)與計(jì)算[1-5]，構(gòu)造最優(yōu)雙環(huán)網(wǎng)絡(luò)，以及雙環(huán)網(wǎng)絡(luò)的尋徑策略研究,曾經(jīng)受到不少學(xué)者的重視[6-10].在過(guò)去的幾年里，圖的彩虹連通著色[11-13]作為圖論中的一個(gè)新問(wèn)題受到了廣泛的關(guān)注，它也被應(yīng)用到網(wǎng)絡(luò)信息安全與密碼學(xué)等領(lǐng)域.劉欣欣等[14]給出了有向雙環(huán)網(wǎng)絡(luò)彩虹連通的一個(gè)著色方案，從而得到了其彩虹連通數(shù)的一個(gè)上界.王燕等[15]研究了一類線性多邊形鏈的彩虹連通著色.本文中將對(duì)無(wú)向雙環(huán)網(wǎng)絡(luò)任意兩點(diǎn)之間的最短路徑進(jìn)行刻畫:證明任意兩點(diǎn)之間存在一條最短路徑W[+s1]+R[+s2]，這里|W|

1 定義及引理

設(shè)1≤s1

圖1 無(wú)向雙環(huán)網(wǎng)絡(luò)G(8;±1,±3)Fig.1 Undirected double loop network G(8; ±1, ±3)

對(duì)于雙環(huán)網(wǎng)絡(luò)G(n;±s1,±s2),從點(diǎn)i到點(diǎn)(i+s1) (modn)的邊稱為[+s1]邊,點(diǎn)i到點(diǎn)(i-s1)(modn)的邊稱為[-s1]邊.點(diǎn)i到點(diǎn)(i+s2)(modn) 的邊稱為[+s2]邊,點(diǎn)i到點(diǎn)(i-s2)(modn) 的邊稱為[-s2]邊.若一條從點(diǎn)i到點(diǎn)j的路徑包含x1條[+s1]和x2條[-s1]邊，y1條[+s2]邊和y2條[-s2]邊,則有j≡(i+x1s1-x2s1+y1s2-y2s2)(modn),且等式成立與路徑中邊的順序無(wú)關(guān)，將此路徑記為：x1[+s1]+x2[-s1]+y1[+s2]+y2[-s2].

設(shè)i、j是G(n;±s1,±s2)中的兩個(gè)節(jié)點(diǎn)，x1[+s1]+x2[-s1]+y1[+s2]+y2[-s2]是一條從i到j(luò)的最短路徑，則x1與x2至少有一個(gè)為0，y1與y2至少一個(gè)為0.從i到j(luò)的最短路徑使用的邊僅含[+s1]與[+s2]或僅含[-s1]與[+s2]，或僅含[+s1]與[-s2]或僅含[-s1]與[-s2].從i到j(luò)的最短路徑可記為：x[+s1]+y[+s2]，這里x、y∈Z.

Chen等[4]給出了由G(n;±s1,±s2)所確定的同余方程最小非負(fù)解和最小交叉解的定義，并給出了G(n;±s1,±s2)的直徑公式.

定義1[4]稱格點(diǎn)(a1，a2)為同余式

xs1+ys2≡0(modn)

(1)

的一個(gè)非負(fù)解，如果a1s1+a2s2≡0(modn),a1，a2∈Z+，并且(a1，a2)≠(0,0).

稱(u，v)為同余式(1)的最小非負(fù)解，若它滿足以下條件：

(i) (u，v)為同余式(1)的非負(fù)解.

(ii) 同余式(1)的任意非負(fù)解(a1,a2)，都有u+v≤a1+a2.

(iii) 如果存在同余式(1)的非負(fù)解(a1，a2)≠(u，v)并且a1+a2=u+v，則有u>a1.

定義2[4]稱格點(diǎn)(-a1，a2)為同余式(1)的交叉解，如果-a1s1+a2s2≡0(modn)，a1、a2∈Z+，(-a1，a2)≠(0，0)，并且(-a1,a2)、(0，0)、(u，v)三點(diǎn)不在同一直線上，其中(u，v)為同余式(1)的最小非負(fù)解.

稱(-a，b)為同余式(1)的最小交叉解，若它滿足以下條件：

(i) (-a，b)為同余式(1)的交叉解.

(ii) 同余式(1)的任意交叉解(-a1，a2)，都有a+b≤a1+a2.

(iii) 如果同余式(1)存在交叉解(-a1,a2)≠(-a，b)并且a+b=a1+a2，則有b>a2.

引理1[4]設(shè)(u,v)、(-a,b)分別是同余式(1)的最小非負(fù)解和最小交叉解.如果u≥v，則有a≤u、a≤b、v

特別地，容易證明：如果u=v，則有a

引理2[4]設(shè)(u,v),(-a,b)分別是同余式(1)的最小非負(fù)解和最小交叉解.如果uu，a>b，b

引理3當(dāng)u=v時(shí)，對(duì)于0≤k≤n-1，G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2]，滿足|W|

證明對(duì)于0≤k≤n-1，若W[+s1]+R[+s2]是一條從0到k的最短路徑，則必有|R|

用反證法，若|R|≥b，不妨設(shè)R≥b(R≤-b類似可證).由引理1可知，當(dāng)u=v時(shí)，有a

若|W|≥u，不妨設(shè)W≥u(W≤-u類似可證).設(shè)W=iu+j,這里i、j∈Z,且0≤j≤u-1.注意到(W-iu)[+s1]+(R-iu)[+s2]也是一條從0到k的路徑，且|W-iu|+|R-iu|=W-iu+|R-iu|≤W-iu+|R|+iu=W+|R|.因此(W-iu)[+s1]+(R-iu)[+s2]也是一條從0到k的最短路徑且|W-iu|

引理4當(dāng)u>v時(shí)，對(duì)于0≤k≤n-1，G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2]，滿足|W|

證明對(duì)于0≤k≤n-1，若W[+s1]+R[+s2]是一條從0到k的最短路徑，則必有|W|

用反證法，若|W|≥u，不妨設(shè)W≥u(W≤-u類似可證).注意到(W-u)[+s1]+(R-v)[+s2]也是一條從0到k的路徑，且|W-u|+|R-v|=W-u+|R-v|≤W-u+|R|+v<|W|+|R|，這與W[+s1]+R[+s2]是一條從0到k的最短路徑矛盾.

若|R|≥b，不妨設(shè)R≥b(R≤-b類似可證).設(shè)R=ib+j,這里i、j∈Z,且0≤j≤b-1.注意到(W+ia)[+s1]+(R-ib)[+s2]也是一條從0到k的路徑，且|W+ia|+|R-ib|=|W+ia|+R-ib≤|W|+ia+R-ib≤|W|+|R|，因此(W+ia)[+s1]+(R-ib)[+s2]也是一條從0到k的最短路徑且|W+ia|

引理5當(dāng)u

證明對(duì)于0≤k≤n-1，若W[+s1]+R[+s2]是一條從0到k的最短路徑，則必有|W|

用反證法，若|W|≥a，不妨設(shè)W≥a(W≤-a類似可證).注意到(W-a)[+s1]+(R+b)[+s2]也是一條從0到k的路徑，且|W-a|+|R+b|=W-a+|R+b|≤W-a+|R|+b<|W|+|R|，這與W[+s1]+R[+s2]是一條從0到k的最短路徑矛盾.

類似可證|R|

令t1=max{u,a},t2=max{v,b},從引理3～5，可得引理6.

引理6對(duì)于0≤k≤n-1，在G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2]滿足|W|

無(wú)向環(huán)狀網(wǎng)絡(luò)G(n; ±s)是如下定義的無(wú)向圖(V(G)，E(G))：節(jié)點(diǎn)集V(G)={0，1，2，…，n-1}，邊集E(G)={i→i-s(modn),i→i+s(modn)|i=0，1，2，…，n-1}.注意到G(n;±s)是連通的當(dāng)且僅當(dāng)gcd(n,s)=1.當(dāng)gcd(n,s)=d>1時(shí),無(wú)向環(huán)狀網(wǎng)絡(luò)是不連通的.此網(wǎng)絡(luò)有d個(gè)連通分量，節(jié)點(diǎn)0，1，2，…，n-1分別屬于這d個(gè)連通分量.

引理8的證明與文獻(xiàn)[14]的引理1類似，這里略去.

例1對(duì)于無(wú)向環(huán)狀網(wǎng)絡(luò)G(33;±12),取t=5,則用6種顏色對(duì)G(33;±12)邊著色,就可使得G(33;±12)中任一條長(zhǎng)度不超過(guò)5的路徑均是一條彩虹路.

2 主要結(jié)果

下面將給出無(wú)向雙環(huán)網(wǎng)絡(luò)強(qiáng)彩虹連通的一個(gè)著色方案，并給出了該網(wǎng)絡(luò)強(qiáng)彩虹連通數(shù)的一個(gè)上界.

圖2 環(huán)狀網(wǎng)絡(luò)G(33;±12)的彩虹著色方案Fig.2 The rainbow coloring scheme of loop network G(33;±12)

證明注意到無(wú)向雙環(huán)網(wǎng)絡(luò)的邊有兩種類型：一種是[+s1]邊或[-s1]邊，即G(n; ±s1)中的邊，另一種是[+s2]邊或[-s2]邊，即G(n;±s2)中的邊.

這樣便完成了無(wú)向雙環(huán)網(wǎng)絡(luò)G(n; ±s1,±s2)中所有邊的著色.

據(jù)引理6，對(duì)于0≤k≤n-1，在G(n;±s1,±s2)中存在一條從0到k的最短路徑W[+s1]+R[+s2]滿足|W|

在G(n;±s1)中有一條長(zhǎng)為|W|的彩虹路：當(dāng)W>0時(shí)，0→s1→2s1→…→Ws1.當(dāng)W<0時(shí)，0→-s1→ -2s1→…→Ws1.

在G(n;±s2)中有一條長(zhǎng)為|R|的彩虹路：當(dāng)R>0時(shí)，Ws1→Ws1+s2→Ws1+2s2→…→Ws1+Rs2.當(dāng)R<0時(shí)，Ws1→Ws1-s2→Ws1-2s2→…→Ws1+Rs2.

因在兩個(gè)網(wǎng)狀網(wǎng)絡(luò)G(n;±s1)與G(n;±s2)中的著色不同，故可得到一條從0到k,長(zhǎng)度為|W|+|R|的最短彩虹路.證畢.

證明僅就u≥v的情形給出證明，u

當(dāng)u≥v，r3=r4且(u+a)(v+b)≡1(mod 2)時(shí)，可推出a=v.由引理1，可知a≤u.因此r3=(u+b)/2.據(jù)引理7，可得D(G)=r3-1=(u+b)/2-1.由定理1，可知src(G)≤2(t1+t2)-6=2(u+b)-6=4[(u+b)/2-1]-2=4D(G)-2.證畢.

例2求無(wú)向雙環(huán)網(wǎng)絡(luò)G(2t2+2t+1;±1,±(2t+1))(這里t是正整數(shù),t>1)的強(qiáng)彩虹連通數(shù)的上界、直徑.

(ii) 計(jì)算G(2t2+2t+1;±1,±(2t+1))的直徑.

注意到src(G)≥D(G),我們得到的G(2t2+2t+1;±1,±(2t+1))的強(qiáng)彩虹連通數(shù)上界2t+2與該網(wǎng)絡(luò)直徑t較為接近.

3 結(jié) 論

圖的彩虹著色問(wèn)題是一個(gè)多項(xiàng)式復(fù)雜程度的非確定性(NP)問(wèn)題.其困難在于使用最小顏色數(shù)k，并要求G的任意兩點(diǎn)間均有一條彩虹路.直至目前，未見(jiàn)有文獻(xiàn)給出無(wú)向雙環(huán)網(wǎng)絡(luò)的彩虹著色方案.本文中通過(guò)對(duì)無(wú)向雙環(huán)網(wǎng)絡(luò)任意兩點(diǎn)之間的最短路徑進(jìn)行刻畫，進(jìn)而給出了該網(wǎng)絡(luò)強(qiáng)彩虹連通的一個(gè)著色方案，最后得到了該網(wǎng)絡(luò)強(qiáng)彩虹連通數(shù)的一個(gè)上界，這上界主要由G(n;±s1,±s2)所對(duì)應(yīng)的同余方程的最小非負(fù)解和最小交叉解中的4個(gè)參數(shù)表示.下一步的任務(wù)是找出更好的著色方案，使得所用的顏色數(shù)更少.