APP下载

基于超立方体和圈的细胞分裂生长网络及其性质

2018-03-02常立婷师海忠

软件 2017年9期

常立婷+师海忠

摘要:立方连通圈是超立方体的有界变型,在这篇文章中作者以立方连通圈网络CCC(n)(n>2)为基础设计了一种新网络一CCC(n,k)(n>2且k是非负数),它是3正则3连通的,且有许多好的性质。作者证明了CCC(3,0)是哈密尔顿连通图,且CCC(n,k)(n>2且k是非负数)是哈密尔顿图,但当k>2和n>2或者k=l和22且k是非负数)和Cm的笛卡尔积的一些性质。

关键词:立方连通圈;CCC(n,k);哈密尔顿图;哈密尔顿连通图;点可迁的

当且仅当,或者:

(i)x=y且/i-j/;l(modn)

(ii)i=j且x和y恰有第i个指标不同。

图1表示了Q3到CCC(3)的变化

定义3/10/:若一个图具有这样的一个图形,它的边仅在端点处相交,则该图称为平面图。

定义4/10/:G的Hamilton圈是指包含G的每个顶点的圈。

定义5/10/: -个图若包含Hamilton圈,则称这个图是Hamilton图。

定义6/10/:若一个图中任意两个顶点之间都有一条Hamilton路,则称这个图为Hamilton连通图。

定义7/9/:如果G是点可迁的,那么对G的每对顶点x和y,存在0∈Aut(G),使得y=0(x)。

定义8/9/:设Γ=(X,o)是非平凡有限群,S是X的非空子集,且不含的r单位元e,定义有向图如下:V(G)=Γ ;(x,y)∈E(G)<=>x-1 y∈S,x,y∈r称G为Γ 关于S的Cayley图,记为Cr(S)。

定义9:两个无向图G=(V,E)和G'=(V',E'),这里V={μ1,μ2,…μ/v'/)和V'={v1,v2,…v/v'/),G和G'的笛卡尔积定义为无向图GxG',其中顶点集为{μv/μ∈V,v∈V'),

边集为{(μv,μ'v')I(μ=μ',(v,v')∈E'或(v=v',(μ,μ')∈E')).

定義10:用3长的圈C3=(0,1,2)代替CCC(n)的每个顶点,且C3中每个顶点仅位于CCC(n)中与该顶点关联的一条边上,我们得到新网络CCC(n,1);用3长的圈C3 =(0,1,2)代替CCC(n,1)的每个顶点,且C3中每个顶点仅位于CCC(n,1)中与该顶点关联的一条边上,我们得到新网络CCC(n,2);重复k次,我们得到新网络CCC,(n,k)。

2 CCC(3,0)的哈密尔顿连通性

引理2.1[9]:CCC(n)是点可迁的。

定理2.1: CCC(3,0)是哈密尔顿连通图。

证明:CCC(3,0)即为CCC(3),故我们要证的是CCC(3)是哈密尔顿连通图。由引理2.1知CCC(3)是点可迁的,所以我们只需找到(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)的一些性质

引理3.1[9]:CCC(3)是平面图;(如图2所示)

引理3.2[9]: CCC(n)是Hamilton图

引理3.3[9]:设G是n阶点可迁图,则

(a)G是正则的:

(b)G的所以n-l阶子图是同构的

引理3.4[9]: Cayley图是点可迁的,但点可迁图不一定是Cayley图

引理3.5[9]:设C是的CCC(n) -个圈,/(c)是圈C的长度,L(n)表示CCC(n)中所有圈的

集合,设l(c)∈{3,4,5,6,7},则l(c)∈l(n),当且仅当/(c)=n

定理3.1: CCC(n,k(n≥3,k≥0)的一些性质:

(1) CCC(n,k)(n≥3,k≥0)有个n3k2n”顶点,n3k+12n-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)不是点可迁的;

(6) CCC(n,1)(3≤n≤7)不是Cayley图;

(7) CCC(n,k)(n≥3,k≥2)不是点可迁图;

(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)我们用数学归纳法证明结论

当时k=0,CCC(n,0)即为CCC(n),所以结论显然成立。

假设当k=r-l时,结论成立,即CCC(n,r -1)有一个哈密尔顿圈Cccc(n,r-1),则当k=r时设V则CCC(n,r-1)的任意顶点,v1,v2,V3是与v相邻的三个顶点,则Cccc(n,r-1)中必含边v1v,V2V,V3V中的两条边。假设Cccc(n,r-1)中含边v1v,V2。V2v,(其他情况证明类似)(见图4),当用3长的圈代替CCC(n,r-1)中的每个顶点时,我们假设用圈vivivi代替vi(o≤i≤3)。用圈v1vv2vv3代替1,,则v,v1,v2,v3四点处变化后的图为图5。用路pv= (v3/1,v3,v1,v2,v2/2)代替路( V1Vv2)后,得到的圈Cccc(n,r-1)即为CCC(n,r)的一个哈密尔顿圈。

综上所述,由数学归纳法知CCC(n,k)是哈密尔顿图。

(5)这里我们仅证明n=7的情况其余情况类似可说明,CCC(7)中必有图6所示结构,为了方便起见,我们将图中顶点分别标号l,2,…,n+l。

当用3长的圈代替CCC(7)中的每个顶点时,我们假设用圈i1i2i3代替i(0≤i≤8),图6中结构变化后结构如图7,则图7中结构即为CCC(7,1)中的一部分不失一般性,设在CCC(7,1)中去掉顶点l,后得到的图为CCC'(7,1),而图7中结构所对的结构变为图8,CCC(7,1)中去掉顶点l,后得到的图为CCC'(n,k),而图7中结构所对的结构变为图9(注意为了方便起见,我们将CCC'(7,1)和CCC"(7,1)中的点分别加了表示“'”, “"”,且CCC(7,1)与CCC'(7,1)和CCC"(7,1)仅在图7部分不同,其余结构均相同)因此CCC'(7,1)中顶点除I'2,I'3,8'为2度顶点外,其余均為3度顶点,CCC"(7,1)除7"3,l"1,l"3顶点为2度顶点外,除其余均为3度顶点,由引理3.3知我们只需证CCC'(7,1)与CCC"(7,1)不同构即可。假设CCC'(7,1)≌CCC"(7,1),即存在①使得Φ(a)=bi(ai∈V(ccc'(7,1))bi∈V(CCC"(7,1)))

因为与顶点8'1:相连的顶点8'2:,8'3均为3度顶点,而与顶点l"1相连的顶点1"3为2度顶点,与顶点l"3相连的顶点1"1:为2度顶点,故Φ(8'1)≠1"1且Φ(8'1)≠l"3, 因此Φ(8'1)=7"1, 即想要CCC'(7,1)≌CCC"(7,1),

由引理3.5知,在CCC(7)中l含在7长的基本圈12345671里,含1的其他圈均大于7,故在CCC(7,1)中l2和I3含在14圈121322233233424352536263727312里,含l2和l3的长其他圈均大于14(除l11213),故在CCC'(7,1)中1'2和l'3含在14长圈l21:22233233424352536263727312里,而在CCC"(7,1)中含1"1和l"3的圈均大于14,即

综上所述,C,CC'(7,1)与CCC"(7,1)不是同构的, 即CCC(7,1)不是点可迁图。CCC(n,1)(3≤n≤7)不是点可迁图。

(6)由引理3.4和(5)显然可得。

(7)当时k>2,CCC(n,k)(n≥3)中必有图10所示结构,为了方便起见我们将图中顶点标记为1-18,不失一般性,我们不妨设在CCC(n,k)中去掉顶点3后得到的图为CCC(n,k),而图10中结构所对的结构变为图11,CCC(n,k)中去掉顶点1后得到的图为CCC"(n,k),而图10中结构所对的结构变为图12,(注意为了方便起见,我们将CCC'(n,k)和CCC"(n,k)中的点分别加了表示“'”,“"”,且CCC(n,k)与CCC'(n,k)和CCC"(n,k)仅在图10部分不同,其余结构均相同)因此,CCC'(n,k)除1',2',7'顶点为2度顶点外,其余均为3度顶点,CCC"(n,k)除2",3",10"顶点为2度顶点外,其余均为3度顶点,由引理3.3知,我们只需证CCC'(n,k)与CCC"(n,k)不同构即可。假设CCC'(n,k)兰endprint

CCC"(n,k),即存在Φ使得Φ(ai)=bi∈V(CCC'(n,k))),bi∈V(CCC"(n,k))))

因为与顶点7'相连的顶点8',9'均为3度顶点,而与顶点2"相连的顶点3"为2度顶点,与顶点3"相连的顶点2"为2度顶点,故Φ(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长的路,与顶点10'相连11'和12'的都不与与4'相连的5'和6'相连,故1'和2'不可能在一个6

综上所述,CCC,,(n,"与CCC,”(聆,”不是同构的,即CCC(n,k)(k≥2)不是点可迁图。

(8)由引理3.4和(7)显然可得。4 CCC(n,k)(k≥2)与圈Cm的笛卡尔积

引理4.1[9]:设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图。根据文[13]和[14],我们设计出了新的互连网络CCC(n,k)(n≥3,k≥0×Cm。

引理4.3:如果G=(V,E)是哈密尔顿连通图,Ck为一个k长的圈,则G×C,k是哈密尔顿连通图。

证明:设G=(V,E)是哈密尔顿连通图,其中V={x1,x2:….,X/V/},Ck為k长的圈,其中Vc={y1,y2….,yk},定义GxCk为G和Ck的笛卡尔积。设Gj= (Vj,Ej)为Gx Ck的子图。

其中Vj={xyjx∈V.显然,Gj≌G。定义endprint