亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        排列圖的限制邊連通度

        2021-04-02 05:14:34鄒婷婷曾雪倩李向軍
        關(guān)鍵詞:容錯(cuò)性鄰點(diǎn)基數(shù)

        鄒婷婷,曾雪倩,李向軍

        (長江大學(xué) 信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

        在大規(guī)模多元信息處理系統(tǒng)中,元件故障不可避免,當(dāng)故障發(fā)生時(shí)網(wǎng)絡(luò)對某些條件性質(zhì)的保持能力就是它的容錯(cuò)性能.在設(shè)計(jì)大規(guī)模網(wǎng)絡(luò)時(shí),高性能、低成本是最終目標(biāo).在選擇互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時(shí),處理器之間的有效通信是衡量系統(tǒng)性能的一個(gè)重要標(biāo)準(zhǔn),當(dāng)處理器數(shù)目逐漸增多時(shí),其發(fā)生故障的可能性也隨之增加,不同處理器之間信息傳遞過程中的容錯(cuò)性便成為一個(gè)非常關(guān)鍵的問題,為此有必要考慮網(wǎng)絡(luò)的容錯(cuò)性和可靠性.點(diǎn)連通度(記作κ(G))是使得G-T不連通的最小頂點(diǎn)子集T的基數(shù);邊連通度(記作λ(G))的定義類似,它是使得G-F不連通的最小邊子集F的基數(shù).但連通度假設(shè)任意頂點(diǎn)和任意邊可以同時(shí)發(fā)生故障,在實(shí)際應(yīng)用中并不能很好地反映網(wǎng)絡(luò)的彈性,Harary針對這一弱點(diǎn),引入了條件連通度的概念,對剩余的網(wǎng)絡(luò)提出了一些附加要求[1].此后,Latifi等[2]在一定意義上推廣了這一概念,通過限制每個(gè)頂點(diǎn)至少有h個(gè)無故障鄰點(diǎn),提出了h-限制連通度.在實(shí)際應(yīng)用中,這些廣義度量可以更準(zhǔn)確地估計(jì)互連網(wǎng)絡(luò)的容錯(cuò)性.

        用無向圖G=(V;E)表示互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),圖G的頂點(diǎn)V(G)代表系統(tǒng)中的元件,圖G的邊E(G)代表元件之間的物理連線[3].對于u∈V,u的度是與u關(guān)聯(lián)的邊數(shù),記作d(u),δ(G)表示圖G的最小度.假設(shè)G為連通圖,T是V(G)的子集,若G-T不連通且最小度至少為h,即δ(G-T)≥h,稱T是圖G的h-點(diǎn)割,h-限制點(diǎn)連通度(記作κh(G))是最小h-點(diǎn)割的基數(shù).對于邊故障的網(wǎng)絡(luò)容錯(cuò)性刻畫也有類似度量,F(xiàn)是E(G)的子集,若G-F不連通,且δ(G-F)≥h,稱F是圖G的h-邊割,h-限制邊連通度(記作λh(G))是最小h-邊割的基數(shù).顯然有κ0=κ,λ0=λ.對有向圖的點(diǎn)割研究也有不少學(xué)者關(guān)注[4-6],本文的主要研究對象是無向排列圖.在排列圖的容錯(cuò)性研究方面,國內(nèi)外學(xué)者對其點(diǎn)故障關(guān)注較多,Zhou等[7]、林麗美等[8]、Cheng等[9-10]學(xué)者在其限制連通度方面得到了部分重要結(jié)果;Wang等[11-12]、Lin等[13]、Lei等[14]、Xu等[15]等學(xué)者在子結(jié)構(gòu)容錯(cuò)方面做了很好的工作.目前對排列網(wǎng)絡(luò)邊故障情況的分析和探討還較少,而現(xiàn)實(shí)網(wǎng)絡(luò)中連線故障是確實(shí)存在的,本文利用圖結(jié)構(gòu)分析方法對排列圖An,2的邊故障容錯(cuò)能力進(jìn)行探索,當(dāng)h≤3時(shí)確定其限制邊連通度λh(An,2),該結(jié)果可為進(jìn)一步分析排列圖的邊故障容錯(cuò)能力提供借鑒.

        1 預(yù)備知識

        定義1[16]令n,k為兩個(gè)整數(shù),且1≤k

        圖1 排列圖A5,1和A4,2Fig.1 The arrangement graphs A5,1 and A4,2

        用Hi表示An,k一個(gè)頂點(diǎn)子集,它是第j(1≤j≤k)個(gè)位置元素pj為i(1≤i≤n)的排列.對頂點(diǎn)v∈Hi,v在Hi中的鄰點(diǎn)稱為內(nèi)鄰點(diǎn),v在An,k-Hi中的鄰點(diǎn)稱為外鄰點(diǎn).

        性質(zhì)1[16]當(dāng)2≤k

        性質(zhì)3[16]對于Hi中的j個(gè)頂點(diǎn),它們有j(n-k)個(gè)不相交的外鄰點(diǎn).

        2 主要結(jié)果

        主要考慮排列圖An,2的h-限制邊連通度.

        引理1 當(dāng)0≤h≤n-2時(shí),λh(An,2)≤(h+1)(2n-h-4).

        證明不失一般性,在H1中取一個(gè)(h+1)-團(tuán)(記為X),F(xiàn)表示X與N(X)之間所有的邊.由于An,2是2(n-2)-正則的,有|F|=2(n-2)(h+1)-h(h+1)=(h+1)(2n-h-4).

        以下證明F是一個(gè)h-邊割,令Y=G-X,證明δ(Y)≥h即可.如果j≠1,對于任意頂點(diǎn)u∈Hj,由于Hj是一個(gè)(n-1)-團(tuán),所以δY(u)≥δHj(u)=n-2≥h.對于任意頂點(diǎn)u∈H1-X,u有(n-2)個(gè)外鄰點(diǎn),從而有δY(u)≥n-2≥h,所以δ(Y)≥h.故F是一個(gè)h-邊割,λh(An,2)≤|F|=(h+1)(2n-h-4).引理得證.

        定理1 當(dāng)h∈{1,2,3},n≥h+2時(shí),λh(An,2)=(h+1)(2n-h-4).

        證明根據(jù)引理1,只需證明λh(An,2)≥(h+1)(2n-h-4).

        令F是An,2的最小h-邊割,只需證明|F|≥(h+1)(2n-h-4).

        假定X是An,2-F中一個(gè)連通分支,Y=An,k-X,令Xi=X∩Hi,Yi=Y∩Hi.

        令JX={i∈[n]:Xi≠?},JY={i∈[n]:Yi≠?},J0=JX∩JY;考慮這幾個(gè)集合大小,令a=|J0|,b=|JX-J0|,c=|JY-J0|,則a+b+c=n.因?yàn)閄與Y有對稱性,不妨假設(shè)|JX|≤|JY|.由于Hi表示第j(1≤j≤2)個(gè)位置元素pj為i(1≤i≤n)的排列,可以選擇某個(gè)j(1≤j≤2)使得|JX|盡可能大.

        用EC表示∪j1∈JX-J0Hj1與∪j2∈JY-J0Hj2之間所有的邊,對于j1∈JX-J0和j2∈JY-J0,Hj1與Hj2之間有n-2條相互獨(dú)立的邊,故|EC|≥bc(n-2).

        用EI表示∪j3∈J0Xj3與∪j3∈J0Yj3之間所有的邊,對于j3∈J0,由于Hj3同構(gòu)于Kn-1,故|EI|≥a(n-2).由于F是邊割,故EI?F.注意到EC?F,則有|F|≥|EC|+|EI|≥bc(n-2)+a(n-2)≥(a+bc)(n-2).

        如果bc≠0,則有(a+bc)(n-2)≥(n-1)(n-2),從而|F|≥(n-1)(n-2)≥(h+1)(2n-h-4).

        下面假設(shè)bc=0,由|JX|≤|JY|有b=0,從而|JX|=|J0|=a.

        下面考慮a

        考慮函數(shù)f(a)=a(2n-3-a),則|F|≥f(a).易知f(a)在區(qū)間[1,n-2]單調(diào)增加,且f(n-1)=f(n-2).

        h=1時(shí),a≥2,根據(jù)f(a)在[1,n-2]單調(diào)性,有|F|≥f(a)≥f(2)=4n-10.

        h=2時(shí),如果a≥3,由f(a)單調(diào)性,可知|F|≥f(a)≥f(3)=6n-18.

        h=3時(shí),如果a≥4,由f(a)單調(diào)性可知|F|≥f(a)≥f(4)=8n-28.

        所以h=1,2,3時(shí)都有λh(An,2)≥(h+1)(2n-h-4),定理得證.

        3 結(jié)語

        研究了排列圖An,2的邊故障容錯(cuò)能力,對n≥3確定λ1(An,2)=4n-10,對n≥4確定λ2(An,2)=6n-18,對n≥5確定λ3(An,2)=8n-28.當(dāng)h≥4時(shí)確定λh(An,2),以及對k≤n-2,h≤n-k確定λh(An,k)是值得進(jìn)一步研究的問題.

        猜你喜歡
        容錯(cuò)性鄰點(diǎn)基數(shù)
        基于視覺補(bǔ)充的水稻插秧機(jī)多傳感器組合定位研究
        一次性傷殘就業(yè)補(bǔ)助金的工資基數(shù)應(yīng)如何計(jì)算?
        圍長為5的3-正則有向圖的不交圈
        千萬不要亂翻番
        巧妙推算星期幾
        『基數(shù)』和『序數(shù)』
        基于認(rèn)知心理學(xué)的交互式產(chǎn)品的容錯(cuò)性設(shè)計(jì)研究
        特殊圖的一般鄰點(diǎn)可區(qū)別全染色
        基于免疫算法的高容錯(cuò)性廣域保護(hù)研究
        電測與儀表(2015年2期)2015-04-09 11:28:56
        基于多Agent的有限廣域方向比較算法與仿真實(shí)現(xiàn)
        国产精品高潮无码毛片| 射精专区一区二区朝鲜| 国产98在线 | 日韩| 日本免费人成视频播放| 亚洲精品久久久中文字| 亚洲视频在线观看一区二区三区| 亚洲av无码片vr一区二区三区| 人妻无码一区二区三区四区| 亚洲欧美国产精品久久久| 国产美女高潮流白浆视频| 成人a级视频在线播放| 精品国产av 无码一区二区三区| 国产久视频| 精品久久一区二区三区av制服 | 天堂sv在线最新版在线| 无码啪啪熟妇人妻区| 人妻少妇精品视频专区二区三区| 久久精品夜色国产亚洲av| 好爽…又高潮了毛片免费看 | 国产福利免费看| 久久精品国产亚洲av高清蜜臀| 国语对白免费观看123| 日射精情感性色视频| 91香蕉视频网| 性色av一区二区三区密臀av| 国产精品高清网站| 亚洲av无码av日韩av网站| 亚洲欧美国产精品久久| 国产自偷亚洲精品页65页| 最新日韩av在线不卡| 国产麻豆一区二区三区在| 中文字幕av长濑麻美| 亚洲av无码一区二区三区人| 人妻无码视频| 日本视频一区二区这里只有精品 | 国产亚洲精品精品精品| 99久久国产福利自产拍| аⅴ天堂一区视频在线观看| 丝袜美腿制服诱惑一区二区| 秋霞在线视频| a国产一区二区免费入口|