扩展k元n立方体的1-好邻诊断度和交换交叉立方体的2-限制连通度
发布时间：2020-09-27 13:52
许多多重处理器系统用互连网络(简称网络)作为它的基础拓扑并且网络通常用图表示,其中顶点表示处理器,边表示处理器之间的通信链路.我们交替使用图和网络.连通度是衡量互连网络容错性的重要参数.由于一个大规模的计算机系统是由成千上万个计算机处理器组成,因此在这种复杂的操作环境下会有更多的处理器可能发生故障.为了更好的研究系统的容错性,1996年,J.Fabreg和M.A.Fiol提出了互联网络的k-限制连通度.诊断度是度量多重处理器系统故障诊断能力的重要参数.然而,在系统中一些处理器可能是故障的.所以,为了保证计算机系统的可靠性,系统中的故障处理器应该被诊断出来并被非故障处理器替换.识别故障处理器的过程被称为系统诊断.诊断度被定义为系统能够被诊断出的故障处理器的最大数目.传统的诊断度允许点的邻点全为故障点.但是在大型多重处理器系统中这种故障出现的概率极小.因此,2015年,Lai等提出了系统的条件诊断度,它限制系统中任意一个处理器至少与一个非故障处理器相邻.2012年,Peng等提出了系统的g-好邻诊断度,它限制每个非故障顶点都至少有9个非故障点与之相邻.并且研究了超立方体在PMC模型下的g-好邻诊断度.为了测量多重处理器系统的诊断度,很多诊断模型已经被提出.尤其是PMC模型和MM*模型,这两个模型被广泛使用.在PMC模型和MM*模型下已经有许多的研究成果.下面是本文的主要内容:第一章:简单介绍一下本文的研究背景和研究现状,给出图论中的一些基本概念,扩展k元n立方体AQn,k和交换交叉立方体ECQ(s,t)的定义,以及两个著名的故障诊断模型(PMC模型和MM*模型).第二章:证明了扩展k元n立方体在PMC模型和MM*模型下的1-好邻诊断度是8n-9(n≥ 4,k≥ 4).第三章:证明了交换交叉立方体ECQ(s,t)的2-限制连通度是3s-2(2 ≤ s ≤第四章:工作总结.
【学位单位】：河南师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：
第一章绪论｝．逡逑Ｇ邋Ｖ（Ｇ）邋－邋Ｆ，邋ｒ；邋Ｇ邋兄则邋ａ（ｕ？）邋＝邋１；逡逑ｅ邋Ｖ（Ｇ）邋－邋Ｆ，则邋＝邋０．逡逑）中任意两个不同的顶点子集巧和ｆ２，若（Ｔ＾）邋ｎ，记（N铣В玻┦强汕侄裕簦幔ǎ
本文编号：2827961
【学位单位】：河南师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【部分图文】：
第一章绪论｝．逡逑Ｇ邋Ｖ（Ｇ）邋－邋Ｆ，邋ｒ；邋Ｇ邋兄则邋ａ（ｕ？）邋＝邋１；逡逑ｅ邋Ｖ（Ｇ）邋－邋Ｆ，则邋＝邋０．逡逑）中任意两个不同的顶点子集巧和ｆ２，若（Ｔ＾）邋ｎ，记（N铣В玻┦强汕侄裕簦幔ǎ
本文编号：2827961
本文链接：https://www.wllwen.com/kejilunwen/yysx/2827961.html
