论文部分内容阅读
随着并行计算机互联网络规模的不断扩大,互联网络中处理器或处理器链路发生故障的情形是不可避免的,这就要求网络具有一定的容错性.网络容错性是指当网络中若干结点和(或)连线发生故障时网络仍能继续有效的工作,因此计算机互联网络的容错性研究变得越来越重要.容错泛圈,容错直径,容错哈密顿性等都是度量网络容错性的参数.本文主要研究加强超立方体Enhanced Hypercube的点边容错性质,讨论容错加强超立方体中路和圈的嵌入情况.论文主要分为四章,研究加强超立方体的某些容错性质:条件情况下和标准情况下的边容错性质、点容错性质、超哈密尔顿脆弱性质等.第一章主要介绍图相关的基本概念,几个著名的互联网络以及泛连通性,哈密尔顿连通性,容错泛圈性,容错哈密尔顿性,强哈密尔顿性限制连通度的定义以及目前已经取得的一些结果.第二章主要研究了加强超立方体的条件边容错奇偶泛圈的嵌入问题以及边容错超哈密尔顿脆弱问题,得到了以下两个结论:(1)给出了加强超立方体Qn,k的条件边容错泛圈性,证明了加强超立方体Qn,k(n≥3)有至多(2n-3)条故障边,其中每一个点至少与两条非故障边相连,且n和k有相同(不同)的奇偶性,那么在Qn,k中存在偶长为4到2n的的容错圈(存在偶长为4到2n的的容错圈以及奇长为n-k+2到2n-1的的容错圈).这就将折叠超立方体的条件边容错泛圈性进行了推广.(2)证明了加强超立方体Qn,k的边容错超哈密顿脆弱性:加强超立方体Qn,k(1≤k≤n-1),当n (≥3)和k (1≤k≤n-1)有相同的奇偶性时,是(n-2)-边容错超哈密顿脆弱的.第三章主要研究了加强超立方体的点容错泛圈性以及点容错最长路的嵌入问题,进一步地,研究了其点边容错路和圈的嵌入,得到了以下几个结果:(1)2-点容错泛圈嵌入加强超立方体和(n2)-点容错最长圈嵌入加强超立方体;(2)点边容错情况下最长路嵌入和容错圈嵌入加强超立方体.第四章我们对全文的工作进行了总结,并且提出了一些仍需要进一步研究的问题.