互连网络圈嵌入的研究

《互连网络圈嵌入的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要互连网络通常用一个图G=(V，E)来表示，其中G的顶点表示处理器，G的边表示处理器之间的通信连线。由于实际的互连网络拓扑结构中的处理器很多，因此提出了在更复杂的互连网络拓扑结构中模拟路和圈的算法，这为图的嵌入问题。超立方体和星图是两个非常通用的互连网络拓扑结构，在超立方体和星图中嵌入路和圈已引起很多学者的研究。本文主要研究圈嵌入问题，所指的圈嵌入是指，在给定的网络拓扑结构中找到所有可能长度的圈。互连网络的可靠性和容错性是评估互连网络性能的重要参数。在实际的网络结构中，有可能会发生故障点和边，因此考虑故障网络十分必要。它对应于

2、圈嵌入问题中，在故障点和(或)边发生故障的条件下，剩余的子网络中仍然能嵌入所有可能长度的圈。本文首先研究星图中的条件故障边下的圈嵌入问题，其中的条件故障是指每个顶点都至少与两条无故障边相连。其次研究的是超立方体中强条件故障下的圈嵌入问题，其中的强条件故障是指每个顶点至少与三个无故障点和三条无故障边相连。同时，由于星图和超立方体是Cayley图，本文还证明了环的递归立方体网络RCR(k，，，j『)是一类Caylvy图。全文共分为以下几个部分：第一章为绪论，主要说明研究工作的背景。第二章介绍图和网络的基本概念、图的对称的相关定义、星

3、图最、超立方体Q和环的递归立方体网络RCR(k，，．，／)的定义、嵌入的相关定义以及星图和超立方体网络中有关嵌入问题已经取得的一些结果。第三章研究在条件故障边下星图墨(刀≥4)中的圈嵌入，并得到一个结果：星图最(月≥4)中存在所有偶数长度从6到刀!的无故障圈，当故障边的数目不超过3刀一10，并且每个顶点至少与两条无故障的边相关联时。第四章研究了在强条件故障下超立方体Q(刀≥5)中圈嵌入，并得到一个结果：当故障点和故障边的数目不超过2刀一5(刀≥5)时，超立方体中的每条无故障边都在偶数长度从4到2。-2IEI的圈上。第五章证明了环

4、的递归立方体网络RCR(k，，．，j『)是一类Cayley图。第六章对本文的主要工作进行了总结，并且提出了有待进一步研究的问题。关键词：互连网络：圈嵌入；条件故障；星图；超立方体IlABSTRACTABSTRACThterconnectionnetworkisalwaysrepresentedbyagarphG=(y，E)，wheretheverticessetofGrepresentsprocessorsandtheedgessetofGrepresentsthelinksbetweenprocessors．Inthereal

5、interconnectionnetwork，thenumberoftheprocessorsishuge，SOpeopleproposesimulatingthealgorithmsofpathsandcyclesinmorecomplicatedinterconnectionnetworks．Thatistheembeddingproblem．Hypercubeandstargrapharetwopopularinterconnectionnetworks．Thestudyofembeddingpathsandcyclesi

6、nhypercubeandstargraphhasattractmanyinterests．Inthispaper,wemainlystudycycleembeddingproblems，thatisfindingallpossiblelengthsofcyclesininterconnetionnetworks．Thereliabilityandfault-tolerancealetwoimportantparametersinevaluatingtheperformanceofnetworks．Intherealnetwor

7、k,theremayexistfaultyverticesandedges，SOitisimportanttoconsiderfaultynetworks．Thatmean5inthecycleembeddingproblems，theremainingnetworkcanembeddingallpossiblelengthsofcyclesundertheconditionthatthereexistsfaultynodesand(00faultyedges．Inthispaper,atfirst，weconsiderthec

8、ycleembeddingproblemintheconditionalfaultyedgesinstargraph，wheretheconditionalfaultymeanseachvertexisincidentwithatleasttwofault-fr