边故障Torus网络的哈密尔顿路

来源 :太原科技大学 | 被引量 : 0次 | 上传用户:fdiskhotmail
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着当前信息量的日益增加以及科学技术研究的不断深入,人们对计算机的计算和存储的性能的要求越来越高,所以,大规模并行计算机系统随之产生。互连网络是大规模计算机系统内部处理器之间的连接方式,可以用无向连通图来表示。图中的顶点代表系统中的处理器,边代表系统中处理器之间的连线。在大规模并行计算机系统中,互连网络对整个并行计算机系统的稳定运转起着重要的甚至是决定性的作用。随着计算机系统规模的不断扩大,各个部件和组件产生故障的概率越来越大,因此人们对互连网络的容错性和可靠性的要求越来越高。为使故障互连网络保持良好的信息传递能力,研究含有故障边的互连网络的哈密尔顿圈和路的存在问题是有意义的。Torus网络是目前应用最广的分布式计算机系统互连网络。其包含很多优点,如网络结构简单;具备正则性、对称性、可扩展性、路径多样性等特性。当前很多已投入商业应用的并行和分布式系统都是基于Torus网络来构成其连接模式。目前,针对Torus网络,关于容错哈密尔顿性和哈密尔顿连通性的研究已取得了一定的成果。学者们提出了各种各样的故障假设,其中最常见的一种假设是故障的发生不会使网络产生1度顶点。然而网络中产生1度顶点这种故障情况是存在的,因此对存在1度点的故障网络进行研究是有意义的。1度点的存在使得网络整体不具有哈密尔顿性和哈密尔顿连通性,但是对于特别的点对之间,仍然可能存在哈密尔顿路。本文以Torus网为研究对象,对网络存在1度点的情形下的哈密尔顿路进行刻画。本文首先对二维Torus网络进行研究。分不同情形,利用特别的剖分方法,研究边故障二维环网在两种情况下的哈密尔顿路存在问题:(1)包含一个1度点;(2)包含两个1度点,证明了三个相关定理。其次,本文扩展了上述结论,在二维Torus网络容错哈密尔顿路存在的基础上,利用数学归纳法,将相关结果推广到n维边故障Torus网络上,并确定网络在当前条件下保持哈密尔顿连通性所允许的故障数目新上界。设F是Torus(k1,k2,…,kn)中的故障边集,其中k,k2,…,kn是偶数且n ≥ 2,得到的主要结论如下:(1)假设kk1,k2,…,kn≥ 4,|F| ≤ 4n-4,u为Torus(k1,k2,…,kn)-F的唯一 1 度顶点。对任意的顶点v,若u、v奇偶性不同且(u,v)?(Torus(k1,k2,…,kn)-F),则u与v之间有哈密尔顿路。(2)若k1,k2,…,kn≥ 6,|F| ≤ 6n-7,u为Torus(k1,((k1,k2,…,kn)-F的唯一 1 度顶点,则点u至少有2n-2个邻点(无故障Torus(k1,k2,…,kn)中的邻点)与u之间有哈密尔顿路。(3)若k1,k2,…,kn≥ 4,|F| ≤ 6n-6,u,v是Torus(k1,k2,…,kn)-F中两个 1 度点且(u,v)∈F,则u与v之间有哈密尔顿路。
其他文献
在以“绿色环保,节能减排”为理念、坚持可持续发展战略的背景下,铁基非晶纳米晶合金用卓越的性能(包括高Bs、高ρ、低Hc等)作为保障,以显著的节能环保优势作为基础,在电器设备制造业中有着非常辽阔的市场。其中FINEMET系合金成本低廉,综合软磁性能较传统非晶合金更为优异,已经实现了工业化生产。但是由于其非晶形成能力较弱,热稳定性较差,难以满足高温应用环境的需求。因此,如何改善FINEMET合金的非晶
在工业应用中,诸如矿井主通风系统、火碱降温系统等通常采用两个或者多个相同子系统组成的冷贮备冗余结构,对其进行定期切换式运行及维护,此策略可称为是离线切换式维修。系统的寿命特性直接决定了其运行性能和切换需求。同时,系统的各部件维修效果也直接影响系统的维修时间、成本及后续的运行性能和最优切换周期。本文针对一用一备或多用多备的冷贮备周期切换式可修系统,研究了不同故障模式下切换维修决策问题。主要研究内容包
起重机械作为一种大吨位运输设备,能够代替人工及人工难以完成的作业。为了保障现代化建设的高效进行和公民的生命财产安全,设计人员有必要对于起重机械安全性能的进行研究分析,寻找优化的途径。首先,在铸造起重机中,就单工作方式制动劣势工况,相较于联合制动、复合制动作理论比较;接着,考虑到岸边起重机的阵风是造成事故的主要原因之一,本文按盘式制动器的流体散热优势,对制动盘在不同工况及机构下进行热机耦合分析。首先
海底图像配准对于深海资源的勘探和研究具有重要的意义,是近年来的研究热点和重点。海底图像特征点配准的主要步骤为:特征点提取,描述特征点和匹配特征点。但由于海底图像受到水中悬浮颗粒的散射以及人造光源的影响,导致深海海底图像质量下降严重,且海底地貌纹理集中于某一区域,相似纹理居多,得到精度高且分布均匀的特征点匹配对成为当下研究的难点。幸运的是,机器人配置导航系统,导航系统拍摄图像的同时记录地理位置坐标,
高等教育领域的信息化建设持续推进,要求教学运行等业务数据的价值充分体现。研究基于教育数据分析的课程评价、本科生课程学习的个性化管理问题,具有理论意义和应用价值。1.一流课程建设,关系一流专业建设和一流本科教育成效。课程评价结果可用来指导课程建设。以太原科技大学为背景高校,在分析课程评价需求基础上,研究了课程评价模型;通过对教学管理职能部门的走访调研,获取了涵盖教学队伍、教学内容、教学资源等维度的精
非正交多址(Non-orthogonal Multiple Access,NOMA)技术能够满足无线通信信号覆盖面广以及传输速率高的要求,并与中继结合而提高用户服务质量。其中继的转发协议可以有效改善系统中断性能,为此,本文探索了用户协作通信NOMA系统和中继转发协议相结合来提高弱用户的中断性能以及对系统吞吐量的分析。本论文主要工作如下:首先,本文提出在用户协作NOMA系统下的混合解码放大转发(Hy
本文旨在改善铝铜合金的综合力学性能,实验选择Al-3%Cu合金作为研究对象,采用一种扩散连接+液压成形结合的复合工艺,在Gleeble-3800热模拟机上,将轧制态A1-3%Cu合金(CR)和退火态Al-3%Cu合金(AR)两种交替叠层的试样进行扩散连接,实现预焊合,然后采用液压工艺将预焊合的试样压缩变形至目标厚度,制备出非均匀层状结构Al-3%Cu合金。通过对不同热变形加工的试样进行研究,得出以
实际工程和科学领域中存在一些优化问题,其进行一次性能评估非常耗时。进化优化算法是求解最优化问题的最有效的手段之一,然而,由于进化算法在获得全局最优解之前需要进行大量的适应值评价,导致其不能直接应用于计算昂贵的优化问题上。近年来,代理模型辅助的进化优化算法受到了越来越多的关注,而其中采样策略是影响模型是否能够辅助进化优化算法在计算资源有限的情况下找到最优解的重要因素之一。本文使用代理模型近似计算费时
互连网络是大规模计算机系统内部处理器之间的连接方式,它可以用无向连通图来表示。图中的顶点代表系统中的处理器,边代表系统中处理器之间的连线。k元n立方体网络由于自身优良的拓扑性质,如易于实现、低延迟,已成为目前重要的互连网络之一。在对互连网络的研究中,网络是否具有哈密尔顿性和不交路覆盖性是十分重要的研究课题。随着多处理器系统规模的不断扩大,处理器以及处理器之间线路出现故障的可能性越来越大。因此,研究
随着我国高端装备制造业的快速发展,对高温环境下使用的耐热不锈钢需求的数量日益提高。目前我国对于耐热不锈钢的使用性能要求越来越高,尤其对于较高温度下的氧化性能要求更加严格,因为高温下良好的抗氧化性能是不锈钢在使用过程中保证寿命和安全的关键因素。通过研究耐热不锈钢的高温氧化性能,来进一步提高耐热不锈钢的性能,拓展其应用领域,为以后提高氧化性能奠定基础。本文所用的实验材料是改进后的国产奥氏体不锈钢309