• 有關(guān)加強(qiáng)超立方體泛連通性的證明-論文.pdf

    ID:53757153

    大小:74.67 KB

    頁(yè)數(shù):1頁(yè)

    時(shí)間:2020-04-24

    有關(guān)加強(qiáng)超立方體泛連通性的證明-論文.pdf_第1頁(yè)
    資源描述:

    《有關(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一

    當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

    此文檔下載收益歸作者所有

    當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
    溫馨提示:
    1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
    2. 本文檔由用戶(hù)上傳,版權(quán)歸屬用戶(hù),天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
    3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
    4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶(hù)請(qǐng)聯(lián)系客服處理。
    关闭