无向双环网络的强彩虹连通性

刘 杰，陈宝兴

(1.闽南师范大学计算机学院，福建 漳州 363000;2.三明医学科技职业学院,福建 三明 365000;3.数据科学与智能应用福建省高等学校重点实验室，福建 漳州 363000)

令G为一个非平凡的连通图，连接图G中的两个顶点u和v的最短路径的长度称为u和v之间的距离，记为d(u,v).图G中任意两个顶点之间距离的最大值称为图G的直径，记作D(G).在G上定义一个边染色C：E(G)→{1,2,…,k},k∈N，其中相邻的边可能染同种颜色，如果一条路P上的边分别染不同的颜色，则称P是一条彩虹路.如果图G任意两个不同顶点之间都有一条彩虹路相连，则称图G是彩虹连通的.使得图G彩虹连通所需要的最少颜色数称为G的彩虹连通数，记为rc(G).如果图G的任意两个不同顶点之间都有一条最短路径是彩虹路，则称图G是强彩虹连通的.使得图G强彩虹连通所需要的最少颜色数称为G的强彩虹连通数，记为src(G).

图的染色有广泛的实际应用，比如说学生选课系统、电路布局、排序问题、会议安排、电路安排、考试安排等，这些问题都与图的染色理论密切相关.双环网络是一种重要的计算机网络，它具有对称性,且易于扩展.与环状网络比较，它的直径比较小，且有较好的容错能力.双环网络在设计和构建大中型网络或者并行处理计算机系统中有着广泛的应用.双环网络的直径估计与计算[1-5]，构造最优双环网络，以及双环网络的寻径策略研究,曾经受到不少学者的重视[6-10].在过去的几年里，图的彩虹连通着色[11-13]作为图论中的一个新问题受到了广泛的关注，它也被应用到网络信息安全与密码学等领域.刘欣欣等[14]给出了有向双环网络彩虹连通的一个着色方案，从而得到了其彩虹连通数的一个上界.王燕等[15]研究了一类线性多边形链的彩虹连通着色.本文中将对无向双环网络任意两点之间的最短路径进行刻画:证明任意两点之间存在一条最短路径W[+s1]+R[+s2]，这里|W|

1 定义及引理

设1≤s1

图1 无向双环网络G(8;±1,±3)Fig.1 Undirected double loop network G(8; ±1, ±3)

对于双环网络G(n;±s1,±s2),从点i到点(i+s1) (modn)的边称为[+s1]边,点i到点(i-s1)(modn)的边称为[-s1]边.点i到点(i+s2)(modn) 的边称为[+s2]边,点i到点(i-s2)(modn) 的边称为[-s2]边.若一条从点i到点j的路径包含x1条[+s1]和x2条[-s1]边，y1条[+s2]边和y2条[-s2]边,则有j≡(i+x1s1-x2s1+y1s2-y2s2)(modn),且等式成立与路径中边的顺序无关，将此路径记为：x1[+s1]+x2[-s1]+y1[+s2]+y2[-s2].

设i、j是G(n;±s1,±s2)中的两个节点，x1[+s1]+x2[-s1]+y1[+s2]+y2[-s2]是一条从i到j的最短路径，则x1与x2至少有一个为0，y1与y2至少一个为0.从i到j的最短路径使用的边仅含[+s1]与[+s2]或仅含[-s1]与[+s2]，或仅含[+s1]与[-s2]或仅含[-s1]与[-s2].从i到j的最短路径可记为：x[+s1]+y[+s2]，这里x、y∈Z.

Chen等[4]给出了由G(n;±s1,±s2)所确定的同余方程最小非负解和最小交叉解的定义，并给出了G(n;±s1,±s2)的直径公式.

定义1[4]称格点(a1，a2)为同余式

xs1+ys2≡0(modn)

(1)

的一个非负解，如果a1s1+a2s2≡0(modn),a1，a2∈Z+，并且(a1，a2)≠(0,0).

称(u，v)为同余式(1)的最小非负解，若它满足以下条件：

(i) (u，v)为同余式(1)的非负解.

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

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

定义2[4]称格点(-a1，a2)为同余式(1)的交叉解，如果-a1s1+a2s2≡0(modn)，a1、a2∈Z+，(-a1，a2)≠(0，0)，并且(-a1,a2)、(0，0)、(u，v)三点不在同一直线上，其中(u，v)为同余式(1)的最小非负解.

称(-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]设(u,v)、(-a,b)分别是同余式(1)的最小非负解和最小交叉解.如果u≥v，则有a≤u、a≤b、v

特别地，容易证明：如果u=v，则有a

引理2[4]设(u,v),(-a,b)分别是同余式(1)的最小非负解和最小交叉解.如果uu，a>b，b

引理3当u=v时，对于0≤k≤n-1，G(n;±s1,±s2)中存在一条从0到k的最短路径W[+s1]+R[+s2]，满足|W|

证明对于0≤k≤n-1，若W[+s1]+R[+s2]是一条从0到k的最短路径，则必有|R|

用反证法，若|R|≥b，不妨设R≥b(R≤-b类似可证).由引理1可知，当u=v时，有a

若|W|≥u，不妨设W≥u(W≤-u类似可证).设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当u>v时，对于0≤k≤n-1，G(n;±s1,±s2)中存在一条从0到k的最短路径W[+s1]+R[+s2]，满足|W|

证明对于0≤k≤n-1，若W[+s1]+R[+s2]是一条从0到k的最短路径，则必有|W|

用反证法，若|W|≥u，不妨设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，不妨设R≥b(R≤-b类似可证).设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当u

证明对于0≤k≤n-1，若W[+s1]+R[+s2]是一条从0到k的最短路径，则必有|W|

用反证法，若|W|≥a，不妨设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对于0≤k≤n-1，在G(n;±s1,±s2)中存在一条从0到k的最短路径W[+s1]+R[+s2]满足|W|

无向环状网络G(n; ±s)是如下定义的无向图(V(G)，E(G))：节点集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)是连通的当且仅当gcd(n,s)=1.当gcd(n,s)=d>1时,无向环状网络是不连通的.此网络有d个连通分量，节点0，1，2，…，n-1分别属于这d个连通分量.

引理8的证明与文献[14]的引理1类似，这里略去.

例1对于无向环状网络G(33;±12),取t=5,则用6种颜色对G(33;±12)边着色,就可使得G(33;±12)中任一条长度不超过5的路径均是一条彩虹路.

2 主要结果

下面将给出无向双环网络强彩虹连通的一个着色方案，并给出了该网络强彩虹连通数的一个上界.

图2 环状网络G(33;±12)的彩虹着色方案Fig.2 The rainbow coloring scheme of loop network G(33;±12)

证明注意到无向双环网络的边有两种类型：一种是[+s1]边或[-s1]边，即G(n; ±s1)中的边，另一种是[+s2]边或[-s2]边，即G(n;±s2)中的边.

这样便完成了无向双环网络G(n; ±s1,±s2)中所有边的着色.

据引理6，对于0≤k≤n-1，在G(n;±s1,±s2)中存在一条从0到k的最短路径W[+s1]+R[+s2]满足|W|

在G(n;±s1)中有一条长为|W|的彩虹路：当W>0时，0→s1→2s1→…→Ws1.当W<0时，0→-s1→ -2s1→…→Ws1.

在G(n;±s2)中有一条长为|R|的彩虹路：当R>0时，Ws1→Ws1+s2→Ws1+2s2→…→Ws1+Rs2.当R<0时，Ws1→Ws1-s2→Ws1-2s2→…→Ws1+Rs2.

因在两个网状网络G(n;±s1)与G(n;±s2)中的着色不同，故可得到一条从0到k,长度为|W|+|R|的最短彩虹路.证毕.

证明仅就u≥v的情形给出证明，u

当u≥v，r3=r4且(u+a)(v+b)≡1(mod 2)时，可推出a=v.由引理1，可知a≤u.因此r3=(u+b)/2.据引理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求无向双环网络G(2t2+2t+1;±1,±(2t+1))(这里t是正整数,t>1)的强彩虹连通数的上界、直径.

(ii) 计算G(2t2+2t+1;±1,±(2t+1))的直径.

注意到src(G)≥D(G),我们得到的G(2t2+2t+1;±1,±(2t+1))的强彩虹连通数上界2t+2与该网络直径t较为接近.

3 结 论

图的彩虹着色问题是一个多项式复杂程度的非确定性(NP)问题.其困难在于使用最小颜色数k，并要求G的任意两点间均有一条彩虹路.直至目前，未见有文献给出无向双环网络的彩虹着色方案.本文中通过对无向双环网络任意两点之间的最短路径进行刻画，进而给出了该网络强彩虹连通的一个着色方案，最后得到了该网络强彩虹连通数的一个上界，这上界主要由G(n;±s1,±s2)所对应的同余方程的最小非负解和最小交叉解中的4个参数表示.下一步的任务是找出更好的着色方案，使得所用的颜色数更少.