有關(guān)加強(qiáng)超立方體泛連通性的證明

【摘 要】在本文中，我們研究容錯(cuò)加強(qiáng)超立方體Qn，k中的路和圈的嵌入問題。利用已知的結(jié)論當(dāng)n（≥2）和k有不同奇偶性時(shí)， 包含了長從4到2n-2容錯(cuò)偶泛圈和長從n-k+2到2n-1的容錯(cuò)奇泛圈；當(dāng)n和k有不同奇偶性時(shí)Qn，k（1≤k≤n-1）是哈密頓連通的。

【關(guān)鍵詞】加強(qiáng)超立方體 偶泛連通性 哈密頓連通性

【中圖分類號(hào)】O29 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-4810（2014）13-0078-01

在互聯(lián)網(wǎng)絡(luò)中，一個(gè)網(wǎng)絡(luò)是否可以被另一個(gè)網(wǎng)絡(luò)模擬是非常重要的，這就是我們所說的嵌入問題。超立方體Qn是現(xiàn)如今最受歡迎的互聯(lián)網(wǎng)絡(luò)之一，它具有很多優(yōu)良的性質(zhì)，如可嵌入性、可遷性、對(duì)稱性、正則性、遞歸性等。關(guān)于折疊超立方體的一些性質(zhì)，前人已做了很多的研究。然而，對(duì)于更一般的形式，加強(qiáng)超立方體的研究卻比較少，我們主要證明：當(dāng)n和k有不同的奇偶性時(shí)，n-維加強(qiáng)超立方體Qn，k是哈密頓連通的。

一 預(yù)備知識(shí)

下面給出一些對(duì)于我們的主要證明很重要的一些引理：

引理1：設(shè)f是FQn中的一個(gè)故障點(diǎn)，其中n≥3，那么Qn-{u，ui}包含從4到 任意長l的偶圈，且如果n是偶數(shù)，對(duì)于n≥2，F(xiàn)Qn-f包含從n+1到2n-2任意長l的奇圈。

引理2：n維超立方體是二部圖并且是強(qiáng)哈密頓脆弱的。

引理3：當(dāng)n和k具有相同奇偶性時(shí)，n維加強(qiáng)立方體是強(qiáng)哈密頓脆弱的。

引理4：當(dāng)n=1或者n（≥2）是偶數(shù)時(shí)，n維折疊超立方體FQn是哈密爾頓連通的。

引理5：當(dāng)n是奇數(shù)時(shí)，n維折疊超立方體FQn是偶泛連通的。

二 加強(qiáng)超立方體的偶泛連通性和哈密頓連通性

下面的一個(gè)定理證明了當(dāng)n和k具有不同的奇偶性時(shí)，n維加強(qiáng)超立方體Qn，k的連通性質(zhì)。

定理1：當(dāng)n和k具有不同的奇偶性時(shí)，n維加強(qiáng)超立方體Qn，k是哈密爾頓連通的。

證明：我們對(duì)n用歸納假設(shè)法來證明這個(gè)定理，從引理可知，當(dāng)k=1，n是偶數(shù)時(shí)，這個(gè)定理是成立的。現(xiàn)在我們考慮n≥3的情況，當(dāng)n=3，k=2時(shí)，這個(gè)結(jié)果很明顯是成立的。現(xiàn)在我們來討論當(dāng)n，4和n；k有不同的奇偶性時(shí)，這個(gè)定理也是成立的。設(shè)x=x1x2…xn和y=y1y2…yn是Qn，k中不同的兩個(gè)頂點(diǎn)。很明顯，存在一個(gè)i使得xi≠yi。對(duì)Qn，k進(jìn)行i-劃分后得到兩個(gè)（n-1）-維的加強(qiáng)超立方體或者是兩個(gè)（n-1）-維的超立方體 和 使得x和y不在同一個(gè)子立方體中。不失一般性，我們可以設(shè) 和 ，現(xiàn)在考慮下面兩種情況：

情況1：x和y在不同的二部劃分集中，設(shè)u是 中x的一個(gè)鄰點(diǎn)，并且，u≠ ，u不和y相鄰。因此x和u是屬于 中不同的二部劃分集。從引理可得，不管 是（n-1）-維的加強(qiáng)超立方體還是（n-1）-維的超立方體在 中都存在x和u之間的一條哈密爾頓路P，并且這條路長為

2n-1-1。因?yàn)?，并且和u相鄰，ui和y是屬于

中不同的二部劃分集。從引理可得，不管 是（n-1）-維的加強(qiáng)超立方體還是（n-1）-維的超立方體，在 中都存在ui和y之間的一條哈密爾頓路R，并且這條路長為2n-1-1。因此P+（u，ui）+R是Qn，k中x和y之間的一條哈密爾頓路。

情況2：x和y在相同的二部劃分集中，如果 和 是兩個(gè)（n-1）-維的超立方體。設(shè)u是 中的一個(gè)鄰點(diǎn)且使得 在 中，u不是y的補(bǔ)邊。因此x和u是屬于 中不同的二部劃分集。從引理可得，在 中存在x和u之間的一條哈密爾頓路P，并且這條路長為2n-1-1。又因?yàn)閚和k具有不同的奇偶性時(shí)，hw（u）和hw（ ）有相同的奇偶性。因?yàn)閤和y的奇偶性相同而和u的奇偶性不同， 和y是屬于 中不同的二部劃分集。由引理可得，在 中存在 和y之間的一條哈密爾頓路R，且這條路長為2n-1-1。因此P+（u，ui）+R是Qn，k中x和y之間的一條哈密爾頓路。如果 和 是兩個(gè)（n-1）-維的加強(qiáng)超立方體。設(shè)u是 中x的一個(gè)鄰點(diǎn)，且使得ui≠y。由歸納可知，在 中存在x和u之間的一條哈密爾頓路P，且在 中存在ui和y之間的一條哈密爾頓路R，并且這兩條路的長都為2n-1-1，這P+（u，ui）+R是Qn，k中x和y之間的一條哈密爾頓路。

三 小結(jié)

在互聯(lián)網(wǎng)絡(luò)中，圈和路的嵌入問題是一個(gè)非常重要的課題。而對(duì)于作為超立方體變形得到的網(wǎng)絡(luò)——加強(qiáng)超立方體中的圈和路的嵌入問題更是值得我們討論。在本文中，我們得到了；當(dāng)n和k的奇偶性不同時(shí)，加強(qiáng)超立方體是哈密頓連通的，即對(duì)加強(qiáng)超立方中的任意兩個(gè)頂點(diǎn)x與y之間必存在一條長為V（G）-1的路來連接這兩個(gè)頂點(diǎn)。

〔責(zé)任編輯：李錦雯〕