局部纽立方体网络的相关性质分析

《局部纽立方体网络的相关性质分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、(Ⅱ)ThefaultdiameterandthewidediameterofLTQnarcthesame，whichis咖删圳诹，=‰蝇喇n----4．’5；KEYWORDS：Locallytwistedcubes；faultdiameter；widediameter；pathIII—目录摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯IABSTRACT⋯⋯．⋯．．．．．．．．．．．．．．．．．⋯．．⋯．⋯．．⋯⋯．．．．．．．．．⋯．⋯．．．J】目录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯IV1绪论⋯⋯

2、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11．2网络容错性的研究概况⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．32局部纽立方体网络的基本概念和研究概况⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．1局部纽立方体网络的基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．2局部纽立方体网络的研究概况⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯82．3本文主要结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．93局部纽立方体网络LTQ，。中路的嵌入⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．103．1三个引理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．103．2故

3、障LTQ，。中路的嵌入⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．164LTQn的容错直径和宽直径⋯⋯⋯⋯⋯⋯_⋯⋯⋯⋯⋯⋯⋯⋯204．1LTQ,n中最短路的一些性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯204．2LTQn的容错直径和宽直径⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯22攻读学位期间取得的研究成果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．44浙江师范大学学位论文独创性声明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．45学位论文使用授权声明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．45学位论文诚信承诺书⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

4、⋯⋯⋯⋯⋯⋯⋯⋯．46IV一●1．1基本概念1绪论本节定义一些图论的基本术语与符号．把一个有序的二元组(y(G)，E(G))称为一个图G，其中v(a)是G的顶点集合，v(a)中的元素叫做图G的顶点或者点；E(G)∈v(a)×v(a)称为G的边集，E(G)中的元素叫做图G的边．通常地，用y和E分别表示一个图G的项点集合和边集合，用IGl和IIG0分别表示G的顶点数和边数。对于图G的顶点u和"，若e=(u，u)∈E，则称11和u在G中相邻，或u和u互为邻点．这时又称t‘和u是边e的两个端点．一条边的两个端点也可能是相同的，

5、这样的边称为环．没有重边和环的图叫做简单图．本文仅考虑顶点数有限的简单图．图G中连接顶点u和u且长度为k的链，记为伽．链，定义为一个点边交替序列W=(t‘=110elvle2⋯e七％=11)，其中ei=忱一1忱∈E(G)，1≤i≤k．若链Ⅳ上的边el，e2⋯．，e七互不相同，则称彬为伽．迹．又若链Ⅳ上的点Vo，u1，⋯，讥互不相同，则称Ⅳ为uu．路，用P或P(u，t，)或P=(t‘，P(u，s)，s，￡，P(t，11)，u)表示，其中P(11，s)和P(t，u)分别表示P(u，移)中u到s的子路和t到u的子路．两端点相

6、同且长度至少为3的路称为圈．路(圈)上的边数为路(圈)的长度．把图G中长度为尼的圈叫做k一圈．k为偶(奇)数时，k．圈称为偶(奇)圈．包含G中每个项点的圈称为Hamilton圈．若图G包含Hamilton圈，则称G为Hamilton图．包含G中每个顶点的路称为Hamilton路．若图G中任意两个不同顶点间都有一条Hamilton路，则称G为Hamilton连通的．设t‘和u是图G的任意两个不同顶点．若对任意整数c(dG(11，移)≤z冬Iy(G)l一1)，G中都有长为Z的ut，．路。则称图G是泛连通的．用F表示图G的任

7、意故障集，记为FCv(a)UE(G)．对图G的任意故障点(或边)集F，若当IFI≤k时，图G—F仍是Hamilton的，则称图G是七容错Hamilton的．对任何一点都至少与两条非故障边相连及故障边集FCE(G)，若当IFl≤2n一5时，图G—F仍是Hamilton的，则称图G是七限制容错Hamilton的．类似地，可有七容错Hamilton连通，七限制容错Hamilton连通．1绪论在G中连接两顶点U和u的所有路中，长度最短的路，称为最短UV一路，又称为G中从u到t?的距离，记为dc(u，”)．G中任何两顶点之间的最

8、大距离称为G的直径，记为D(G)，即，D(G)=max{dc(札，v)lu，"∈y(G))．若对于图G中的任意两个顶点U和u，G中都存在一条UU一路，则称G为连通图，否则称为非连通图．不含圈的连通图称为树．如果存在非空子集SCy(G)，使得G—S非连通，那么S称为G的点分离集．G的所有点分离集中最小点数称为G的连通度，记为K(G)