图的限制边连通性与哈密尔顿性

发布时间：2017-12-03 04:02

  本文关键词：图的限制边连通性与哈密尔顿性

  更多相关文章： 图 互连网络 极大κ限制边连通图 超级κ限制边连通图 极大κ等周边连通图 Hamiltonian图 κ限制边连通度 λ_κ-碎片 团 围长

【摘要】：多处理机系统的互连网络拓扑通常以图为数学模型,因此网络拓扑的性能可以通过图的性质和参数来度量.在设计和选择多处理机系统的互连网络拓扑时,我们要考虑的一个问题是系统的可靠性(容错性).边连通度λ(G)是度量网络可靠性的一个重要参数.通常,边连通度A(G)越大,网络越可靠.但是,这个参数有一个明显的缺陷：它假定系统的任何部分都可能同时损坏,这在实际应用中几乎不可能发生.为弥补这个缺陷,Fabrega和Fiol提出了k限制边连通度的概念.对于互连网络来说,有一类重要的问题,是在某一个网络上模拟另外一个网络,这个问题被称为网络嵌入问题.图的嵌入是把客图映射到主图.许多应用,如建筑仿真,处理器分配,和超大规模集成电路芯片设计,可以建模为图的嵌入.本文主要研究图的k限制边连通性和Hamiltonian性.本文共分五章.第一章首先给出本文将用到的图论方面的术语和记号,然后综述图的k限制边连通性和Hamiltonian性的应用背景和研究进展,最后概述了本文的研究内容和获得的主要结论.作为边连通度的推广,k限制边连通度是度量图的连通性的一个重要参数.当k=2时,2限制边连通度通常被称为限制边连通度.2012年,Holtkamp等研究了非极大限制边连通无3-圈图的λ2-碎片的基数的下界和非极大k限制边连通无3-团图的Ak-碎片的基数的下界.进一步,给出了极大限制边连通无3-圈图和极大k限制边连通无3-团图的充分条件.第二章主要研究无(p+1)-团图和围长为g的图的极大k限制边连通性.我们首先给出了一个非极大k限制边连通且无(p+1)-团图的λk-碎片的基数的下界.其次,我们给出了一个围长为9的非极大k限制边连通图的λk-碎片的基数的下界.最后,一些极大k限制边连通图的充分条件被给出.近年来,图的极大限制边连通性和极大3限制边连通性得到了广泛的研究.但是关于更一般的k限制边连通性研究略少.这需要被推广到更一般的情形.2004年,Hell-wig和Volkmann证明了：如果λ'-连通图G中所有不相邻顶点u,v都满足N(u)∩N(v)|≥2,且G中每个三角形T中都存在一点u使得d(v)≥[(v(G))/2]+1,那么G是极大限制边连通的.第三章主要研究了图的极大k限制边连通性和超级k限制边连通性.我们首先给出了一个图是极大k限制边连通的充分条件,这个结果推广了上面的结论.其次,我们证明了如果G中任意一对不相邻顶点都有d(u)+d(v)≥v(G)+2k-4且G不属于一类特殊图,那么G是极大k限制边连通的.最后,我们给出了一个图是超级k限制边连通的度条件.k等周边连通度是一个与k限制边连通度密切相关的概念.它也是度量网络可靠性的一个重要的参数.2009年,Wang等人证明了一个阶至少为2k的图G,如果G中任意一对不相邻顶点u,v都满足W(u)∩N(u)|≥2k-1,那么G是极大k等周边连通的.第四章主要研究极大k等周边连通图的邻域交条件.我们首先给出了一个在k等周边连通图中,由γk-碎片生成的子图中存在(k-1)-路的充分条件.其次,我们给出了极大等周边图的一个邻域交条件,这个是上面结果的一个改进.最后研究了直径为2的图的极大k等周边连通性.一个图G中的Hamiltonian圈是指经过G中每个顶点恰好一次的圈Hamiltonian圈的嵌入是图论中的一个热点问题.第五章主要研究直径为2的图中的Hamiltonian圈.首先,我们给出了相关的概念和结果.然后,我们证明了如果对于阶至少是3的图G中任意一对不相邻顶点都有N(u)∩N(u)|≥[v/2]-1,且G不属于一类特殊图,那么G是一个Hamiltonian图.
【学位授予单位】：山西大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】

中国期刊全文数据库 前10条

1 霍美霞;高敬振;;图的四阶边连通度的存在性[J];科学技术与工程;2007年14期

2 周艳;武燕;;关于金字塔网限制边连通度的研究[J];西南大学学报(自然科学版);2007年08期

3 杨超;徐俊明;;强乘积图的连通度和边连通度(英文)[J];中国科学技术大学学报;2008年05期

4 蔡俊青;高敬振;;k阶限制边连通度最优的一个充分条件[J];科学技术与工程;2008年13期

5 赵元庆;金显华;;星网的4-限制边连通度[J];计算机工程与应用;2012年13期

6 李国君;一类特殊图的连通度与边连通度之间的关系[J];烟台师院学报(自然科学版);1987年02期

7 张胜贵，，王自果;系统的核度与边连通度[J];系统工程与电子技术;1995年06期

8 江秉华;陈金阳;王志平;;图的平均边连通度[J];北华大学学报(自然科学版);2013年06期

9 王应前,李乔;图的限制性边连通度等于其最小边度的一个充分条件[J];高校应用数学学报A辑(中文版);2001年03期

10 王铭,李乔;关于图的超常边连通度和等周边连通度的等值性[J];上海交通大学学报;2002年06期

中国重要会议论文全文数据库 前1条

1 吕敏;徐俊明;范英梅;;无向de Bruijn图的超边连通度(英文)[A];中国运筹学会第七届学术交流会论文集（下卷）[C];2004年

中国博士学位论文全文数据库 前6条

1 张磊;图的限制边连通性与哈密尔顿性[D];山西大学;2015年

2 尚莉;图的高阶限制边连通度[D];兰州大学;2008年

3 李峰伟;网络的若干稳定性参数的研究[D];南开大学;2006年

4 祁忠斌;曲面Fullerene图的环边连通度、共振性及哈密尔顿性[D];兰州大学;2008年

5 王建伟;容错网络中若干问题研究[D];中国科学技术大学;2010年

6 李向军;某些网络容错性研究[D];中国科学技术大学;2013年

中国硕士学位论文全文数据库 前10条

1 郭利涛;图的3-限制性边连通度和3-限制性连通度[D];新疆大学;2008年

2 桑镇;关于k阶限制边连通度若干问题的研究[D];山东师范大学;2009年

3 陈亮;高阶限制边连通度的最优性和超级性[D];山东师范大学;2009年

4 张凤娟;k阶限制边连通度的最优性和超级性[D];山东师范大学;2009年

5 蔡俊青;k-限制边连通度的存在性与上界[D];山东师范大学;2009年

6 杨莹莹;图的k阶限制边连通度的若干性质[D];山东师范大学;2010年

7 李鑫;关于图的k-限制边连通度的最优性和超级性[D];山东师范大学;2010年

8 孟祥军;图的低阶限制边连通度的研究[D];山东师范大学;2010年

9 马玉;图的k-限制边连通度性质的研究[D];山东师范大学;2011年

10 周宏强;图的k-限制边连通度的最优性和超级性[D];山东师范大学;2011年

本文编号：1247338