謝 歆，項詩景

(1.黃山學院 數(shù)學與統(tǒng)計學院，安徽 黃山 245041； 2.華僑大學 數(shù)學科學學院，福建 泉州 362021)

本文采用文獻[1]中有關圖論的術語和記號，用圖表示網(wǎng)絡.圖的直徑和連通度被廣泛應用到圖論中，可靠性和有效性是設計互連網(wǎng)絡的重要參數(shù).網(wǎng)絡中從點x到點y的距離是指從x到y(tǒng)最短路的邊數(shù)，圖G的直徑是任何兩頂點間距離的最大數(shù)，連通度k(G)是指使得連通圖G不連通所需去掉的最少頂點數(shù).

n維無向超環(huán)面網(wǎng)C(d1,d2,…,dn)，頂點集為({(x1,x2,…,xn)|0≤xi≤di-1，i=1,2,…,n}.頂點(x1,x2,…,xn)相鄰于2n個頂點(x1±1,x2,…,xn),(x1,x2±1,…,xn),… ,(x1,x2,…,xn±1)，這里±為模di(1≤i≤n)同余.n維無向超環(huán)面網(wǎng)C(d1,d2,…,dn)具有2n正則和點可遷的性質，連通度為2n，被廣泛應用到網(wǎng)絡理論中[2-4].

為了刻畫實時平行系統(tǒng)網(wǎng)絡傳輸延遲的可靠性，F(xiàn)landrin等[5]，Hsu等[6]分別定義了圖的m寬直徑.設圖G為m連通圖，頂點x到頂點y的寬度為m的距離dm(G;x,y)是指最小數(shù)d使得G中存在m條內點不交且長度不超過d的(x,y)路.圖G的m寬直徑dm(G)是指G中任何頂點x,y寬度為m的距離dm(G;x,y)的最大值.

在m連通圖中，Li等[7]定義了參數(shù)(l,m)控制數(shù)，在某種程度上(l,m)控制數(shù)比寬直徑更能精確地刻畫網(wǎng)絡的可靠性.對于m連通圖G和給定正整數(shù)l, 如果對于G的任一頂點x(不在S中)都存在m條內點不交且長度不超過l的(S,x)路，則稱頂點集G的非空真子集S為G的(l,m)控制集.用Sl,m(G)表示G的所有(l,m)控制集集合，定義參數(shù)γl,m(G)=min{|S||S∈Sl,m(G)}為G的(l,m)控制數(shù).

(l,m)控制數(shù)不僅推廣了通常意義下的圖的控制數(shù)，并且很好地度量了容錯網(wǎng)絡中的資源共享問題.一個重要而又實際問題是怎么選取(l,m)控制集S使得S中頂點數(shù)盡可能少.因此(l,m)控制數(shù)和圖的其他重要參數(shù)例如(l,m)獨立數(shù)[8]結合起來，能更精確地分析實時平行系統(tǒng)網(wǎng)絡的可靠性和有效性的容錯性.

由于確定圖的(1,1)控制數(shù)是NPC(NP-Completeness)問題[9]，因此確定圖的(l,m)控制數(shù)也是NPC問題.這樣對于特殊的正整數(shù)l和m，確定特定網(wǎng)絡的(l,m)控制數(shù)[10-16]顯得更有意義.

1 預備知識

→…

這里±為模dj同余，j=i1,i2,…,ir.

引理1[17]如果n≥2，di≥3(i=1,2,…,n)，則

引理2[17]如果n≥3，di≥3(i=1,2,…,n)，則

d2n(C(d1,d2,…,dn))=dG(C(d1,d2,…,dn))+1.

2 主要結果

引理3設G是n維無向超環(huán)面網(wǎng)C(d1,d2,…,dn)，S={o,u}是G的頂點子集，其中：o=(0,0,…,0)，u=(e1,e2,…,en)，這里n≥4，di≥5(i=1,2,…,n).對于任意頂點x∈V(G)-S，一定存在2n條內點不交且每條長度至多為

的S到x的路.

情形1頂點x的坐標都不為0.

子情形1.1頂點x的坐標xi不等于ei(i=1,2,…,n).

構造如下2n條內點不交的路，其中n條起點為o且每條長度為dG(o,x)的路P2t(1≤t≤n)，另外n條起點為u且每條長度為dG(e,x)的路P2t-1(1≤t≤n)，即

±為模dj同余(j=1,2,…,n).

子情形1.2頂點x有坐標xi值為ei(1≤i≤n).

不失一般性，設x=(x1,x2,…,xn-s,en-s+1,en-s+2,…,en)，這里0≤s≤n-1,xi≠0或ei(i=1,2,…,n-s).首先由子情形1.1可以構造n條從頂點o到頂點x的路P2t(1≤t≤n).

接著構造如下n條路，其中s條路P2t-1(n-s+1≤t≤n)起點為o，n-s條路P2t-1(1≤t≤n-s)起點為u，即

易知2n條路內點不交且長度不超過

情形2頂點x有坐標為0.

子情形2.1頂點x的坐標xi都不等于ei(i=1,2,…,n).

由點可遷性，類似于子情形1.2，可以構造2n條內點不交的路，其中n-s條路P2t(1≤t≤n-s)起點為o且每條長度為dG(o,x)，n條路P2t-1(1≤t≤n)起點為u且每條長度至多為dG(e,x)，另外s條路P2t(n-s+1≤t≤n)起點為u且每條長度至多為dG(e,x)+e′t-et.

子情形2.2頂點x有坐標xi等于ei，1≤i≤n.

不失一般性，設

x=(x1,x2，…,xn-s1-s2,en-s1-s2+1,en-s1-s2+2，…,en-s2,0,0，…,0)，

其中： 0≤s1≤n-1，xi≠0或ei(i=1,2,…,n-s1-s2).可得

類似地，容易構造2n條內點不交的路，其中n-s2條路P2t(1≤t≤n-s)起點為o且每條長度至多為dG(o,x),s1條路P2t-1(n-s1-s2+1≤t≤n-s2)起點為o且每條長度至多為dG(o,x)+e′t-et，n-s1條路P2t-1(1≤t≤n-s1-s2或n-s2+1≤t≤n)起點為o且每條長度至多為dG(e,x)，s2條路P2t(n-s2+1≤t≤n)起點為u且每條長度至多為dG(e,x)+e′t-et.

子情形1.1s=n-1.構造2n條從頂點o到頂點x且每條長度至多為dG(o,x)+6的路，即

(1)

(2)

(3)

子情形1.2s=n-2.構造2n條從頂點o到頂點x且每條長度至多為dG(o,x)+4的路，即

(4)

(5)

(6)

(7)

子情形3.2s=n-2.

如果e1-1≤min{x1,d1-x1}≤e1，且e2-1≤min{x2,d2-x2}≤e2，構造2n-2條像(4)～(7)的路，剩下2條路P3，P4如下：

路P3，P4長度至多為

子情形4.1s=n-1.類似于子情形 3.1.

情形1頂點x的坐標都不為0.

情形2頂點x有坐標為0.

子情形2.1頂點x至少有n-2個坐標為0.

由引理4可證.

子情形2.2頂點x至多有n-3個坐標為0.

不失一般性，設x=(x1,x2，…,xn-s,0,0，…,0)，其中： 1≤s≤n-3，0

構造2n條從頂點o到頂點x內點不交且每條長度至多為dG(o,x)+2的路：

定理1證畢.

3 結論和思考