论文部分内容阅读
互连网络是大规模计算机系统内部处理器之间的连接方式,可以用无向连通图来表示。图中的顶点代表系统中的处理器,边代表系统中处理器之间的连线。交错群图和分裂星图由于自身优良的拓扑性质,已成为目前重要的互连网络。在对互连网络的研究中,构造点不相交的路是一个十分重要的研究课题。点不交路可以通过提供并行通信路径来加速数据传输,避免通信拥塞。采用这种点不相交路由方案增强了对节点故障的鲁棒性、增强了负载平衡能力。随着多处理器系统规模的不断扩大,计算机系统间不断地高速运算,多处理器系统中处理器以及处理器之间线路出现故障的可能性越来越大,同时人们对网络可靠性的要求也越来越高,因此,研究带有故障的网络的不交路覆盖(DPC)是十分必要的。目前,针对交错群图不交路覆盖问题中,关于一对一模式下的容错不交路覆盖性已取得了一定的成果,但是指定多对多模式下的不交路覆盖性还没有得到研究,所以本文研究了交错群图的指定多对多不交路覆盖问题,然后将研究对象扩展到分裂星图,研究了分裂星图的一对一不交路覆盖问题。本文首先对交错群图AGn的不交路覆盖问题进行研究。先考虑了AG5的指定二不交路覆盖性,得到结论:至多具有一个故障点的AG5是指定2-DPC的。然后以此结论作为归纳基础,利用数学归纳法,证明了以下结论:定理1:任意的交错群图AGn,n≥5是指定多对多m-DPC的,对任意m,1≤m≤n-2-f成立,其中f为故障边或故障顶点数。其次,本文还研究了分裂星图Sn2的不交路覆盖性。先给出关于有故障顶点的交错群图的哈密尔顿连通性的两个新结果,然后根据这些结果证明了分裂星图的不交路覆盖性,得到以下结论:定理2:在分裂星图Sn2,n≥3中,任意两个不同顶点u,v之间存在一个一对一的m-不交路覆盖,其中1≤m≤2n-3.