本书对于互连网络的容错嵌入问题提供了一个统一的理论框架。内括图与互连网络的概述；对网络容错泛连通性、容错泛圈性、条件容错泛连通性、条件容错泛圈性、哈密尔顿连通性和哈密尔顿性的研究；对网络匹配障碍问题和多对多不交路覆盖问题的研究。书中许多内容和方法是作者的研究成果。还提出一些问题供有兴趣的读一步研究。

总序

序

前言

主要符号表

第pan style="font-family:宋体">章绪论

pan style="font-family:宋体">图与互连网络

1pan style="font-family:宋体">并行计算机互连网络

11 2图论的一些基本概念和符号

11 3互连网络设计原则

11 4网络嵌入

11 5网络容错性-

1 2 k元m立方网络

1 2lk元n一立方的提出

1 2 2k元n立方的性质

pan style="font-family:宋体">研展和本书的主要内容

第2章容错泛连通性

2pan style="font-family:宋体">相关概念和结果

22二维环面网络的容错泛连通性

23k元n立方的容错泛连通性

24一些说明

第3章容错边偶泛圈性

3pan style="font-family:宋体">相关概念和结果

32容错奇元m立方的边偶泛圈性

3 3容错偶元n立方的边偶泛圈性

34一些说明

第4章条件容错哈密尔顿交织性

4pan style="font-family:宋体">准备工作

4 2条件容错k元3一立方的哈密尔顿交织性

43条件容错k元n立方的哈密尔顿交织性

4 4本章小结

第5章条件容错泛圈性

5pan style="font-family:宋体">相关概念和结果

5 2准备工作

53(4n一5)一条件容错泛圈性

5 4性说明

第6章哈密尔顿连通性

6 pan style="font-family:宋体">相关概念和结果

62准备工作

6 3(2n一2)一哈密尔顿连通性

64一些说明

第7章哈密尔顿性

7 pan style="font-family:宋体">相关概念和结果

72奇元n立方的哈密尔顿性

73偶元n立方的哈密尔顿性

74一些说明

第8章匹配排除和条件匹配排除

8pan style="font-family:宋体">相关概念和结果

8 2≈元n一立方的匹配排除

83本章小结

第9章多对多m不交路覆盖

9pan style="font-family:宋体">相关概念和结果

92准备工作

9 3 n-维超立方体的多对多n不交路覆盖

94一些说明

参考文献

自从第一台电子计算机问世以来，电子计算机的发展始终遵循着摩尔定律，即集成电路上可容纳的晶体管的数目每隔大概pan style="font-family:宋体">个月就会增加一倍，电子计算机的性能也将提高一倍．然而，制作工艺决定了晶体管的尺有一个极限值，单位面积上可容纳的晶体管数目是有限的．另一方面，随着社会的迅猛发展，各行各业每天都有海量的数据需要处理，这就要求计算机有足够快的处理速度和巨大的存储能力．并行与分布式系统为解决上述矛盾提供了一个途径  并行与分布式系统通常以某种互连网络作为拓扑结构，将众多的处理机及其他硬件设备连接起来，相互配合，并行处理，以加快处理速度，提高运算能力互连网络通常以图为数学模型可以将某个互连网络用图H表示，称为“主图"而欲嵌入H中的互连网络G称为“客图”．若G可以嵌入H中，则可以在H中模拟G的某些行为在众多的互连网络拓扑中，路和圈是最为基础，也最为重要的两种网络拓扑结构在上述两种互连网络中，容易设计出简单而又的路由算法．因此，在设计和选择互连网络时，路和圈的可嵌入性是一个重要的参考因素．  作年来一直从事k元m立方网络中路和圈的嵌入研究工作，查阅了本领域的大部分文献资料，获得了一些有意义的结果因此，为了年来的研究成行整理、修正和归纳，故撰写本书本书的基本结构如下：第pan>章首先介绍并行计算机互连网络的背景，并给出本书将用到的图论领域的术语和记号，然后介绍互连网络的设计原则，着重对图嵌入和网络容错行介绍，最后综述k元m立方网络的结构、性质以及相关的研展．第2—7章对％一元n_立方中路和圈的嵌入问题，即k元n．立方网络的各种类哈密尔顿行了研究．第2章和第3章分别研究了随机容错假设下二维环面网络，k元n．立方网络的泛连通性和k元n．立方网络的边偶泛圈性，解决了国外同行提出的一些问题．第4章和第5章分别讨论了条件容错假设下k元m立方网络的哈密尔顿交织性和泛圈性总地来说，在有故障假设的情况下研究路和圈嵌入问题可统一视为“规避嵌入问题”．另一方面，在设计网络的路由算法时，有时需要路径通过某些边，这引起“嵌入问题”的研究．第6章和第7章分别讨论了k元n．立方网络的哈密尔顿连通性和哈密尔顿性有时候，嵌入问题也可以从以下角度考虑：当主图中故障数超过多少时，在该图中一定不能嵌入某个客图?第8章研究了k元n_立方网络的匹配排除和条件匹配问题，给出了该网络中一定不能够嵌入一个匹配的故障边数的上界第9章讨论了在某些限制条件下的一种特殊的k元n一立方网络——超立方网络的多对多n不交路覆盖问题．我们感谢书末参考文献中列出的所有作者，正是他们出色的工作才使本领域如此精彩感谢林上为、王瑞霞和张淑蓉，本书的部分章节饱含着他们的心血感谢厦门大学张福基教授对我们的指导最后感谢山西大学对本书出版的支持．由于时间仓促，加之作者有限，疏漏之处在所难免，恳请读者批评指正

图论作为离散数学的一个重要分支，已有两百多年的历史由于其广泛的应用背景半个世纪以来，越来越多的科研工作者投入到了该领域的研究中．是在计算机的出现和推动下，有关图的理论有了更加迅速的现在已经成为研究系统工程、管理工程、计算机科学、通信与网络理论、自动控制、运筹学以至社会科学等诸多学科的一种重要数学工具用图来表示互连网络拓扑结构这一事实已被计算机科学工作者和工程技术人员广泛接受和运用实践证明，图论是设计和分析互连网络拓扑结构的一个有用的数学工具…“对于互连网络来说，有一类重要的问题是在某一个网络上模拟另外一个网络，这个问题称为嵌入问题在本章中，我们先简单介绍互连网络容错嵌入问题的应用背景，再对本书将用到的图论概念和它们相应的网络背行回顾，最后介绍相关研展及本书的主要内容pan>．pan>图与互连网络pan>．pan>．pan>并行计算机互连网络科学与工程计算领域对计算能力的要求是永无止境的．199pan>年，美国高性能计算和通信计划(High Performanccomputing and(~ommunication，HPCC：)提出了科学与工程计算领域里具有深远影响的一些重大挑战性课题，其括中长期天气预报、湍流分析、海洋环流建模、空气动力学、三维等离子体研究、分子结构设计、全球气候变化、结构生物学、图像理解等诸多方面所有这些课题全都具有极大的计算量，因而无一不对计算机的性能提出了高的要求【31_这些需求的增长超出了微处理机性能增长的情况，使得单处理器计算机的处理速度远远不能满足需要具有多处理器的并行计算机(I)arallel computer)为实现高性能计算提供了解决方案，以满足人们对计算能力日益增长的需求科学家已经发现，在大多数科学和工程应用中，解决问题的算法本身就具有并行性，因此，无论是基于共享存储器的高性能计算机(tfigh performan(：e computer，HP(：)，还是大规模并行处理机(massivel)rparallel pro(：essor，MF’P)，超大规模并行、多级存储结构都已经成为其必然的发展趋势在这些系统中，都集成了大量的、能执行用户任务的处理单元(可以是处理.....

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