• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      故障超立方體類網(wǎng)絡(luò)的極大連通分支

      2019-08-28 05:51:50翟登鑫阿依古麗馬木提
      關(guān)鍵詞:連通分支點子立方體

      翟登鑫, 阿依古麗·馬木提

      (1. 喀什大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 新疆 喀什 844000; 2. 新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 新疆 烏魯木齊 830046)

      1 引言及預(yù)備知識

      互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)通常由一個連通圖G=(V,E)來表示,其中頂點表示處理器,邊表示通信鏈路.傳統(tǒng)上衡量網(wǎng)絡(luò)可靠性和容錯性的經(jīng)典參數(shù)是連通度和邊連通度.若F?V(G),圖G中刪去F中的所有點后,使得G-F是不連通或者是平凡的,則稱F是圖G的點割.類似地,若S?E(G),圖G中刪去S中的所有邊后,使得G-S是不連通或者是平凡的,則稱S是圖G的邊割.圖G的連通度用κ(G)表示,則κ(G)=min{|F|:F是G的點割}.圖G的邊連通度用λ(G)表示,則λ(G)=min{|S|:S是G的邊割}.然而這2個參數(shù)存在本質(zhì)的缺點,理想狀態(tài)下與圖G的一個頂點相鄰的所有頂點(或邊)不可能同時失效,但這在實際網(wǎng)絡(luò)應(yīng)用中幾乎是不可能的.由于幾乎所有同一處理器的相鄰處理器或同一處理器的所有鏈路都有可能同時失效,為了彌補這個缺點,可以通過對G-F的組件增加一些條件或限制來推廣經(jīng)典連通性的概念,其中F表示有故障的點(或邊).

      無向圖G=(V,E)由點集V和邊集E組成,其中V是有限集,E是V中任意2個不同元素的無序?qū)?gòu)成的集合.如果uv∈E,那么u和v兩點是相鄰接的,并且u和v是uv邊的端點.令v是G中的點,點v的鄰集N(v)是與v相鄰接的所有點構(gòu)成的集合,且|N(v)|被稱為點v的度數(shù),記作degG(v)或者簡記為deg(v).圖G中的一些點子集或邊子集,記作F,符號G-F表示從G中刪除F的元素所得到的子圖.令mc(G)為圖G中一個極大連通分支的最大階.圖G的點子集F,令N(F)={u∈V(G)-F:u是與F中的點相鄰接的點}.點子集V′?V,在子圖H(H?G)中的V′的鄰集,被定義為

      Vaidya等[1]提出了一類超立方體類網(wǎng)絡(luò),稱為HL-圖(或BC圖),它用以下完美匹配運算“⊕”遞歸定義:HL0={K1},

      i={0,1}, n≥1.

      顯然,HL1={K2},HL2={C4},HL3={Q3,G(8,4)},其中,C4是四圈,Q3是3維超立方體,且G(8,4)是一個遞歸循環(huán)圖[2],見圖1.

      圖 1 HL3

      HL-圖類不僅有小直徑,而且有一些優(yōu)良的特性,如正則性、連通性和哈密爾頓性.文獻[3]發(fā)現(xiàn),對HLn中任意滿足條件|F|≤2n-3(n≥2)的點集F,HLn-F包含一個連通分支,其階數(shù)至少為|V(HLn)|-|F|-1.同時,對HLn中任意滿足條件|F|≤3n-6(n≥5)的點集F,HLn-F包含一個連通分支,其階數(shù)至少為|V(HLn)|-|F|-2.但實際上,HLn中可能有更多故障點.因此,研究HLn中有大量故障點的最大連通分支的最大階具有重要意義.

      引理 1[1,4]設(shè)HLn是n維超立方體類網(wǎng)絡(luò),則下面4個性質(zhì)成立:

      1) |V(HLn)|=2n;

      2) |E(HLn)|=n·2n-1;

      3)HLn是n-正則的;

      4)κ(HLn)=n.

      引理 2[5]設(shè)n和k都是正整數(shù),1≤k≤n+1.若F是HLn中點子集,|F|=k,則

      此外,F是由HLn中一個點v和它的k-1個鄰點組成的點子集,則

      引理 3[6]設(shè)n、k、x、z都是正整數(shù),1≤k≤n-1,1≤x≤k-1,x+1≤z≤x+(k-1),若

      2k(n+1)-k(k+1)≥-z2+

      (2x+2n-1)z+(4-2x2),

      則z≤k-1.

      定理 1[2]若HLn中任意點子集F,|F|≤2n-3,n≥2,則

      mc(HLn-F)≥|V(HLn)|-|F|-1.

      此外,HLn中存在|F|=2n-2的點子集F,使得

      mc(HLn-F)≤|V(HLn)|-|F|-2.

      定理 2[2]若HLn中任意點子集F,|F|≤3n-6,n≥5,則

      mc(HLn-F)≥|V(HLn)|-|F|-.

      此外,HLn中存在|F|=3n-5的點子集F,使得

      mc(HLn-F)≤|V(HLn)|-|F|-3.

      2 主要結(jié)果

      引理 4設(shè)n是整數(shù),n≥5,x是實數(shù),則

      x2-(2n+5)x+(2n+1+4)>0.

      證明令△為一元二次方程:x2-(2n+5)x+(2n+1+4)=0的判別式,則

      △=(2n+5)2-4(2n+1+4)=

      (4n2+20n+9)-2n+3.

      用歸納法可以證明:當(dāng)n≥5時,2n+3>4n2+20n+9.因此

      △=(2n+5)2-4(2n+1+4)=

      (4n2+20n+9)-2n+3<0.

      因此,一元二次方程無實根,圖像全都在x軸上方,結(jié)論成立.

      mc(HLn-F)≥|V(HLn)|-|F|-(k-1).

      證明令S是HLn中一個點子集,其由一個點v和它的k-1個鄰點組成.根據(jù)引理2可知

      不失一般性,假設(shè)F=N(S).顯然,

      mc(HLn-N(S))=

      mc(HLn-F)=|V(HLn)|-|F|-k,

      即第二部分成立.

      下面用歸納法對第一部分進行討論.

      mc(HL4-F)≥|V(HL4)|-5-1.

      mc(HL5-F)≥|V(HL5)|-6-2.

      假設(shè)對n成立,其中n≥4.下面證明對n+1也成立.

      情形 11≤k≤n-2.下面分3種子情形進行討論.

      mc(HLn+1-F)≥|V(HLn+1)|-|F|-|T|≥

      |V(HLn+1)|-|F|-(k-1).

      其中0≤p≤r-1,0≤q≤r-1.

      根據(jù)引理4可知

      因此,

      |F|+(p+q),

      |V(C0)|=2n-|F0|-

      進一步,令x=|T0|,y=|T1|,z=x+y,則0≤x≤k-1,0≤y≤k-1,及

      mc(HLn+1-F)=|V(C)|=

      |V(HLn+1)|-|F|-(x+y).

      此時,x=0或y=0.接下來假設(shè)x≥1且y≥1.

      N*(T0)?F0,N*(T1)?F1.

      由此可知

      |F0|+|F1|≥|N*(T0)|+|N*(T1)|.

      由上述條件及引理2可知

      把y=z-x代入上式,化簡得

      2k(n+1)-k(k+1)≥

      -z2+(2x+2n-1)z+(4-2x2),

      其中,1≤x≤k-1,x+1≤z≤x+(k-1)≤x+(n-2).

      由上式和引理3可知,z≤k-1及

      mc(HLn+1-F)≥|V(HLn+1)|-|F|-|T|≥

      |V(HLn+1)|-|F|-(k-1).

      情形 2k=n-1,則

      下面分4種子情形進行討論.

      1) |F1|≤n-2,則|T|≤n-2,因此

      mc(HLn+1-F)≥|V(HLn+1)|-

      |F|-|T|≥|V(HLn+1)|-|F|-(n-2);

      2)T∩F0≠?,則

      mc(HLn+1-F)≥|V(HLn+1)|-

      |F|-|T|+1≥|V(HLn+1)|-|F|-(n-2);

      mc(HLn+1-F)≥|V(HLn+1)|-

      |F|-|T|+1≥|V(HLn+1)|-|F|-(n-2);

      令N*(T)=N(T)-F1.由假設(shè)可知,N*(T)?F0.因此

      這與引理2的

      相矛盾.

      此時,下面的討論與情形1.3類似.

      因此第一部分成立.

      mc(HLn-F)≤|V(HLn)|-|F|-(n-2).

      為了能夠使得對k=n-1也有類似定理3的結(jié)論,可以通過把定理3中F的取值減少1來得到.

      mc(HLn-F)≥|V(HLn)|-|F|-

      (k-1)=|V(HLn)|-|F|-(n-3).

      mc(HLn-F)≥|V(HLn)|-|F|-(n-2);

      猜你喜歡
      連通分支點子立方體
      疊出一個立方體
      偏序集的序連通關(guān)系及其序連通分支
      關(guān)于圖的距離無符號拉普拉斯譜半徑的下界
      好點子不足以支撐好買賣
      圖形前線
      立方體星交會對接和空間飛行演示
      太空探索(2016年9期)2016-07-12 09:59:53
      折紙
      一個圖論問題的簡單證明
      新課程(下)(2015年9期)2015-04-12 09:23:30
      交換環(huán)的素譜與極大譜的連通性
      點子將軍
      奧秘(2014年1期)2014-01-17 12:54:56
      余庆县| 济源市| 兴山县| 和平县| 桑植县| 呼伦贝尔市| 新巴尔虎左旗| 石景山区| 稷山县| 泽州县| 依兰县| 涪陵区| 儋州市| 定边县| 甘泉县| 彝良县| 长乐市| 涟水县| 平山县| 镇安县| 利川市| 万州区| 小金县| 萍乡市| 桂阳县| 吴桥县| 三穗县| 巴塘县| 沿河| 奉化市| 宁明县| 阳新县| 五华县| 阿克陶县| 长泰县| 惠安县| 拉萨市| 封丘县| 和平县| 子洲县| 神池县|