论文部分内容阅读
人们通常用图做为数学模型表示多处理机系统的互连网络拓扑，其中图的顶点表示处理机，边表示一对处理机之间的直接通信联系，从而可以通过图的性质来度量网络拓扑的性能.网络的可靠性是指在规定条件下网络保持连通和满足通信要求的能力.k-限制边连通度是度量网络可靠性的重要参数.设G是一个无向简单连通图，S是G的一个边割.如果G-S的每个连通分支至少有k个顶点，那么称S是G的一个k-限制边割.若G存在k-限制边割，则称G是λk-连通图.定义λk(G)=min{|S|:S为G的k-限制边割｝为G的k-限制边连通度，具有最少边数的k-限制边割称为G的一个λk-割.定义ξk(G)=min{|[X，(X)]|:X(∈)V(G)，|X|=k，G[X]连通｝.设G是λk-连通图，若λk(G)=ξk(G)，则称G是极大k-限制边连通的，简记为G是λk-最优的.若G的每个λk-割都能分离一个k阶连通子图，即G的每个λk-割都是某个k阶连通子图的关联边集，则称G是超级k-限制边连通的，简记为G是超级-λk的.一般来说，以极大k-限制边连通图或超级k-限制边连通图为基础的拓扑构建的网络都具有较高的可靠性.
本文在前人的工作基础上，继续研究了图的极大k-限制边连通性和超级尼-限制边连通性，共分为三章.
第一章综述k-限制边连通度的应用背景和研究进展并介绍本文中将用到的一些基本概念、术语和记号.
第二章给出了图是极大k-限制边连通的和超级k-限制边连通的度条件，得到以下结论:
(1)设k≥2是一个正整数，G是一个阶为v(G)＞k(k-1)的λk-连通图.如果G满足以下两个条件，则G是极大k-限制边连通的.
(a)对任意一对距离为m的顶点u，v∈V(G)有max{dG(u)，dG(v)｝≥「v(G)/2」+k-2m+1，其中2≤m≤k;
(b)对G中同构于k+1阶完全图的子图H，存在一点v∈V（H）满足dG(v)≥「v(G)/2」+k-1.
(2)设k≥2是一个正整数，G是一个阶为v(G)＞k（k-1）的λk-连通图.如果G满足以下两个条件，则G是超级k-限制边连通的.
(a)对任意一对距离为m的顶点u，v∈V(G)有max｛dG(u)，dG(v)｝≥「v(G)/2」+k-2m+2，其中2≤m≤k;
(b)对G中同构于k+1阶完全图的子图H，存在一点v∈V（H）满足dG(v)≥「v(G)/2」+k.
第三章给出了二部图是极大k-限制边连通的充分条件，主要结果如下:
(1)设G=(X∪ Y,E)是一个阶为v(G)≥8的连通二部图且ξ4(G)≤「V(G)/2」.若G有一个饱和X或Y中所有顶点的匹配且对任意的u，v∈X和u，v∈Y都有|N(u)∩N(v)|≥4，则G是极大4-限制边连通的.
(2)设k≥2为一个正整数，G=(X∪ Y,E)是一个阶为v(G)≥2k的连通二部图.令[U,(U)]是G的一个λk-割，记U*={v∈U:|[v,U]|≤k-1/2｝.若对任意的u，v∈X和u，v∈Y都有|N(u)∩N(v)|≥k，且当|U*|＞「k/2」时，对任意的u∈U*满足dG(u)≥「v(G)/2」-1，则G是极大k-限制边连通的.
(3)设k是满足2≤k≤δ+1的一个正整数，G=(V∪ V"，E)是一个阶为v(G)≥2(δ+1)的连通二部图.若G存在一个λk-割S=[X，(X]满足|X|≤|X|，|X∩V|≤「v(G)/4」和|X∩V"|≤「v(G)/4」，并且对任意一对距离为2的顶点x，y有dG(x)+dG(y)≥2「v(G)/4」+2k-2，则G是极大k-限制边连通的.