环面网络关于圈嵌入的边容错性

来源 :太原科技大学 | 被引量 : 0次 | 上传用户:wushiguo208
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
计算机或通信系统中各个元件之间不同的连接方式被称为该系统的互连网络。人们一般将互连网络看作一个图,图中顶点代表网络中的处理器,边代表处理器之间的通信线路。随着大型网络中处理器的不断增加,故障的出现也变得越来越频繁,保证信息仍然能够在故障系统的不同处理器之间顺利传递的容错性便成为了一个非常关键的问题。因此,研究新的故障模式对设计互连网络拓扑以便容纳更多的故障通信单元是十分必要的。在网络拓扑中,圈作为结构最基础的类别之一,它的可嵌入性对解决一些优化问题是至关重要的,因为它代表了许多并行算法的数据流结构。本文针对两类特殊的环面网络,研究其边容错性与圈嵌入问题。对于二维环面网络,主要研究了边容错和最长圈嵌入问题。并得到结果:在具有至多4条故障边的二维环面网络Torus(m,n)(其中m,n≥5是整数)中,如果满足两个容错条件(1)任意一个顶点的度至少是2,与(2)不存在禁止4圈,那么它是哈密尔顿的。对于二元n维环面网络(即n维超立方体,记为Qn,其中整数n≥2),考虑了边容错和偶圈嵌入问题。并得到结果:在具有至多3n-8条故障边的Qn(n≥5是整数)中,如果满足两个容错条件(1)任意一个顶点的度至少是2,与(2)不存在禁止4圈,那么Qn中存在长度从4到|V(Qn)| 的无故障偶圈。此外,对于n维超立方体的容错哈密尔顿圈嵌入方面,将n维超立方网络保持哈密尔顿性所允许的故障边数从3n-8提升到3n-7。证明了具有至多3n-7条故障边的n维超立方体Qn(n≥6是整数),在满足两个容错条件(1)任意一个顶点的度至少是2,与(2)不存在禁止4圈和禁止6圈下,仍然是哈密尔顿的。
其他文献
关于SiHnRm(n=0,2,m=2;R=F,Cl)分子的研究可以追溯到1598年,由于人们希望在半导体材料方面取得突破性的进展,开始对含Si的一系列化合物进行物理和化学方面的深入研究。而对该类
决策是人类的日常生活中的最常见的行为,我们每天都面临着不同规模的决策问题。并且,在生活中,许多信息都是不精确的、不确定的和模糊的。因此,不确定性决策问题是我们生活中
C*代数的理论和应用在算子代数、群表示、拓扑、动力系统等方面都有很多的关系.自1993年,Elliott开始利用K理论对C*代数进行了分类.近年来对C*代数的分类问题不断加深.本文主
本文的主要工作是求解带秩约束的二次半定规划(rank-QSDP)问题。此问题因秩约束的存在,故是一个非凸的问题。本文的求解思路是首先把秩约束罚到目标函数上,使其变为一个最小
光子具有高速传播的能力,外部环境对它的传播过程作用和干扰很小,正因为光子的这一特性,将它用来做量子信息的载体是可靠的。而原子则是理想的信息记忆单元,通过光与原子相互
在自然界中存在大量的碳元素,含碳化合物不仅是化石能源的主要成分,而且还是大气中温室气体的主要组成成分,此外,他们还广泛存在于星际空间中。碳化物分子的结构及其光谱特性
氧是生命活动的重要物质,环境低氧(hypoxia)一般会造成机体组织供氧不足,严重者可导致细胞凋亡(apoptosis)、组织损伤,甚至机体死亡。地下鼠(subterranean rodents)终生营地
密度函数核估计是日常生活中应用比较广泛的一种参数估计方法。在Rosenblatt和Parzen先后提出并完善此类密度估计后,众多国内外的数理统计学家研究了此类方法的各种性质。其
高温是制约水稻生长和产量的重要因素,发掘调控水稻耐热元件和培育耐热水稻品种是保证水稻稳产的重要手段。B-box锌指蛋白(BBX)是一类重要的转录因子,对植物响应非生物胁迫具
脑是自然界中最复杂的网络,脑中数以亿计的神经元之间不同的连接模式不仅编码了动物的行为,而且控制着躯体的功能输出。因此,与特定行为和功能相对应的神经元网络信息处理机