基于超立方體和圈的細(xì)胞分裂生長網(wǎng)絡(luò)及其性質(zhì)

常立婷+師海忠

摘要：立方連通圈是超立方體的有界變型，在這篇文章中作者以立方連通圈網(wǎng)絡(luò)CCC（n）（n>2）為基礎(chǔ)設(shè)計(jì)了一種新網(wǎng)絡(luò)一CCC（n，k）（n>2且k是非負(fù)數(shù)），它是3正則3連通的，且有許多好的性質(zhì)。作者證明了CCC（3，0）是哈密爾頓連通圖，且CCC（n，k）（n>2且k是非負(fù)數(shù)）是哈密爾頓圖，但當(dāng)k>2和n>2或者k=l和22且k是非負(fù)數(shù)）和C_m的笛卡爾積的一些性質(zhì)。

關(guān)鍵詞：立方連通圈；CCC（n，k）；哈密爾頓圖；哈密爾頓連通圖；點(diǎn)可遷的

當(dāng)且僅當(dāng)，或者：

（i）x=y且/i-j/；l（modn）

（ii）i=j且x和y恰有第i個指標(biāo)不同。

圖1表示了Q₃到CCC（3）的變化

定義3^/10/：若一個圖具有這樣的一個圖形，它的邊僅在端點(diǎn)處相交，則該圖稱為平面圖。

定義4^/10/：G的Hamilton圈是指包含G的每個頂點(diǎn)的圈。

定義5^/10/： -個圖若包含Hamilton圈，則稱這個圖是Hamilton圖。

定義6^/10/：若一個圖中任意兩個頂點(diǎn)之間都有一條Hamilton路，則稱這個圖為Hamilton連通圖。

定義7^/9/：如果G是點(diǎn)可遷的，那么對G的每對頂點(diǎn)x和y，存在0∈Aut（G），使得y=0（x）。

定義8^/9/：設(shè)Γ=（X，o）是非平凡有限群，S是X的非空子集，且不含的r單位元e，定義有向圖如下：V（G）=Γ ；（x，y）∈E（G）<=>x^-1 y∈S，x，y∈r稱G為Γ 關(guān)于S的Cayley圖，記為C_r（S）。

定義9：兩個無向圖G=（V，E）和G'=（V'，E'），這里V={μ₁，μ₂，…μ_/v'/）和V'={v₁，v₂，…v_/v'/），G和G'的笛卡爾積定義為無向圖GxG'，其中頂點(diǎn)集為{μv/μ∈V，v∈V'），

邊集為{（μv，μ'v'）I（μ=μ'，（v，v'）∈E'或（v=v'，（μ，μ'）∈E'））.

定義10：用3長的圈C₃=（0，1，2）代替CCC（n）的每個頂點(diǎn)，且C3中每個頂點(diǎn)僅位于CCC（n）中與該頂點(diǎn)關(guān)聯(lián)的一條邊上，我們得到新網(wǎng)絡(luò)CCC（n，1）；用3長的圈C3 =（0，1，2）代替CCC（n，1）的每個頂點(diǎn)，且C3中每個頂點(diǎn)僅位于CCC（n，1）中與該頂點(diǎn)關(guān)聯(lián)的一條邊上，我們得到新網(wǎng)絡(luò)CCC（n，2）；重復(fù)k次，我們得到新網(wǎng)絡(luò)CCC，（n，k）。

2 CCC（3，0）的哈密爾頓連通性

引理2.1[9]：CCC（n）是點(diǎn)可遷的。

定理2.1： CCC（3，0）是哈密爾頓連通圖。

證明：CCC（3，0）即為CCC（3），故我們要證的是CCC（3）是哈密爾頓連通圖。由引理2.1知CCC（3）是點(diǎn)可遷的，所以我們只需找到（000；0）到（000；1）和（000；2）；（000；1）到（000；2）以及（000；0）：（000；1）和（000；2）分別到（010；0）、（010；1）、（010.2）、（10l；0）、（101；1）、（101；2）、（111；0）、（111；1）、（111；2）的一條Hamilton路即可。3 CCC（n，k）（n≥3，k≥0）的一些性質(zhì)

引理3.1^[9]：CCC（3）是平面圖；（如圖2所示）

引理3.2^[9]： CCC（n）是Hamilton圖

引理3.3^[9]：設(shè)G是n階點(diǎn)可遷圖，則

（a）G是正則的：

（b）G的所以n-l階子圖是同構(gòu)的

引理3.4^[9]： Cayley圖是點(diǎn)可遷的，但點(diǎn)可遷圖不一定是Cayley圖

引理3.5^[9]：設(shè)C是的CCC（n） -個圈，/（c）是圈C的長度，L（n）表示CCC（n）中所有圈的

集合，設(shè)l（c）∈{3，4，5，6，7}，則l（c）∈l（n），當(dāng)且僅當(dāng)/（c）=n

定理3.1： CCC（n，k（n≥3，k≥0）的一些性質(zhì)：

（1） CCC（n，k）（n≥3，k≥0）有個n3^k2ⁿ”頂點(diǎn)，n3^k+12^n-1”條邊；

（2 ）CCC（n，k）（n≥3，k≥0）是3正則3連通的；

（3） CCC（3，k）（k≥0）是平面圖；

（4） CCC（n，k）（n≥3，k≥0）是Hamilton圖；

（5） CCC（n，1）（3≤n≤7）不是點(diǎn)可遷的；

（6） CCC（n，1）（3≤n≤7）不是Cayley圖；

（7） CCC（n，k）（n≥3，k≥2）不是點(diǎn)可遷圖；

（8） CCC（n，k）（n≥3，k≥2）不是Cayley圖。

證明：（1），（2）顯然（3）由引理3.1知CCC（3）是平面圖，故如圖3 CCC（3，1）是平面圖，依次下去可知CCC（3，k）（k≥0）是平面圖；

（4）我們用數(shù)學(xué)歸納法證明結(jié)論

當(dāng)時(shí)k=0，CCC（n，0）即為CCC（n），所以結(jié)論顯然成立。

假設(shè)當(dāng)k=r-l時(shí)，結(jié)論成立，即CCC（n，r -1）有一個哈密爾頓圈C_{ccc（n，r-1）}，則當(dāng)k=r時(shí)設(shè)V則CCC（n，r-1）的任意頂點(diǎn)，v₁，v₂，V₃是與v相鄰的三個頂點(diǎn)，則C_{ccc（n，r-1）}中必含邊v₁v，V₂V，V₃V中的兩條邊。假設(shè)C_{ccc（n，r-1）}中含邊v₁v，V₂。V₂v，（其他情況證明類似）（見圖4），當(dāng)用3長的圈代替CCC_{（n，r-1）}中的每個頂點(diǎn)時(shí)，我們假設(shè)用圈v_iv_iv_i代替v_i（o≤i≤3）。用圈v¹vv₂vv₃代替1，，則v，v₁，v₂，v₃四點(diǎn)處變化后的圖為圖5。用路p_v= （v³/₁，v³，v¹，v²，v²/₂）代替路（ V₁Vv₂）后，得到的圈C_{ccc（n，r-1）}即為CCC_{（n，r）}的一個哈密爾頓圈。

綜上所述，由數(shù)學(xué)歸納法知CCC_（n，k）是哈密爾頓圖。

（5）這里我們僅證明n=7的情況其余情況類似可說明，CCC（7）中必有圖6所示結(jié)構(gòu)，為了方便起見，我們將圖中頂點(diǎn)分別標(biāo)號l，2，…，n+l。

當(dāng)用3長的圈代替CCC（7）中的每個頂點(diǎn)時(shí)，我們假設(shè)用圈i₁i₂i₃代替i（0≤i≤8），圖6中結(jié)構(gòu)變化后結(jié)構(gòu)如圖7，則圖7中結(jié)構(gòu)即為CCC（7，1）中的一部分不失一般性，設(shè)在CCC（7，1）中去掉頂點(diǎn)l，后得到的圖為CCC'（7，1），而圖7中結(jié)構(gòu)所對的結(jié)構(gòu)變?yōu)閳D8，CCC（7，1）中去掉頂點(diǎn)l，后得到的圖為CCC'（n，k），而圖7中結(jié)構(gòu)所對的結(jié)構(gòu)變?yōu)閳D9（注意為了方便起見，我們將CCC'（7，1）和CCC"（7，1）中的點(diǎn)分別加了表示“'”， “"”，且CCC（7，1）與CCC'（7，1）和CCC"（7，1）僅在圖7部分不同，其余結(jié)構(gòu)均相同）因此CCC'（7，1）中頂點(diǎn)除I'₂，I'₃，8'為2度頂點(diǎn)外，其余均為3度頂點(diǎn)，CCC"（7，1）除7"₃，l"₁，l"₃頂點(diǎn)為2度頂點(diǎn)外，除其余均為3度頂點(diǎn)，由引理3.3知我們只需證CCC'（7，1）與CCC"（7，1）不同構(gòu)即可。假設(shè)CCC'（7，1）≌CCC"（7，1），即存在①使得Φ（a）=b_i（a_i∈V（ccc'（7，1））b_i∈V（CCC"（7，1）））

因?yàn)榕c頂點(diǎn)8'₁：相連的頂點(diǎn)8'₂：，8'₃均為3度頂點(diǎn)，而與頂點(diǎn)l"₁相連的頂點(diǎn)1"₃為2度頂點(diǎn)，與頂點(diǎn)l"₃相連的頂點(diǎn)1"₁：為2度頂點(diǎn)，故Φ（8'₁）≠1"₁且Φ（8'₁）≠l"₃， 因此Φ（8'₁）=7"₁， 即想要CCC'（7，1）≌CCC"（7，1），

由引理3.5知，在CCC（7）中l(wèi)含在7長的基本圈12345671里，含1的其他圈均大于7，故在CCC（7，1）中l(wèi)₂和I₃含在14圈1₂1₃2₂2₃3₂3₃4₂4₃5₂5₃6₂6₃7₂7₃1₂里，含l₂和l₃的長其他圈均大于14（除l₁1₂1₃），故在CCC'（7，1）中1'₂和l'₃含在14長圈l21：22233233424352536263727312里，而在CCC"（7，1）中含1"₁和l"₃的圈均大于14，即

綜上所述，C，CC'（7，1）與CCC"（7，1）不是同構(gòu)的， 即CCC（7，1）不是點(diǎn)可遷圖。CCC_（n，1）（3≤n≤7）不是點(diǎn)可遷圖。

（6）由引理3.4和（5）顯然可得。

（7）當(dāng)時(shí)k>2，CCC_（n，k）（n≥3）中必有圖10所示結(jié)構(gòu)，為了方便起見我們將圖中頂點(diǎn)標(biāo)記為1-18，不失一般性，我們不妨設(shè)在CCC_{（n，k）}中去掉頂點(diǎn)3后得到的圖為CCC_{（n，k）}，而圖10中結(jié)構(gòu)所對的結(jié)構(gòu)變?yōu)閳D11，CCC_{（n，k）}中去掉頂點(diǎn)1后得到的圖為CCC"_{（n，k）}，而圖10中結(jié)構(gòu)所對的結(jié)構(gòu)變?yōu)閳D12，（注意為了方便起見，我們將CCC'_{（n，k）}和CCC"_（n，k）中的點(diǎn)分別加了表示“'”，“"”，且CCC_{（n，k）}與CCC'_{（n，k）}和CCC"_（n，k）僅在圖10部分不同，其余結(jié)構(gòu)均相同）因此，CCC'_{（n，k）}除1'，2'，7'頂點(diǎn)為2度頂點(diǎn)外，其余均為3度頂點(diǎn)，CCC"_（n，k）除2"，3"，10"頂點(diǎn)為2度頂點(diǎn)外，其余均為3度頂點(diǎn)，由引理3.3知，我們只需證CCC'_（n，k）與CCC"_{（n，k）}不同構(gòu)即可。假設(shè)CCC'_{（n，k）}蘭endprint

CCC"_{（n，k）}，即存在Φ使得Φ（a_i）=b_i∈V（CCC'_（n，k））），b_i∈V（CCC"_（n，k））））

因?yàn)榕c頂點(diǎn)7'相連的頂點(diǎn)8'，9'均為3度頂點(diǎn)，而與頂點(diǎn)2"相連的頂點(diǎn)3"為2度頂點(diǎn)，與頂點(diǎn)3"相連的頂點(diǎn)2"為2度頂點(diǎn)，故Φ（7"）≠2"且Φ（7'）≠3"，因此①（7'）=10"，即想要CCC'_（n，k）≌CCC"_（n，k）.

由圖12顯然2"4"6"8"7"3"2"為一個6長的圈，即CCC"_{（n，k）}中2"和3"在一個6長的圈中，而10'1'2'4'為4長的路，與頂點(diǎn)10'相連11'和12'的都不與與4'相連的5'和6'相連，故1'和2'不可能在一個6

綜上所述，CCC，，（n，"與CCC，”（聆，”不是同構(gòu)的，即CCC_（n，k）（k≥2）不是點(diǎn)可遷圖。

（8）由引理3.4和（7）顯然可得。4 CCC_（n，k）（k≥2）與圈C_m的笛卡爾積

引理4.1[9]：設(shè)G=（V，E）和G'=（V'，E'），GxG'為G和G'的笛卡爾積則

（1）如果G和G'分別為r正則和r'正則的，

則GxG'是r+r'正則的。

（2）如果κ（G）=δ（G）>0，κ（G'）=δ（G'）0，那么κ（G×G'）=κ（G）+κ（G'）

引理4.2[9]： Hamilton圖的笛卡爾積是Hamilton圖。根據(jù)文[13]和[14]，我們設(shè)計(jì)出了新的互連網(wǎng)絡(luò)CCC_{（n，k）}（n≥3，k≥0×Cm。

引理4.3：如果G=（V，E）是哈密爾頓連通圖，C_k為一個k長的圈，則G×C，k是哈密爾頓連通圖。

證明：設(shè)G=（V，E）是哈密爾頓連通圖，其中V={x₁，x₂：….，X_/V/}，C_k為k長的圈，其中V_c={y₁，y₂….，y_k}，定義GxC_k為G和C_k的笛卡爾積。設(shè)G_j= （V_j，E_j）為Gx C_k的子圖。

其中Vj={xy_jx∈V.顯然，G_j≌G。定義endprint