图的k限制边连通性.doc

图的 k 限制边连通性【摘要】：人们通常用图做为数学模型表示多处理机系统的互连网络拓扑,其中图的顶点表示处理机,边表示一对处理机之间的直接通信联系,从而可以通过图的性质来度量网络拓扑的性能.网络的可靠性是指在规定条件下网络保持连通和满足通信要求的能力.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-连通图,若 Ak(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]+κ-2m+1,其中 2≤m≤k;(6)对 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]+κ-2m+2,其中 2≤m≤k;(6)对 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,u∈X和 u,u∈Y 都有|N(u)∩N(u)|≥4,则 G 是极大 4-限制边连通的.(2)设 k≥2为一个正整数,G=(X∪Y,E)是一个阶为 v(G)≥2k 的连通二部图.令[U,U]是 G 的一个 Ak-割,记 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|,|xnV’|≤[v(G)/4]和|X∩V”Ⅳ|≤「v(G)/4],并且对任意一对距离为 2 的顶点 x,y 有 dG(x)+dG(y)≥2[v(G)/4]+2k-2,则 G 是极大 k-限制边连通的.【关键词】：k-限制边连通度极大 k-限制边连通性超级 k-限制边连通性邻域度【学位授予单位】：山西大学 【学位级别】：硕士【学位授予年份】：2013【分类号】：O157.5【目录】：摘要 6-8ABSTRACT8-10 第一章引言 10-15§1.1k-限制边连通度的应用背景及研究进展 10-12§1.2 预备知识 12-15 第二章λ_k-最优图和超级-λ_k 连通图的度条件 15-22§2.1 相关结果 15-16§2.2 主要结果及证明 16-22 第三章 λ_k-最优二部图的充分条件 22-42§3.1 相关结果 22§3.2λ_4-最优二部图的邻域交条件 22-29§3.3λ_k-最优二部图的邻域交条件 29-32§3.4λ_k-最优二部图的度条件 32-42 结束语 42-43 参考文献 43-45 研究成果 45-46 致谢 46-47 个人简况及联系方式 47-49 本论文购买请联系页眉网站。