資源描述:
《有關(guān)加強(qiáng)超立方體泛連通性的證明-論文.pdf》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、學(xué)園lXUEYUAN2014年第13期有關(guān)加強(qiáng)超立方體泛連通性的證明范漪涵劉紅三峽大學(xué)理學(xué)院【摘要】在本文中,我們研究容錯(cuò)加強(qiáng)超立方體Q,中的路和圈的嵌入問(wèn)題。利用已知的結(jié)論當(dāng)(≥2)和k有不同奇偶性時(shí),Q一{_廠}包含了長(zhǎng)從4到2一2容錯(cuò)偶泛圈和長(zhǎng)從,z—k+2到2一1的容錯(cuò)奇泛圈;當(dāng)和k有不同奇偶性時(shí)Q,(1≤≤一1)是哈密頓連通的。【關(guān)鍵詞】加強(qiáng)超立方體偶泛連通性哈密頓連通性【中圖分類(lèi)號(hào)】029【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】1674—4810(2014)13—0078—01在互聯(lián)網(wǎng)絡(luò)中,一個(gè)
2、網(wǎng)絡(luò)是否可以被另一個(gè)網(wǎng)絡(luò)模擬是現(xiàn)在考慮下面兩種情況:非常重要的,這就是我們所說(shuō)的嵌入問(wèn)題。超立方體Q是情況1:X和Y在不同的二部劃分集中,設(shè)“是Q中X現(xiàn)如今最受歡迎的互聯(lián)網(wǎng)絡(luò)之一,它具有很多優(yōu)良的性質(zhì),的一個(gè)鄰點(diǎn),并且,“≠,“不和Y相鄰。因此X和是屬如可嵌人性、可遷性、對(duì)稱(chēng)性、正則性、遞歸性等。關(guān)于折于Q中不同的二部劃分集。從引理可得,不管Q是(一疊超立方體的一些性質(zhì),前人已做了很多的研究。然而,對(duì)1).維的加強(qiáng)超立方體還是(一1).維的超立方體在Q中于更一般的形式,加強(qiáng)超立方體的研究卻比較少
3、,我們主要都存在和“之間的一條哈密爾頓路P,并且這條路長(zhǎng)為證明:當(dāng)n和k有不同的奇偶性時(shí),.維加強(qiáng)超立方體Q,2"-1—1。因?yàn)椤蔘,并且和“相鄰,“和Y是屬于Q是哈密頓連通的。中不同的二部劃分集。從引理可得,不管Q:是(一1).一預(yù)備知識(shí)維的加強(qiáng)超立方體還是(一1).維的超立方體,在Q:中都下面給出一些對(duì)于我們的主要證明很重要的一些引理:存在和y之間的一條哈密爾頓路R,并且這條路長(zhǎng)為一1。引理1:設(shè)廠是FQ中的一個(gè)故障點(diǎn),其中≥3,那么因此P+(”,)+R是,中X和Y之間的一條哈密爾頓路。Q一
4、{“,}包含從4到2一2lFJl任意長(zhǎng),的偶圈,且如果情況2:X和Y在相同的二部劃分集中,如果Q和Q是n是偶數(shù),對(duì)于"≥2,F(xiàn)Q_廠包含從+1到2“一2任意長(zhǎng)z兩個(gè)("一1).維的超立方體。設(shè)“是Q中的一個(gè)鄰點(diǎn)且使的奇圈。得0n“中,“不是Y的補(bǔ)邊。因此X和是屬于QiO中不引理2:n維超立方體是二部圖并且是強(qiáng)哈密頓脆弱的。同的二部劃分集。從引理可得,在Q中存在X和之間的一引理3:當(dāng)n和k具有相同奇偶性時(shí),維加強(qiáng)立方體條哈密爾頓路P,并且這條路長(zhǎng)為~一1。又因?yàn)楹途呤菑?qiáng)哈密頓脆弱的。有不同的奇偶性
5、時(shí),hw()和hw()有相同的奇偶性。引理4:當(dāng)n=l或者n(≥2)是偶數(shù)時(shí),"維折疊超立因?yàn)楹偷钠媾夹韵嗤汀钡钠媾夹圆煌?,和Y是屬于方體FQ是哈密爾頓連通的。Q中不同的二部劃分集。由引理可得,在Q中存在和Y引理5:當(dāng)是奇數(shù)時(shí),維折疊超立方體FQ是偶泛之間的一條哈密爾頓路R,且這條路長(zhǎng)為2一1。因此P+連通的。(甜,)+R是Q樅中X和Y之間的一條哈密爾頓路。如果Q二加強(qiáng)超立方體的偶泛連通性和哈密頓連通性和Q是兩個(gè)(”一1).維的加強(qiáng)超立方體。設(shè)“是Q中X下面的一個(gè)定理證明了當(dāng)n和k具有不同的
6、奇偶性時(shí),的一個(gè)鄰點(diǎn),且使得“≠。由歸納可知,在Q中存在X和n維加強(qiáng)超立方體Q,的連通性質(zhì)。之間的一條哈密爾頓路P,且在Q中存在和Y之間的一定理1:當(dāng)n和k具有不同的奇偶性時(shí),”維加強(qiáng)超立條哈密爾頓路R,并且這兩條路的長(zhǎng)都為~一1,這P+(“,方體Q,是哈密爾頓連通的。)+R是Q,中X和Y之間的一條哈密爾頓路。證明:我們對(duì)n用歸納假設(shè)法來(lái)證明這個(gè)定理,從引理三小結(jié)可知,當(dāng)=1,一是偶數(shù)時(shí),這個(gè)定理是成立的?,F(xiàn)在我們?cè)诨ヂ?lián)網(wǎng)絡(luò)中,圈和路的嵌入問(wèn)題是一個(gè)非常重要的課考慮≥3的情況,當(dāng)n=3,k=2時(shí)
7、,這個(gè)結(jié)果很明顯是成題。而對(duì)于作為超立方體變形得到的網(wǎng)絡(luò)——加強(qiáng)超立方體立的?,F(xiàn)在我們來(lái)討論當(dāng)”,4和”;k有不同的奇偶性時(shí),中的圈和路的嵌入問(wèn)題更是值得我們討論。在本文中,我們這個(gè)定理也是成立的。設(shè)X:XlX2?Xn和:=),2?是Q,得到了;當(dāng)和k的奇偶性不同時(shí),加強(qiáng)超立方體是哈密頓中不同的兩個(gè)頂點(diǎn)。很明顯,存在一個(gè)f使得Xi≠。對(duì)Q,連通的,即對(duì)加強(qiáng)超立方中的任意兩個(gè)頂點(diǎn)與Y之間必存進(jìn)行f一劃分后得到兩個(gè)(”一1).維的加強(qiáng)超立方體或者是在一條長(zhǎng)為V(G)一1的路來(lái)連接這兩個(gè)頂點(diǎn)。兩個(gè)("
8、一1)一維的超立方體Q和Q使得和Y不在同一個(gè)子立方體中。不失一般性,我們可以設(shè)∈Q和Y∈Q,[責(zé)任編輯:李錦雯]一78一