一些网络的（子）结构割的刻画.pdf

摘要

随着社会科学技术的进步,并行系统越来越受到人们的关注.在许多并行计算机系统

中,处理器以互连网络为基础.互连网络通常用一个图表示,其中点表示处理器,边表示各

处理器之间的通信链路.在一个大型处理器中,处理器和通信链路故障是不可避免的.因

此,互连网络的容错性成为一个重点研究问题.计算连通度是评价网络容错性的一个方法,

而结构连通度和子结构连通度是连通度的推广.对比这两个参数,一个更有趣和更重要的

问题是刻画互连网络的最小结构割和最小子结构割.本文分为四章:

第一章,主要介绍了相关的研究背景和现状,以及所用到的基本概念.

第二章,首先介绍了冒泡排序图的定义和性质,并证明了:

−1

(1)1,1,⌈2⌉,其中≥,≤≤.

(2)是hyper|-连通的和hyper子-|-连通的,其中≥,≤≤.

1,11,1

第三章,首先介绍了星图的定义和性质,并证明了:

(1)是hyper|-连通的和hyper子-|-连通的,其中≥,≤≤−.

1,11,1

(2)是hyper|-连通的和hyper子-|-连通的,其中≥.

41,141,1

(3)是hyper|-连通的和hyper子-|-连通的,其中≥.

5151

(4)是超|-连通的和hyper子-|-连通的,其中≥.

6161

第四章,首先介绍了分层星图的定义和性质,并证明了:

(1)1,11,1,其中≥.

(2)1,1,−,其中≥,≤≤−.

(3)是hyper|-连通的和hyper子-|-连通的,其中≥.

1,111,11

(4)是hyper|-连通的和hyper子-|-连通的,其中≥,≤≤−.

1,11,1

关键词:容错性,(子)结构连通度,冒泡排序图,星图,分层星图

I

ABSTRACT

Withtheprogressofsocialscienceandtechnology,parallelsystemsarereceivingincreasing

attention.Inmanyparallelcom