緊優(yōu)無向雙環(huán)網(wǎng)絡(luò)強彩虹連通數(shù)的下界估計*

劉杰，陳寶興，鐘瑋

1. 閩南師范大學(xué)計算機學(xué)院，福建 漳州 363000

2. 三明醫(yī)學(xué)科技職業(yè)學(xué)院，福建 三明 365000

3. 福建省高等學(xué)校數(shù)據(jù)與智能應(yīng)用重點實驗室，福建 漳州 363000

設(shè)G是非平凡連通圖，可定義圖為G=(V，E)，其中頂點集和邊集分別用V(G)，E(G)表示。圖的連通性有廣泛的實際應(yīng)用，比如通信網(wǎng)絡(luò)的結(jié)構(gòu)可以用圖來表示，其中頂點代表不同的處理機或用戶，邊集代表了通信線路，構(gòu)造出可靠最優(yōu)的通信網(wǎng)絡(luò)具有很強的實用價值，這些問題可抽象為圖的問題來研究。2008 年Chartrand 等［1］首次提出了圖的彩虹連通性的概念，作為此概念的一種加強，他們在此論文中也介紹了強彩虹連通的概念。關(guān)于圖的（強）彩虹連通方面的一些定義，請讀者參考文獻［2］。

雙環(huán)網(wǎng)絡(luò)是計算機互聯(lián)網(wǎng)絡(luò)、大規(guī)模并行處理系統(tǒng)和通信系統(tǒng)的一類重要拓撲結(jié)構(gòu)，雙環(huán)網(wǎng)絡(luò)最優(yōu)直徑策略研究以及雙環(huán)網(wǎng)絡(luò)最優(yōu)構(gòu)造法等方面受到許多學(xué)者的重視［2-6］，并得出不少結(jié)論。由于圖的彩虹連通數(shù)在網(wǎng)絡(luò)安全與密碼管理中有重要的應(yīng)用，而決定圖的彩虹連通數(shù)問題是NP困難的，因此彩虹連通圖的著色方法近幾年來已成為圖論的熱門研究問題［1，7-9］，文獻［10］得出一類邊染色臨界圖的獨立數(shù)。文獻［11］探究了線性多邊形鏈彩虹著色問題。文獻［12］給出了某類含圈圖的修正的彩虹頂點連通數(shù)。文獻［13］研究了三類特殊圖的（強）彩虹連通數(shù)，并得到了它的精確值。文獻[14]與文獻[15]分別給出一類有向與無向環(huán)型網(wǎng)絡(luò)彩虹連通一種著色方法，并確定了其彩虹連通數(shù)的一個上界。

眾所周知，網(wǎng)絡(luò)的強彩虹連通數(shù)必大于或等于該網(wǎng)絡(luò)的直徑。容易驗證圖1 所示的無向雙環(huán)網(wǎng)絡(luò)G(8；±1，± 3)，其強彩虹連通數(shù)等于該網(wǎng)絡(luò)的直徑2。本文對無向雙環(huán)網(wǎng)絡(luò)最短路徑唯一表示問題進行刻畫，給出了緊優(yōu)無向雙環(huán)網(wǎng)絡(luò)具有最短路徑表示的一個充要條件，最后證明了一類具有唯一最短路徑表示的緊優(yōu)無向雙環(huán)網(wǎng)絡(luò)，其強彩虹連通數(shù)必大于或等于該網(wǎng)絡(luò)的直徑加1。

1 定義及引理

設(shè)1 ≤h＜n，h≠n/2，無向雙環(huán)網(wǎng)絡(luò)G(n；±1，±h)可定義為無向圖（V（G），E（G）），其中頂點集為V(G) ={0，1，2，…，n- 1}， 邊 集 是E(G) ={j→j+ 1(modn)，j→j- 1(modn)，j→j+h(modn)，j→j-h(modn) |j= 0，1，2，…，n- 1｝. 圖1G(8；±1，± 3)表示為有8個頂點的無向雙環(huán)網(wǎng)絡(luò)。

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

對于雙環(huán)網(wǎng)絡(luò)G(n；±1，±h)，定義點j到點(j+ 1)(modn)的邊為［+1］，點j到點(j- 1)(modn)的邊為［-1］。點j到點(j+h)(modn) 的邊為［+h］，點j到點(j-h)(modn) 的邊為［-h］。若一條從點v1到點v2的路徑，它包含x1個［+1］與x2個［-1］邊，y1個［+h］與y2個［-h］邊，則有l(wèi)≡(j+x1-x2+y1h-y2h)(modn)，并且模等式成立和邊的順序無關(guān)，從而路徑可表示為：x1[+1]+x2[-1]+y1[+h]+y2[-h].

設(shè)v1，v2是G(n；±1，±h)中的兩個頂點，x1[+1]+x2[-1]+y1[+h]+y2[-h]為點v1到點v2的一條最短路徑，那么x1、x2中至少有一個是0，y1、y2中至少有一個是0. 點v1到點v2最短路徑的邊僅含［+1］和［+h］，或僅含［-1］和［+h］，或僅含［+1］和［-h］或僅含［-1］和［-h］. 可表示為：x[+1]+y[+h]，這里x，y∈Z.

設(shè)x1[+1]+y1[+h]，x2[+1]+y2[+h]是從點v1到點v2的任意兩條最短路徑，且可推出(x1，y1)=(x2，y2)，則稱從點v1到點v2的最短路徑表示唯一。

若一個無向雙環(huán)網(wǎng)絡(luò)的任意兩個結(jié)點間均有唯一的最短路徑表示，則稱此網(wǎng)絡(luò)具有唯一最短路徑表示。

例1 無向雙環(huán)網(wǎng)絡(luò)G(8；±1，± 3)，從0 到2 的最短路徑可表示為：2[+1]+ 0[+3]，(-1)[+1]+ 1[+3]，或0[+1]+(-2)[+3]. 此網(wǎng)絡(luò)不具有唯一最短路徑表示。

文獻［1］給出了由G(n；±t1，±t2)所確定同余方程最小非負解與交叉解的定義，并給出了G(n；±t1，±t2)直徑公式，可參見定理1。

定義1稱同余式

為無向雙環(huán)網(wǎng)絡(luò)G(n；±1，±h)所對應(yīng)的同余方程。

定義2設(shè)a1，a2∈Z，若有同余式a1+a2h≡0(modn)，則稱格點(a1，a2)為零格點。對于零格點

推論1給定G(n；±1，±h)，其中n，h是正整數(shù)，1 ≤h＜n，h≠n/2，同余方程（1）的最小非負解與交叉解分別為(u，v)與(-a，b).設(shè)d為網(wǎng)絡(luò)G(n；±1，±h)的直徑，則u+v≤2d+ 1，a+b≤2d+ 1.

2 主要結(jié)果

引理1給定G(n；±1，±h)，其中n，h是正整數(shù)，1 ≤h＜n，h≠n/2，同余方程（1）的最小非負解與交叉解分別為(u，v)與(-a，b).設(shè)G(n；±1，±h)具有唯一最短路徑表示，則u+v與a+b均為奇數(shù)。

證明 設(shè)d為網(wǎng)絡(luò)G(n；±1，±h)的直徑。不妨設(shè)u≥v（當(dāng)u＜v時類似可證）。現(xiàn)證明u+v為奇數(shù)，類似可證a+b為奇數(shù)。用反證法，若u+v為偶數(shù)，由定理1的推論，可知u+v≤2d.

令t=(u+v)/2. 因為u+v為偶數(shù)，所以u，v同時為偶數(shù)，或同時為奇數(shù)。不妨設(shè)u，v都是偶數(shù)。易證網(wǎng)絡(luò)G(n；±1，±h)中從0 到(u/2) +(v/2)h的距離為t. 注意到(u/2)[+1] +(v/2)[+h]與-(u/2)[+1]-(v/2)[+h]均是從0到(u/2) +(v/2)h的最短路徑。這與G(n；±1，±h)具有唯一最短路徑表示矛盾！ 證畢

引理2給定G(n；±1，±h)，其中n，h是正整數(shù)，1 ≤h＜n，h≠n/2，同余方程（1）的最小非負解與交叉解分別為(u，v)與(-a，b).設(shè)d為網(wǎng)絡(luò)G(n；±1，±h)的直徑，G(n；±1，±h)具有唯一最短路徑表示，則

（i）當(dāng)u≥v時，有v=a，且u+b= 2d+ 2；

（ii）當(dāng)u＜v時，有u=b，且a+v= 2d+ 2.

先證圖G(n；±1，±h)具有唯一最短路徑表示時，(u+a)(v+b) ≡1(mod 2) 并且r3=r4.

以下先證明u≥v的情形，當(dāng)u＜v時，同理可證。

用反證法，若(u+a)(v+b) ≡1(mod 2)并且r3=r4不成立，由定理1可知d= max{r1，r2，min{r3，r4}}.因此min{r3，r4}≤d.

情形1：當(dāng)r3≤r4時，可得r3≤d. 因為u+v與a+b均為奇數(shù)，所以u-a+v+b是偶數(shù)。從而u-a，v+b同時為偶數(shù)，或同時為奇數(shù)。不妨設(shè)u-a，v+b都是奇數(shù)。易證網(wǎng)絡(luò)G(n；±1，±h)中從0 到(u-a+ 1)/2 +(v+b- 1)/2*h的 距 離 為r3≤d. 注 意 到(u-a+ 1)/2[+1] +(v+b- 1)/2*[+h] 與-(u-a-1)/2[+1]-(v+b+ 1)/2*[+h]均是從0 到(u-a+ 1)/2 + (v+b- 1)/2*h的最短路徑。這與G(n；±1，±h)具有唯一最短路徑表示矛盾！

情形2：當(dāng)r4＜r3時，類似地，易證得與假設(shè)矛盾。

當(dāng)(u+a)(v+b) ≡1(mod 2)并且r3=r4時，則G(n；±1，±h)的直徑d=r3- 1，且u+v+a+b為偶數(shù)。

當(dāng)u≥v時，因為

證明 注意到當(dāng)網(wǎng)絡(luò)G(n；±1，±h)是緊優(yōu)的，且其直徑為d時，有2d2- 2d+ 2 ≤n≤2d2+ 2d+ 1。

以下就u≥v情形給予證明。當(dāng)u≥v時，可證得a≤b（見文獻［3］的引理5）。

用反證法，若u+v≤d，因為

n=ub+va=ub+v2=u(2d+ 2 -u) +(u+v-u)2≤u(2d+ 2 -u) +(d-u)2=d2+ 2u≤d2+ 2d，注意到當(dāng)d≥4時，n≤d2+ 2d<2d2- 2d+ 2，這與n≥2d2- 2d+ 2矛盾！

若a+b≤d，因為

n=ub+va=ub+a2=b(2d+ 2 -b) +(a+b-b)2≤b(2d+ 2 -b) +(d-b)2=d2+ 2b≤d2+ 2d，注意到當(dāng)d≥4時，n≤d2+ 2d＜2d2- 2d+ 2，這與n≥2d2- 2d+ 2矛盾！

當(dāng)u＜v時，類似可證結(jié)論u+v＞d且a+b＞d成立。

證明 必要性可由引理1和引理2得到?，F(xiàn)證充分性，若G(n；±1，±h)不具有唯一最短路徑表示，則存在一個結(jié)點i，使得從0到i的最短路徑表示不唯一。不妨設(shè)u≥v（當(dāng)u＜v時類似可證）。注意到d(0，i) ≤d.

設(shè)x1[+1]+y1[+h]，x2[+1]+y2[+h]是從0 到i的兩個最短路徑表示，這里(x1，y1)≠(x2，y2). 注意到(x1-x2，y1-y2)是零格點。

若x1-x2，y1-y2同號（同為正或同為負），不妨設(shè)x1-x2，y1-y2同為正。由引理3，可知2u+ 2v＞2d. 零格點(u-a，b+v)，(2u，2v)均在直線x+y= 2d的右側(cè)，而且零格點(u+a，v-b)在第四象限中。與零格點C(u-a，b+v)相鄰的4 個格點：B(u，v)，D(-a，b)，(u- 2a，2b+v)，(2u-a，b+ 2v)均是奇零格點（見圖2）。

圖2 零格點A(0，0)，B(u，v)，C(u - a，b + v)，D(-a，b)位置示意圖Fig. 2 A location diagram of zero lattice points A(0,0),B(u,v),C(u - a,b + v),D(-a,b)

因為

因此(u- 2a，2b+v)，(2u-a，b+ 2v)均在直線x+y= 2d的右側(cè)。因此在第一象限中，由x軸，y軸，及直線x+y= 2d圍成的區(qū)域Ω 中，至多只有一個零格點(u，v)，(u，v)是一個奇零格點。因為x1-x2+y1-y2=2d(0，i) ≤2d，故偶零格點(x1-x2，y1-y2)在Ω中，這與區(qū)域Ω中不含偶零格點矛盾！

若x1-x2，y1-y2異號，不妨設(shè)x1-x2≤0，y1-y2≥0 . 由引理3，可知2a+ 2b＞2d. 因此零格點(-u-a，b-v)，(-2a，2b)均 在 直 線y=x+ 2d的 左 側(cè)。與 零 格 點C(-u-a，b-v) 相 鄰 的4 個 格 點：D(-a，b)，(-u，-v)，(-u- 2a，2b-v)，(-2u-a，b- 2v)均是奇零格點。且因為因此(-u- 2a，2b-v)，(-2u-a，b- 2v)均在直線y=x+ 2d的左側(cè)。另外(-u，-v)在第三象限中。在第二象限中，由x軸，y軸，及直線y=x+ 2d圍成的區(qū)域Σ 中，至多只有一個零格點(-a，b)，(-a，b)是一個奇零格點。因為-(x1-x2)+y1-y2= 2d(0，i) ≤2d，故偶零格點(x1-x2，y1-y2)在Σ 中，這與區(qū)域Σ 中不含偶零格點矛盾！ 證畢

引理5設(shè)t是一個正整數(shù)且2 ≤t＜n. 對于無向環(huán)形網(wǎng)絡(luò)G(n；±1)，若t?n，則使得G(n；±1)中長度不超過t的任一條路徑都是彩虹路至少需要用t+ 1種顏色對G(n；±1)邊著色。

證明 因為t?n，可設(shè)n=pt+q，這里0 ＜q＜t. 若只用t種顏色對G(n；±1)邊著色，從0 到t的路徑是彩虹路，其路徑上的t條邊均應(yīng)著不同的顏色，不妨設(shè)分別著色為1，2，…，t. 從1到t+ 1的路徑也是彩虹路，因此t到t+ 1 的邊應(yīng)著色為1。從2 到t+ 2 的路徑也是彩虹路，因此t+ 1 到t+ 2 的邊應(yīng)著色為2。因此從t到2t的路徑上邊的著色與從0到t的路徑上的邊著色相同，分別著色為1，2，…，t. 類似地，從2t到3t的路徑上邊的著色，……從(p- 1)t到pt的路徑上邊的著色，也應(yīng)分別著色為1，2，…，t. 從pt到n的路徑上邊的著色，也應(yīng)分別著色為1，2，…，q. 這導(dǎo)致了從pt到1 的路徑上邊的著色為1，2，…，q，1。從pt到1的路徑不是彩虹路，其長度q+ 1 ≤t. 因此若僅使用t種顏色對G(n；±1)邊著色，無法保證任一條長度不超過t的路徑均是彩虹路。 證畢

推論2設(shè)t是一個正整數(shù)且2 ≤t＜n. 對于無向環(huán)形網(wǎng)絡(luò)G(n；±h)，1 ≤h＜n，h≠n/2，若t?n且t＜ngcd(n，h)，這里gcd(n，h)表示n，h的最大公因數(shù)，則使得G(n；±h)中長度不超過t的任何一條路徑都是彩虹路至少需要用t+ 1種顏色對G(n；±h)邊著色。

證明 記m=ngcd(n，h). 因t?n，故t?m. 因為網(wǎng)絡(luò)G(n；±h)有g(shù)cd(n，h)個圈，每個圈的長度為m.對于網(wǎng)絡(luò)G(n；±h)中的某個圈，與引理5的證明類似，至少需用t+ 1種顏色對這個圈的邊進行著色。證畢

定理2給定G(n；±1，±h)，其中n，h是正整數(shù)，1 ≤h＜n，h≠n/2. 設(shè)d為網(wǎng)絡(luò)G(n；±1，±h)的直徑，且d?n，d≥4，同余方程（1）的最小非負解與交叉解分別為(u，v)與(-a，b).若網(wǎng)絡(luò)G(n；±1，±h)是緊優(yōu)的，具有唯一最短路徑表示，且u+v= 2d+ 1或a+b= 2d+ 1，則使得G(n；±1，±h)中任給兩點間的最短路徑有一條是彩虹路至少需用d+ 1種顏色對G(n；±1，±h)邊著色。

證明 我們就當(dāng)u≥v時給予證明（當(dāng)u＜v時，類似可證）。因為u+v，a+b均為奇數(shù)，所以有u＞v，a＜b. 當(dāng)u+v= 2d+ 1，可知u≥d+ 1?，F(xiàn)證d(0，d) =d. 因為a=v≤d，所以d-a≥0。注意到格點(d-a，b)到4個零格點(0，0)，(u，v)，(u-a，b+v)，(-a，b)的距離分別為：d-a+b，d+ 2，d+ 1，d. 因為d-a+b＞d，(d-a) +bh≡d(modn)，所以d(0，d) =d. 因此從0到d的最短路徑為：d[+1]+ 0[+h]. 從而在G(n；±1，±h)中從0到d，1到d+ 1，…，n-d到0，…，n- 1到d- 1的最短路徑，與在G(n；±1)中的最短路徑相同，據(jù)引理5 可知，則使得G(n；±1，±h)中任給兩點間的最短路徑有一條是彩虹路至少需用d+ 1種顏色對G(n；±1，±h)邊著色。

當(dāng)a+b= 2d+ 1，可知b≥d+ 1. 記m=ngcd(n，h). 現(xiàn)證d＜m. 若d≥m，因為mh≡0(modn)，所以(-a，b-m)是同余方程（1）的交叉解，這與(-a，b)是同余方程（1）的最小交叉解矛盾。

現(xiàn)證d(0，dh) =d. 因為v=a≤d，所以d-v≥0. 注意到格點(0，d)到4 個零格點(0，0)，(u，v)，(u-a，b+v)，(-a，b)的距離分別為：d，u+d-v，d+ 2，d+ 1. 因為u+d-v＞d，所以d(0，dh) =d. 因此從0到dh的最短路徑為：0[+1]+d[+h]. 從而在G(n；±1，±h)中從0 到dh，1 到dh+ 1，…，n- 1 到dh- 1 的最短路徑，與在G(n；±h)中的最短路徑相同，據(jù)引理5 的推論2 可知，則使得G(n；±1，±h)中任給兩點間的最短路徑有一條是彩虹路至少需用d+ 1種顏色對G(n；±1，±h)邊著色。 證畢

例2

（i）對于無向雙環(huán)網(wǎng)絡(luò)G(2t2+ 2t+ 1；±1，±(2t+ 1))（這里t是正整數(shù)，t≥4），同余方程（1）的最小非負解與交叉解分別是(t+ 1，t)、(-t，t+ 1). 利用定理1，易求得網(wǎng)絡(luò)G(2t2+ 2t+ 1；±1，±(2t+ 1))的直徑為t，因此網(wǎng)絡(luò)G(2t2+ 2t+ 1；±1，±(2t+ 1))是緊優(yōu)的。因為u=t+ 1，v=t，a=t，b=t+ 1，所以有u≥v，v=a，u+b= 2t+ 2，且u+v與a+b均是奇數(shù)。因此依據(jù)引理4，G(2t2+ 2t+ 1；±1，±(2t+ 1))具有唯一最短路徑表示。注意到u+v= 2t+ 1，據(jù)定理2，G(2t2+ 2t+ 1；±1，±(2t+ 1))的強彩虹連通數(shù)至少是該網(wǎng)絡(luò)的直徑加1。

（ii）對于無向雙環(huán)網(wǎng)絡(luò)G(2t2+ 1；±1，±(2t2- 2t))（這里t是正整數(shù)，t≥4），同余方程（1）的最小非負解與交叉解分別是(t- 1，t)、(-t- 2，t- 1) . 利用定理1，易求得網(wǎng)絡(luò)G(2t2+ 1；±1，±(2t2- 2t))的直徑為t，因此網(wǎng)絡(luò)G(2t2+ 1；±1，±(2t2- 2t))是緊優(yōu)的。因為u=t- 1，v=t，a=t+ 2，b=t- 1，所以有u＜v，u=b，a+v= 2t+ 2，且u+v與a+b均是奇數(shù)。因此依據(jù)引理4，G(2t2+ 1；±1，±(2t2- 2t))具有唯一最短路徑表示。注意到a+b=t+ 2 +t- 1 = 2t+ 1，據(jù)定理2，G(2t2+ 1；±1，±(2t2- 2t))的強彩虹連通數(shù)至少是該網(wǎng)絡(luò)的直徑加1。