基于FQn和圈的细胞分裂生长网络FQCC(n,k) 及其性质

ComputerScienceandApplication计算机科学与应用,2017,7(10),960-973PublishedOnlineOctober2017inHans.://doi.org/10.12677/csa.2017.710109文章引用:赵媛,师海忠.基于FQn和圈的细胞分裂生长网络FQCC(n,k)及其性质[J].计算机科学与应用,2017,7(10):960-973.DOI:10.12677/csa.2017.710109BasedonFQnandCyclesCell-BreedingNetworkFQCC(n,k)andItsPropertiesYuanZhao1,HaizhongShi2*CollegeofMathematicsandStatistics,NorthwestNormalUniversity,LanzhouGansuReceived:Oct.4th,2017;accepted:Oct.17th,2017;published:Oct.24th,2017AbstractThefoldedcube-connectedcyclesnetworkFQCC(n)(n1)isaclassicinterconnectionnetwork;itis3regular.Onthebasisofthefoldedcube-connectedcyclesnetworkFQCC(n)(n1)andcell-breedinggraphmodelforinterconnectionnetwork,FQCC(n,k)(n1,kisnotanegativeinteger)isdesignedbyHaizhongShi:eachvertexinthefoldedcube-connectedcyclesnetworkFQCC(n)(n1)isreplacedbythecyclesoflength3,andthevertexineverycycleislocatedontheedgeofthefoldedcube-connectedcyclesconnectedtothevertex,thenwecalledthenewnetworkFQCC(n,1);insimilarwayeachvertexinthefoldedcube-connectedcyclesnetworkFQCC(n,1)(n1)isre-placedbythecyclesoflength3,thenwecalledthenewnetworkFQCC(n,2),loopingexecutiontheabovemethodktimes,andthengetthenewnetwork—FQCC(n,k)(n1,kisnotanegativeinteger).ThenetworkFQCC(n,k)keepssmallorfixeddegree(is3)ofFQCC(n),andhasbetterex-tendabilitythanFQCC(n).Furthermoreproposedaconjecture:FQCC(n,k)isHamiltonian.YuanZhaoproofsthatFQCC(2,k)isplanarandHamiltonian,andthatFQCC(n,k)(k1)isnotvertex-transitive.KeywordsTheFoldedCube-ConnectedCycles,FQCC(n,k),PlanarGraph,HamiltonGraph,Hamilton-ConnectedGraph,Vertex-Transitive基于FQn和圈的细胞分裂生长网络FQCC(n,k)及其性质赵媛1，师海忠2*西北师范大学数学与统计学院，甘肃兰州*通讯作者。赵媛，师海忠DOI:10.12677/csa.2017.710109961计算机科学与应用收稿日期：2017年10月4日；录用日期：2017年10月17日；发布日期：2017年10月24日摘要折叠立方体连通圈网络FQCC(n)(n1)是一类典型的互连网络，它是3正则的。师海忠根据折叠立方体连通圈网络FQCC(n)(n1)和细胞分裂生长图模型设计出了一种新的互连网络——FQCC(n,k)(n1，k是非负整数)：用三长的圈代替FQCC(n)的每个顶点且圈中每个顶点恰位于折叠立方体连通圈网络FQCC(n)(n1)中与该顶点关联的一条边上，得到新的网络FQCC(n,1)；再类似的用三长的圈代替FQCC(n,1)的每个顶点得FQCC(n,2)，循环执行上述方法k次得到的新网络称为FQCC(n,k)(n1，k是非负整数)。该网络FQCC(n,k)在保持了FQCC(n)的小的固定的度(为3)的特性外，还有比FQCC(n)更好的扩展性。进而提出了猜想：FQCC(n,k)是Hamilton图。赵媛证明了FQCC(2,k)是平面图和Hamilton图，还证明了FQCC(n,k)(k1)不是点可迁的。关键词折叠立方体连通圈网络，FQCC(n,k)，平面图，Hamilton图，Hamilton连通图，点可迁的Copyright©2017byauthorsandHansPublishersInc.ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY).引言互连网络是超级计算机的重要组成部分。网络遵循八个原则：小的固定顶点度；小通信传输延迟；简单的路由算法；均匀性或对称性；高容错性；可扩性；可嵌入性；有效的布图算法。大规模集成电路技术的出现和现代通信技术的飞速发展要求人们设计出多核的互连网络，对这种网络来讲网络的平面性是一项很重要的指标。互连网络的基本拓扑结构是连通图G(V,E)。其中V是处理器的集合，E是网络通信链路的集合[1][2]。许多学者设计出了多种互连网络，例如：折叠Petersen立方体、折叠立方体、正则图连通圈网络(折叠立方体连通圈网络，立方体连通圈网络等)、细胞分裂生长图模型、层次环群论模型等并给出了它们的部分性质[3]-[17]。这些互连网络都有许多优点，也各自存在一些缺点。比如折叠立方体，它的度(n+1)随着规模(2n)的增大而增大。折叠立方体连通圈具有优点——小的固定的度(都为3)，但它的扩展性较差。在这篇文章中，根据文献[8]和[10]中提出的设计互连网络的新思想，师海忠设计出了新的互连网络()(),2,0FQCCnknk≥≥。除了保持折叠立方体连通圈()FQCCn的优点——小的固定的度(为3)外，当固定n之后，它有较好的可扩展性，即规模可随着k的增大而增大。特别是赵媛证明了()2,FQCCk是个平面图和Hamilton图，还证明了()(),2FQCCnkk≥不是点可迁的。本文其余结构是：第2节，基本概念；第3节，新互连网络k及其性质；第4节，结束语。2.基本概念定义1[14]：令011nxxxx−=是一个n比特二元串，我们用()jx来定义比特jx。令()ixy=当x和y仅在第i个位置比特不同。OpenAccess赵媛，师海忠DOI:10.12677/csa.2017.710109962计算机科学与应用定义2：如果两个顶点011nxxxx−=和011nyyyy−=有()10,1,,1iiyxin=−=−，那么我们就记做yx=。我们说x和x是互补的。定义3：n维折叠立方体连通圈()FQCCn定义为一个无向图，它有()12nn+⋅个顶点，记做(),xl，其中011nxxxx−=是一个n比特二元串，l是0到n的一个正整数，两个顶点(),xl，(),yl′相连当且仅当(i)xy=且1ll′−=或者(ii)01lln′≤=≤−且()lyx=或者(iii)lln′==且yx=。定义4：我们给出新网络()()2,0FQCCkk≥的严格数学定义，()2,FQCCk的顶点记作()(),1xlk+，其中x是2比特二元串，()1211klklll++=，il是0到2的整数。两个顶点()(),1xlk+和()(),1ylk′+相连当且仅当(i)()()0,1jyxj==且()11iilljik′==≤≤+；或者(ii)yx=且()211iillik′==≤≤+；或者(iii)xy=且kkll′≠，1kkll+≠，1kkll+′′≠，()iillik′=≠；或者(iv)xy=且()(),xlk，()()()(),2,1ylkVFQCCk′∈−且()()()()()()(),,,2,1xlkylkEFQCCk′∈−且11kkkkllll++′′===；或者(v)xy=且11kkll++′≠，()1iillik′=≤≤。如图2、图3。定义5[2]：若一个图具有这样的一个图形，它的边仅在端点处相交，则该图称为平面图。定义6：G的Hamilton圈是指包含G的每个顶点的圈。定义7：一个图若包含Hamilton圈，则称这个图是Hamilton图。定义8[15]：若一个图中任意两个顶点之间都有一条Hamilton路，则称这个图为Hamilton连通图。定义9[1]：如果G是点可迁的，那么对G的每对顶点x和y，存在()AutGθ∈，使得()yxθ=。3.新互连网络FQCC(n,k)及其性质3.1.FQCC(n,k)及其基本性质在这一节中师海忠设计出了新互连网络(),FQCCnk：用三长的圈代替()FQCCn的每个顶点且圈中每个顶点恰位于折叠立方体连通圈网络()()2FQCCnn≥中与该顶点关联的一条边上，得到新的网络(),1FQCCn；再类似的用三长的圈代替(),1FQCCn的每个顶点得(),2FQCCn，循环执行上述方法k次得到的新网络称为()(),2,0FQCCnknk≥≥，注意(),0FQCCn即为()FQCCn。新互连网络()(),2,0FQCCnknk≥≥有()123nkn+个顶点，()11123nkn−++条边，且它的度为3。(),FQCCnk比()FQCCn有更好的扩展性，即当固定n之后，规模(()123nkn+)随着k的增大而增大。特别是()2,FQCCk有较好的性质(见3.2节)。3.2.FQCC(2,k)及其性质在这一节中，赵媛讨论了()2,FQCCk的平面性、Hamilton性、点可迁性。定理1：()()2,0FQCCkk≥是平面图。证明：显然2FQ是平面图，如图1。所以()2FQCC即()2,0FQCC是平面图，如图2。那么()2,FQCCk也是平面图，如图3。定理2：()2,FQCCk是Hamilton图。证明：当0k=时，我们可以在()2,0FQCC(也就是()2FQCC)中找到一个Hamilton圈：(00,0)-(00,2)-(11,2)-(11,0)-(11,1)-(10,1)-(10,0)-(10,2)-(01,2)-(01,0)-(01,1)-(00,1)-(00,0)。显然()2FQCC是Hamilton图。当1k=时，()2,0FQCC中的顶点()1,xl变成了()11,xll。我们可以找到路P1(00,00),(00,01),(00,21),(00,20),(00,22)来代替边((00,0),(00,2))；路P2(00,22),(11,22)来代替边((00,2),(11,2))；路P3(11,22),(11,20),(11,21),(11,01),(11,00)来代替边((11,2),(11,0))；路P4(11,00),(11,02),(11,12),(11,10),(11,11)来代替边((11,0),(11,1))；路P5(11,11),(10,11)来代替边((11,1),(10,1))；路P6(10,11),(10,10),(10,