边故障k元n立方体网络的不交路覆盖

发布时间：2018-02-11 13:48

  本文关键词： 互连网络 k元n立方体 容错性 多对多不交路　出处：《太原科技大学》2017年硕士论文　论文类型：学位论文

【摘要】：一个系统的互连网络是指该系统中各处理器之间的不同的连接方式.人们通常将互连网络看作是一个图,图中的顶点可以表示互连网络中的处理器,图中的边可以表示处理器之间的通信线路.一个好的网络,是可以较好的通过它的顶点和边来进行信息与数据的接收和传递的.本文探讨的k元n立方体,具有很多好的拓扑性质,因此被广泛用于目前实际应用中的多处理器系统的互连网络拓扑.多对多不交路覆盖问题是互连网络研究领域一个重要的研究课题,它与互连网络中数据的传递密切相关.设点集S = {s1,s2,…,sm}和T={t1,t2…,tm}是图G中两个包含m个顶点的不相交的集合,若图G中存在m条互不相交的路Pi,i=1,2…,m,使得每个Pi都连接si和ti且满足Ui=1mV(Pi)=V(G),则称P1,P2,…Pm}是图G的一个多对多m-不交路覆盖.若对任意的两个具有m个顶点的集合S和T,图G都存在多对多m-不交路覆盖,则称图G是多对多m-不交路覆盖的.随着科学进步和多处理器系统规模的不断扩大,多处理器系统中处理器以及处理器之间的线路出现故障的可能性也越来越大,因此人们对网络的可靠性的要求也越来越高.对于一个处理器之间的线路出现故障的互连网络,若其还能有效的传递信息和数据,则称该互连网络是具有好的容错性的.为使故障互连网络保持良好的信息传递能力,研究含有故障边的互联网络的多对多不交路覆盖是有意义的.本文主要针对k元n立方体研究了当其含有一定数目的故障边时的多对多不交路覆盖问题.对于k元n立方体Qnk(n≥2,奇数k≥3),证明了当其故障边数最多为2n-4时,Qk-F是二不交路覆盖的;对于k元3立方体Q3k(奇数k≥3),证明了当其故障边数最多为3条时,它仍然具有二不交路覆盖性质,且故障边数已达到上界;对于k元n立方体Qnk(n≥2,偶数k≥4),设F是Qnk的故障边集,证明了当|F|≤2n-m-2时,是m-F-不交路覆盖的,其中1 ≤ m≤2n-2.
[Abstract]:The interconnection network of a system refers to the different ways of connection between the processors in the system. People usually think of the interconnection network as a graph, the vertices in the graph can represent the processors in the interconnection network. The edges in the graph can represent the communication lines between processors. A good network can receive and transfer information and data through its vertices and edges. It has many good topological properties, so it is widely used in the interconnect network topology of multiprocessor systems in practical applications. Many-to-many disjoint coverage problem is an important research topic in the field of interconnection network research. It is closely related to the transmission of data in the interconnection network. The set of points S = {S1 / s2, 鈥，

本文编号：1503202