互连网络的容错嵌入

出版时间：2012-4  出版社：科学出版社  作者：王世英，李晶，李玉星　著  页数：167  

内容概要

　　《互连网络的容错嵌入》(作者王世英、李晶、杨玉星)对于互连网络的容错嵌入问题提供了一个统一的理论框架。内容包括图与互连网络的概述；对网络容错泛连通性、容错泛圈性、条件容错泛连通性、条件容错泛圈性、指定哈密尔顿连通性和指定哈密尔顿性的研究；对网络匹配障碍问题和多对多不交路覆盖问题的研究。书中许多内容和方法是作者的研究成果。还提出一些问题供有兴趣的读者进一步研究。
　　《互连网络的容错嵌入》可供高等院校计算机和应用数学、网络通信等专业教师、研究生以及相关领域研究人员阅读参考。

作者简介

王世革 ，男，山西省晋中市人，理学博士，山西大学教授，山西大学数学和应用数学研究所副所长，山西大学数学科学学院基础数学博士点的方向带头人和博士研究生导师。山西大学计算机与信息技术学院系统工程博士点的方向带头人和博士研究生导师。美国《数学评论》评论员，中国运筹学会理事，山西省数学学会常务理事，主要从事离散数学和理论计算机科学方面的研究工作。出版专著一部，在国内外学术刊物上发表学术论文132篇。

书籍目录

总序
序
前言
主要符号表
第1章 绪论
　1．1 图与互连网络
　1．1．1 并行计算机互连网络
　1．1．2 图论的一些基本概念和符号
　1．1．3 互连网络设计原则
　1．1．4 网络嵌入
　1．1．5 网络容错性
　1．2 k-元n-立方网络
　1．2．1 k-元n-立方的提出
　1．2．2 k-元n-立方的性质
　1．3 研究进展和本书的主要内容
第2章 容错泛连通性
　2．1 相关概念和结果
　2．2 二维环面网络的容错泛连通性
　2．3 k-元n-立方的容错泛连通性
　2．4 一些说明
第3章 容错边偶泛圈性
　3．1 相关概念和结果
　3．2 容错奇元n-立方的边偶泛圈性
　3．3 容错偶元n-立方的边偶泛圈性
　3．4 一些说明
第4章 条件容错哈密尔顿交织性
　4．1 准备工作
　4．2 条件容错k-元n-立方的哈密尔顿交织性
　4．3 条件容错k-元n-立方的哈密尔顿交织性
　4．4 本章小结
第5章 条件容错泛圈性
　5．1 相关概念和结果
　5．2 准备工作
　5．3 (4n-5)一条件容错泛圈性
　5．4 最优性说明
第6章 指定哈密尔顿连通性
　6．1 相关概念和结果
　6．2 准备工作
　6．3 (2n-2)一指定哈密尔顿连通性
　6．4 一些说明
第7章 指定哈密尔顿性
　7．1 相关概念和结果
　7．2 奇元n-立方的指定哈密尔顿性
　7．3 偶元n-立方的指定哈密尔顿性
　7．4 一些说明
第8章 匹配排除和条件匹配排除
　8．1 相关概念和结果
　8．2 k-元n-立方的匹配排除
　8．3 本章小结
第9章 多对多n-不交路覆盖
　9．1 相关概念和结果
　9．2 准备工作
　9．3 n-维超立方体的多对多n-不交路覆盖
　9．4 一些说明
参考文献
　　

章节摘录

版权页：   插图：   在本节剩余部分，我们将完成本章的主要定理的证明，根据故障边在Qkn中的分布情况将证明分成下面3个引理。每个引理证明的基本策略都是先将Qkn划分为一些子立方的联合，然后在这些联合中应用上述的一些引理构造它们的哈密尔顿路，最后连接这些路得到Qkn中满足要求的哈密尔顿路。 引理4.3.3设n≥3是一个整数，k≥4是一个偶数。若对于i1=0，1，…，k—1，Fi1均是Q（i1）的条件故障边集，且存在某个j1∈{0，1，…，k—1）使得fj1=4n—9，则Qkn—F有一条（u，v）哈密尔顿路，证明不失一般性，设f0=4n—9。注意，∣F∣=4n—6且∣F0∣≥3。因此，∣F0∣=3且对r=1，2，…，k—1均有，fr=0。 断言1Q（O）中存在一条故障边（x，y）与F0中至多一条边相邻。 反证法。假设Q（0）中的每一条故障边均与F0中至少两条边相邻。选取Q（0）的一条故障边（s，s1）。若在E（Q（0））中存在一条与（s，s1）不相邻的故障边（t，t1），则∣F0∣≥4，矛盾，所以，Q（0）中的每对故障边都是相邻的，注意，Q（0）中没有三角形。于是，Q（0）中的所有故障边均与Q（0）的某个顶点关联。因此，4n—9>dQ（0）（a）—2=2n—4，矛盾。断言1成立。