完全二部图K_（n,n）的容错偶泛连通性和完全k（k≥3）部图K_（n,n,…,n）的泛连通性.pdf

文档介绍：年第期漳州师范学院学报自然科学版..年
总第期.. .
文章编号:——

王超越
漳州师范学院数学与信息科学系,福建漳州
摘要:图称为泛连通的,如果对于中距离为,的任意两点和,中都存在每个长为,的:
路这里,,≤卜;图称为偶泛连通的,如果对于中距离为【,的任意两点和,中都
存在每个长为,的:路这里,.≤,≤,,且,和,
下结论: 当时,在完全二部图中,若故障边数,一,,并且的上界
,一是最优的;.
关键词:泛连通性;偶泛连通性;边客错;完全二部图;完全多部图
中图分类号: . 文献标识码:
——

. ,
·
,,
: ,
,,,一,,
; ,
,,,一,一,.
. , ,
一,,一,一
; .
: ; ;—; ;
.
引言
在互连网络中,
此,、度数小、
通信成本低的优点,
长度的路或圈,,研究互连网络的泛圈性

化,如果一个网络是泛连通的则一定是泛圈的.
对于一个给定的互连网络,最多能容许多少个节点和或连线同时发生故障,而剩余的子网络中仍然
具有某种结构或各节点之间还仍能继续保持通信,
收稿日期:
作者简介:王超越,男,河南省开封市人,硕士研究生.
漳州师范学院学报自然科学版
运行时,面上系统出现故障是难以避免的,因此,
,已经被深入地研究和广泛地探讨
见文献【.
完全多部图是一类重要的图,也是一类基本的互连网络拓扑结构,本文研究有故障的完全多部图中,
路的嵌人情况,即它的容错偶泛连通性和泛连通性.
预备知识
本文的图论术语和记号见参考文献.,代表一个简单图,顶点集记为,边集记为
.如果妨是任意的顶点,那么记,表示边,并之间的路用:表示,其中,是端
:路的长称为矛口,的距离,记为,.设,由导出的的子图记为,.
图称为泛连通的,如果对于图中距离为,的任意两点和,中都存在每个长为,的
:路这里,≤,≤—.
图称为偶泛连通的,如果对于中距离为,的任意两点和,中都存在每个长为,的.
路这里,,,且,和,有相同的奇偶性.
完全多部图是指一个简单图,它的顶点集可分解为多个非空子集,两个顶点相邻当且仅当它们不在同
,
时,记为
,
主要结果及其证明
定理当,≥时,在完全二部图
, 中,若故障边数≤一,则一是偶泛连通