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

总序
序
前言
主要符号表
第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-元3-立方的哈密尔顿交织性
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 一些说明
参考文献

第1 章绪论
图论作为离散数学的一个重要分支,已有两百多年的历史.由于其广泛的应用背景,近半个世纪以来,越来越多的科研工作者投入到了该领域的研究中.特别是在计算机的出现和推动下,有关图的理论有了更加迅速的发展.图论现在已经成为研究系统工程、管理工程、计算机科学、通信与网络理论、自动控制、运筹学以至社会科学等诸多学科的一种重要数学工具.
用图来表示互连网络拓扑结构这一事实已被计算机科学工作者和工程技术人员广泛接受和运用.实践证明,图论是设计和分析互连网络拓扑结构的一个非常有用的数学工具[1, 2].对于互连网络来说,有一类重要的问题是在某一个网络上模拟另外一个网络,这个问题称为嵌入问题.在本章中,我们先简单介绍互连网络容错嵌入问题的应用背景,再对本书将用到的图论概念和它们相应的网络背景进行回顾,*后介绍相关研究进展及本书的主要内容.
1.1 图与互连网络
1.1.1 并行计算机互连网络
科学与工程计算领域对计算能力的要求是永无止境的.1991年,美国高性能计算和通信计划(HighPerformanceComputingandCommunication,HPCC)提出了科学与工程计算领域里具有深远影响的一些重大挑战性课题,其中包括中长期天气预报、湍流分析、海洋环流建模、空气动力学、三维等离子体研究、**分子结构设计、全球气候变化、结构生物学、图像理解等诸多方面.所有这些课题全都具有极大的计算量,因而无一不对计算机的性能提出了非常高的要求[3].这些需求的增长超出了微处理机性能增长的情况,使得单处理器计算机的处理速度远远不能满足需要.
具有多处理器的并行计算机(parallelcomputer)为实现高性能计算提供了解决方案,以满足人们对计算能力日益增长的需求.科学家已经发现,在大多数科学和工程应用中,解决问题的算法本身就具有并行性,因此,无论是基于共享存储器的高性能计算机(highperformancecomputer,HPC),还是大规模并行处理机(massivelyparallelprocessor,MPP),超大规模并行、多级存储结构都已经成为其必然的发展趋势.在这些系统中,都集成了大量的、能执行用户任务的处理单元(可以是处理器、计算节点或商用计算机)及存储单元,这些处理单元通过互连网络,以时间重叠、相互协同的方式分别完成用户任务的不同部分,这也是“并行”的含义.因此,这些通过某种方式连接多个处理单元和存储单元、并行的高性能计算机,也被称作并行计算机.
并行计算机系统的一个基本特征是它的元件之间要通过物理连线按照某个模式相互连接在一起以传输信息.随着对并行计算机系统研究的不断深入,科学家们开始认识到,科学计算不但需要浮点计算速度,还需要信息传输速度.随着单个处理器速率的不断提高、体积的不断缩小、互连带宽增大以及并行计算机中的处理器数量不断增加,多处理单元之间经过相互连接进行通信的开销也随之大大增加.因此,并行计算机系统功能的实现很大程度上越来越依赖于元件之间的连接模式.
系统中元件之间的连接模式称为该系统的互连网络(interconnectionnetworks),简称为网络.从拓扑上讲,一个系统的互连网络逻辑上指定了该系统中所有元件之间的连接方式.
在并行计算机系统中,尤其是大规模的并行计算机系统中,互连网络的性能对整个并行计算机系统的性能起着重要的
,甚至是决定性的作用,以至于并行计算机的设计理念已经由以CPU为主逐步让位于以互连网络为主.因此,互连网络的研究成为并行计算领域研究的热点之一.
从图论的角度来看,互连网络可以用图1.1来表示.图的顶点表示系统中的元件,图的边表示元件之间的物理连线,而关联函数指定了元件之间的连接方式.这样的图称为互连网络拓扑结构(topologicalstructure),简称网络拓扑(networktopology).反之,图也可以看成是某个互连网络的拓扑结构.从拓扑上讲,图和互连网络是等价的.在本书后面的叙述中,我们不区分“图”和“互连网络”,将网络、元件和连线分别说成图、顶点和边.
迄今为止,人们已经提出了很多互连网络,对它们也有各种分类的方法.但从并行计算机系统的角度出发,以网络开关元件与处理器为结点的连接方式来分类似乎更为合理.这样,互连网络按几何形状分为两大类:规则互连网络和不规则互连网络.规则互连网络又分为动态互连网络和静态互连网络两种.如图1.1所示.
动态互连网络,其输入和输出间的连接关系是可变的,由其互连的结点之间的连接关系也是可变的.一般动态互连网络由物理上都是集中的单级或多级开关网络构成.由于物理上的集中和控制上的相对复杂,使得这种网络的可扩展性较差.只适用于结点数不多、规模不大的系统互连.常见的动态网络拓扑结构有:蝶形网(butter.ynetwork)、洗牌交换网(shu.e-exchangenetwork)、交叉开关网(cross-barswitchnetwork)、Benes网、STARAN网、数据交换网等.
静态互连网络,其输入和输出间的连接关系是固定的,由其互连的结点之间的连接关系也是固定的.非直接连接的结点间的通信不像动态互连网络通过动态改变开关网络的连接完成,而是由源结点到目的结点间路径上的路由器协助完成.由于构成静态互连网络的路由器逻辑上是独立的,物理上是分布的,因此静态互连网络扩展性好,可支持不同规模并行系统的构成.根据网络的维数,静态网络可以分为一维、二维和多维网络.常见的静态网络拓扑结构有:线性列阵形网(lineararray)、单环网(ring)、网格形网(mesh)、树形网(tree)、蜂窝网(honeycomb)、超立方体形网(hypercube)、总线形网(bus)、全互连网等.部分网络拓扑如图1.2所示.
..
(a)线性列阵形网(b)单环网
(c)树形网(d)网格形网
图1.2
目前的并行计算机系统绝大多数采用的都是静态互连网络,在本书中,我们感兴趣的是静态互连网络拓扑结构.
1.1.2 图论的一些基本概念和符号
本文所考虑的图都是有限简单无向图,也就是说,我们所考虑的无向图都有有限的顶点集和边集,并且既不包含环也没有两条连接同一对顶点的边.本节介绍本书将用到的图论的基本概念和记号.一些专用术语和概念,我们将在使用时再予以介绍.
设G=(V,E)是一个无向图,其中V=V(G),E=E(G)分别表示图G的顶点集和边集.用ν(G)表示G的顶点数,称为G的阶,ε(G)表示G的边数,即ν(G)=|V(G)|,ε(G)=|E(G)|.当用图来表示网络时,点代表网络结点,边代表节点之间的直接通信连接.
若边e的端点为u,v,我们用(u,v)表示边e.此时,称u和v(在G中)相邻,
又称e与u相关联.G中所有与顶点u相邻的点所组成的集合NG(u)叫做u的邻
域.记图G中与顶点u相关联的边的集合为EG(u).顶点u的度dG(u)是指G中与
u相关联的边的数目.0度点称为孤立点.分别用δ(G)=min{dG(u):u∈ V(G)}
和Δ(G)=max{dG(u):u∈ V(G)} 表示图G的*小(顶点)度和*大(顶点)度.
若对每个顶点v ∈ V(G)都有dG(v)=k,则称图G是k正则的.一个图是二部图,若它的顶点集可以被划分为两个不相交的集合X和Y使得每条边的两个端点分别在X和Y中;这样的一个分划(X,Y)被称为是图的一个二分划,X和Y被称为是图的两个部.记具有二分划(X,Y)的二部图G为G[X,Y].
一条路P[v0,vt]=.v0,v1,,vt. 是使得任意两个连续的顶点都相邻的一条
互不相同的顶点序列.点v0和vt??? 是这条路的两个端点.也称这条路是一条(v0,vt)
路.路的长度是指这条路上边的数目.在本书中,记通过倒转P[v0,vt]的顶点而得
到的路为P .1[vt,v0],即P.1[vt,v0]=.vt,vt.1,,v0.. 图G 的一个圈是一列
???
顶点.v0,v1,,vt,v0.,其中t.2,v0,v1,,vt两两不同且任两个连续的顶点
??????
相邻.长为奇数的圈称为奇圈,长为偶数的圈称为偶圈.长为k的圈称为k圈,3圈
也称为三角形.G中*短圈的长度称为G的围长,记为g(G).经过G的每个点一次的圈称为图G的哈密尔顿圈.称一个包含哈密尔顿圈的图是哈密尔顿的.经过图G所有顶点一次的路是G的哈密尔顿路.若图G中任意两个不同的顶点之间存在一条哈密尔顿路,则称图G是哈密尔顿连通的.因为任何非平凡的二部图都不可能是哈密尔顿连通的,哈密尔顿交织性这一概念被提出来.若对二部图G[X,Y]的任意两个在不同部中的顶点(一个在X中,另一个在Y中),G存在一条哈密尔顿路连接这两个顶点,则称图G是哈密尔顿交织的.
图G中一对顶点u,v之间存在一条(u,v)路,则称点u,v是连通的.连通是
顶点集V上的一个等价关系.于是存在V的一个划分,即把V分成互不相交的非空子集V1,V2,,Vω,使得两个顶点u和v是连通的,当且仅当它们属于同一子
???
集Vi.子图G[V1],G[V2],,G[Vω]称为G的连通分支.若G只有一个连通分支,则称G是连通的;否则G??? 是不连通的.
如果u和v是连通图G中两个顶点,那么u和v之间的距离dG(u,v)是G中*短(u,v)路的长度.因此,若G是一个连通图,则G中(u,v)路的长l满足dG(u,v).l.|V(G)|. 1.若图G中每一对u,v点之间存在长从dG(u,v)到|V(G)|. 1的(u,v)路,则称图G是泛连通的.若对任意故障点和(或)故障边的集合F(|F | .k),G. F 中任意两点间存在长从p 到|V (G . F )|. 1的路,则称图G是k-故障p-泛连通的.
G的直径D(G)是指G的所有顶点对之间的*大距离;若G不连通,则定义G的直径为无穷大.设F是连通图G的一个边子集,若G. F不连通,则称F为G的一个边割.G中边数*少的边割的势称作G的边连通度.图G的连通度是指*小的顶点数使得删除这些顶点后图G不连通或是平凡的.一个连通度为c的图G的容错直径是指删去任意c. 1个顶点得到的子图的*大直径.G的围长g(G)是指G中*短圈的长;若G没有圈,则定义G的围长为无穷大.
若图G包含长从围长g(G)到|V(G)| 的圈,则称G是泛圈的.若它包含一个长从4到|V(G)| 的偶圈,则称G是偶泛圈的.进一步,若偶泛圈图G的每条边都在长从4到|V(G)| 的偶圈上,则图G被称为是边偶泛圈的.泛圈性和偶泛圈性都是判断一个网络拓扑是否适合将不同长度的圈映射到其上的重要指标.若对任意边集F(|F | .k),G. F中存在一个哈密尔顿圈,则图G是k-边故障哈密尔顿的.若对任意故障点和(或)故障边的集合F(F.k),G. F中存在一个哈密尔顿圈,则图G是k-故障哈密尔顿的.||
图的一个匹配是指一个两两不相邻的边的集合.设M是一个匹配,称每个同M中某条边关联的点被M饱和.图的一个**匹配是指使每个点都被饱和的匹配.图的一个几乎**匹配是指使得除一个顶点外其余每个顶点都被饱和的匹配.
称两个图G和H是同构的(记作G~→
=H),如果存在一个一一对应θ:V(G)V(H),使得uv∈ E(G)当且仅当θ(u)θ(v)∈ E(H).为方便起见,本书有时也把同构的两个图看成是同一个图.
假设U是V=V(G)的非空子集.以U为顶点集,以G中两个端点均在U中的所有边的集合为边集组成的子图称为G的由U导出的子图,记为G[U];这时,也称G[U]为G的导出子图.导出子图G[V. U] 记为G . U;它是从G中删去U中的顶点以及与U中的顶点相关联的边所得到的子图.若U={u}, 则G .{u} 简记为G . u.
假设F是E=E(G)的非空子集.以F为边集,以F中所有边的端点的并集为顶点集的子图称为G的由F导出的子图,记为G[F];这时,也称G[F]为G的边导出子图.特别地,在不引起歧义的情况下,我们有时也记.F . 为边导出子图.边导出子图G[E. F ] 简记为G . F . 设e 是G 的一条边. 则G .{e} 简记为G . e.在本书中集合X和Y的差我们记作X\ Y,但当Y中只有一个元素时,比如Y={y} 时, 我们也将X \{y} 记作X \ y.
如果G是互连网络的拓扑结构,那么,G+F表示为了改进网络的性能而添加连线集F之后得到的网络;G. U 和G . F分别表示网络包含一个故障点集U和故障连线集F.
令C1和C2是两个圈.我们记C1. C2是由E(C1). E(C2)导出的图,其中E(C1). E(C2)是E(C1)和C(C2)的对称差.
并和交是图组合的两个*基本的方式.两个简单图G和H的并G∪H是指顶点集为V(G)∪ V(H),边集为E(G)∪ E(H)的图.若图G和H没有公共顶点,则称它们是不相交的.若图G和H不相交,则它们的并图是一个不交并,记为G+H.类似可定义两个简单图G和H的交G∩ H(注意到当图G和H不相交时,它们的交为空图).
书中未予定义而直接使用的无向图术语和记号可参见文献[4].
1.1.3 互连网络设计原则
如前所述,随着超大规模集成电路的出现和现代通信技术的高速发展,人们已经能够构造出大规模并行计算机系统.然而,在设计这些系统时,选择什么样的互连网络拓扑至关重要.一般而言,在设计互连网络时有两个*基本的设计原则:**率和低成本.但是影响网络效率和成本的因素很多,总的而言分四个方面:操作方式、控制策略、交换方法以及网络拓扑.具体一些,操作方式分为同步操作、异步操作和组合操作三种;控制策略分为集中控制和分布式控制两种;交换方法分为巡回交换、数据包交换和整合交换三种;趋于规则的网络拓扑分为动态网和静态网两种.本节仅仅从网络拓扑方面来简单介绍网络设计需要遵循的几个原则[2, 5, 6].
1. 规则性
目前使用和研究的互连网络大多是规则网络.规则性包括均匀性和对称性等.人们希望网络中的组件能够以相同的方式启动和连接,使得在各结点的容量和连线负载保持平衡.这就要求网络拓扑结构应具有一定的对称性.图中的点传递和边传递性质是衡量网络对称性的指标.
2. 小的固定顶点度
顶点的度固定,则网络的输入和输出间的连接关系固定,结点之间的连接关系也固定.这也是系统网络大多选择静态网络的原因.顶点的度小意味着物理连接的

div>