国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

條件故障下3-元n-立方體的容錯分析

2021-08-18 08:53秦學姣
山東科學 2021年4期
關鍵詞:連通性立方體頂點

秦學姣

(新疆醫(yī)科大學 厚博學院,新疆 克拉瑪依 834000)

在設計一個互連網絡時,容錯性是一個基本原則,邊連通性是衡量互連網絡容錯性的一個重要指標。圖G的邊連通度,記作λ(G),定義為使G不連通時需刪除的最小邊數。然而,邊連通度往往低估了多處理系統(tǒng)的容錯能力。在很多情況下,當故障邊數大于邊連通度時,一個具有故障邊的網絡仍可能是連通的,或者存在較大的連通分支[1-3]。因此,互連網絡的容錯性與帶有故障邊的網絡的較大連通分支的頂點數密切相關。

假設F是圖G的一故障邊集,G-F是從G中刪除F得到的圖,u和v是圖G-F中的兩個頂點,我們關心的是G-F中u和v之間的邊不相交無故障路徑的數目。我們將此問題考慮為邊故障條件下的Menger定理[4]。近年來,學者們對互連網絡的Menger特性進行了大量的研究[5-7]。特別地,Qiao等[6]研究了條件故障下的超立方體和折疊超立方體的強Menger邊連通性。

k-元n-立方體是一類重要的互連網絡。一方面,其包括了傳統(tǒng)的互連網絡作為其子類,如環(huán)(1-元n-立方體)、超立方體(2-元n-立方體)和環(huán)面(k-元 2-立方體)。另一方面,目前已經建立了多個大型并行分布式計算系統(tǒng),如Gray T3D、J-machine、iWarp和Blue Gene,都是基于k-元n-立方體的拓撲結構。近年來,k-元n-立方體的許多拓撲性質得到了廣泛的研究[8-13]。例如,Li等[9]考慮了路限制條件下將路和圈嵌入到3-元n-立方體中的問題;Yuan等[11]研究了3-元n-立方體網絡的g-好鄰點條件可診斷性。目前,有關條件故障下k-元n-立方體的強Menger性的研究較少。本文研究了具有條件邊故障的3-元n-立方體網絡的較大連通分支和強Menger邊連通性。

1 預備知識

定義1[5]連通圖G稱為條件邊故障下的f-強Menger連通度,是指在F?E(G),|F|≤f和δ(G-F)≥2條件下,G-F中任意一對頂點u和v之間存在min{degG-F(u),degG-F(v)}條邊不交的無故障路。

2 帶有故障邊的3-元n-立方體的較大連通分支

取(t+1)組3-元子立方體,其頂點集互不相交。用Qi代表第i組3-元子立方體,這里0≤i≤t。而每一個Qi包含xi個3-元yi-維子立方體,記做Qi,1,…,Qi,xi。

Qi,ji表示第ji個3-元yi-維子立方體,這里0≤i≤t,1≤ji≤xi≤2。G1可以用一種遞歸的方式得到。給定Q0,j0,其包含x0個3-元y0-維子立方體,在不產生歧義的時候,我們也使用U1U2…Uy0-1Uy0(j0-1)00…00來代表Q0,j0,3-元yi-維子立方體Qi,ji(i>0)是指Qi-1,xi-1把第(yi-1+1)位的(ji-1-1)改為xi-1,把Qi-1,xi-1的第(yi+1)位坐標改為(ji-1)而獲得。除了第(yi-1+1)位坐標外,令第(yi+2)位坐標到第yi-1位坐標都是0。G1的構造如圖1所示。

圖1 G1的構造

圖的圖示

為了方便理解這個構造的方法,下面舉一個具體的例子(圖2):

構造如下:

Q0,j0,j0=1:U1U20;

Q1,j1,j1=1:U101;

Q2,j2,j2=1,2:011,111。

且V(G1)={000,100,200,010,110,210,020,120,220}∪{001,101,201}∪{011}∪{111}={000,100,200,010,110,210,020,120,220,001,101,201,011,111}。

按照這個定理的結論,我們可以得到表1。

表1 帶有故障邊的的較大連通分支

3 帶有條件邊故障的的強Menger邊連通度

證明:使用數學歸納法來證明。當n=2時,引理結論顯然成立。假設引理對n-1時結論成立。下面證明引理對n結論成立,這里n≥3。

情況1 |S2|≤4n-7

情形1.1 |S0|≤|S1|≤|S2|≤2n-3

情形1.2 |S0|≤|S1|≤2n-3且2n-2≤|S2|≤4n-7

情形1.3 |S0|≤2n-3且2n-2≤|S1|≤|S2|≤4n-7

情況2 |S0|≤|S1|≤4n-7且4n-6≤|S2|≤4n-3

綜上所述,引理得證。

注解3.2 引理3.1的結果是最優(yōu)的。

證明方法與引理3.1類似,故略。

注解3.4 引理3.3的結果是最優(yōu)的。

情況1 |V(H)|=3n-1

情況2 |V(H)|=3n-2

下面,證明這個結論是最優(yōu)的。

圖3 定理3.5的圖示Fig.3 Illustration for the Theorem 3.5

猜你喜歡
連通性立方體頂點
偏序集及其相關拓撲的連通性?
植被覆蓋度和降雨侵蝕力變化對小流域泥沙連通性的影響
中國自然保護地連通性的重要意義與關鍵議題
過非等腰銳角三角形頂點和垂心的圓的性質及應用(下)
過非等腰銳角三角形頂點和垂心的圓的性質及應用(上)
去2 度點后不滿足Pósa- 條件的圖的Z3- 連通性
內克爾立方體里的瓢蟲
圖形前線
立方體星交會對接和空間飛行演示
折紙
江西省| 泽库县| 凤山县| 延庆县| 贵阳市| 阿拉善盟| 桐城市| 曲麻莱县| 布拖县| 定南县| 科尔| 双桥区| 宁陵县| 长武县| 广平县| 含山县| 昆山市| 卢湾区| 北票市| 峡江县| 靖安县| 望江县| 饶阳县| 区。| 攀枝花市| 增城市| 泰来县| 砚山县| 微山县| 双辽市| 泸定县| 普定县| 荆门市| 石嘴山市| 綦江县| 山阴县| 麻江县| 北票市| 商河县| 广州市| 十堰市|