5-连通图和7-连通图的可收缩边的分布
本文关键词:5-连通图和7-连通图的可收缩边的分布
【摘要】:图的连通性是图论非常重要的概念之一,图的许多性质和图的连通性有着密切的关系。在图论的研究方法中,我们常常运用一些图的特性的运算,用一些简单的连通图构造出复杂的连通图满足要求的性质。基于此,图的可收缩边运算成为研究复杂连通图的有力工具之一。本文选择连通图的可收缩边作为研究的对象,考虑5-连通图和7-连通图的可收缩边在不同的特定子图——最长圈、生成树和完美匹配上的分布情况,并得到相应的结果。对于5-连通图,本文首先对5-连通图最长圈上可收缩边的分布的已有成果进行了改进,并首次提出5-连通图生成树上可收缩边的分布情况,得出的主要结论有:定理2.1.3设G是5-连通图,且G中不存在2-断片。P:x=x1x2…xn=少是G的一条最长(x,y)-路。如果路P上任一顶点xi都满足以下条件之一,那么P上至少有两条可收缩边:(1)d(xi)≥6;(2)d(xi)=5,则[V(P)]中无3-圈包含它。定理2.2.1设G是5-连通图,且G中不存在2-断片,H是G的一棵生成树。如果H上的任一顶点均满足以下条件之一,则生成树H上至少有一条可收缩边:(1)d(xi)≥6;(2)d(ci)=5,则[V(H)]中无3-圈包含它。对于7-连通图,本文仍然采用树形结构理论进行分类讨论,考虑了7-连通图的可收缩边在最长圈、生成树以及完美匹配上的分布情况,得到的主要结论有:定理3.1.5设G是7-连通图,且G的任意断片的阶都大于3。若C:x=x1x2…xn=少是G的任意最长圈,则C至少包含三条可收缩边。定理3.2.1设G是7-连通图,H是G的一棵生成树。如果口任意一个断片的阶都大于3,那么生成树H上至少包含两条可收缩边。定理3.3.7设G是7-连通图且|G|15,并且M是G的一个完美匹配,如果M上的任意一条边均不在三角形上,那么M上至少包含两条可收缩边。定理3.3.8设G是7-连通图且|G|15,M是G的一个完美匹配,如果图G的任意一个断片的阶都大于3,那么M上至少包含两条可收缩边。
【关键词】:连通图 可收缩边 最长圈 生成树 完美匹配
【学位授予单位】:山东大学
【学位级别】:硕士
【学位授予年份】:2015
【分类号】:O157.5
【目录】:
- 中文摘要6-8
- ABSTRACT8-10
- 符号说明10-11
- 第一章 绪论11-14
- §1.1 图论概述11-12
- §1.2 基本概念12-13
- §1.3 成果综述13-14
- 第二章 5-连通图的可收缩边的分布14-21
- §2.1 5-连通图最长圈的可收缩边的分布14-18
- §2.2 5-连通图生成树的可收缩边的分布18-21
- 第三章 7-连通图的可收缩边的分布21-35
- §3.1 7-连通图最长圈的可收缩边的分布22-27
- §3.2 7-连通图生成树的可收缩边的分布27
- §3.3 7-连通图完美匹配的可收缩边的分布27-35
- 第四章 k-连通图的可收缩边的分布35-37
- 参考文献37-39
- 致谢39-40
- 攻读硕士学位期间发表的学术论文40-41
- 附件41
【相似文献】
中国期刊全文数据库 前10条
1 谢果;判定k-点连通图与k-边连通图极小性的定理[J];四川师范大学学报(自然科学版);2000年05期
2 余世群;一类极大临界h连通图的性质[J];湖北民族学院学报(自然科学版);2002年04期
3 齐登记,余世群;收缩临界6-连通图中的6度点[J];湖北民族学院学报(自然科学版);2002年04期
4 赵克文,曾克扬;哈密尔顿连通图的一点注记[J];工程数学学报;2003年02期
5 赵克文;哈密尔顿连通图与邻域并条件[J];信息工程大学学报;2003年02期
6 余世群;一类极大临界2连通图的结构[J];湖北民族学院学报(自然科学版);2004年04期
7 陈仪朝,苏健基;恰含5条非基本边的极小3连通图[J];广西师范大学学报(自然科学版);2004年03期
8 林福财;关于4连通图的容错直径和宽直径[J];漳州师范学院学报(自然科学版);2005年01期
9 余世群;;一类极大临界4连通图的结构[J];湖北民族学院学报(自然科学版);2006年02期
10 刘育兴;苏健基;;恰有k条非基本边的极小3连通图[J];数学研究与评论;2006年04期
中国重要会议论文全文数据库 前1条
1 张薇;张立辉;乞建勋;李星梅;苏志雄;;带正权的无向连通图中最短路问题研究[A];中国运筹学会第九届学术交流会论文集[C];2008年
中国博士学位论文全文数据库 前10条
1 罗朝阳;图的点度与距离型拓扑指标参数及其应用[D];山东大学;2015年
2 吴亚平;k-连通图中最长圈及余直径研究[D];华中师范大学;2011年
3 康海燕;连通图中可去边和圈的研究[D];山东大学;2010年
4 刘素娟;2-(边-)连通图的彩虹连通数[D];南开大学;2013年
5 陈晓东;无爪图及其扩展图的Hamilton性[D];大连理工大学;2012年
6 侯新民;网络(图)广义直径的研究[D];大连理工大学;2002年
7 蔡建生;图的因子和分数因子[D];山东大学;2007年
8 梁浩;图的拉普拉斯矩阵和临界群[D];中国科学技术大学;2009年
9 洪振木;某些网络可靠性和有效性研究[D];中国科学技术大学;2014年
10 Alaa Amer Najim;关于图的边添加和边减少问题研究[D];中国科学技术大学;2006年
中国硕士学位论文全文数据库 前10条
1 齐恩凤;k-连通图的可收缩边和可收缩圈[D];广西师范大学;2006年
2 余世群;一类极大临界h连通图的结构[D];广西师范大学;2003年
3 覃城阜;收缩临界5-连通图的性质[D];广西师范大学;2004年
4 杨迎球;k连通图中的k可收缩边[D];广西师范大学;2007年
5 张志芳;6连通图中的可收缩边[D];河南师范大学;2011年
6 毕振明;恰含6条非基本边的极小3连通图[D];山东大学;2012年
7 王雪;7-连通图最长圈上的可收缩边及3-连通图可收缩非边的分布[D];山东大学;2013年
8 刘秀松;几类图的全局强迫数和完全强迫数[D];兰州大学;2015年
9 吴敏如;图中过给定点集的圈结构[D];华中师范大学;2015年
10 常晓玲;4-连通图中最长圈上弦的存在性与可去边的关系[D];山东大学;2015年
,本文编号:569204
本文链接:https://www.wllwen.com/kejilunwen/yysx/569204.html