几类图的全局强迫数和完全强迫数

发布时间：2017-03-25 01:12

  本文关键词：几类图的全局强迫数和完全强迫数，由笔耕文化传播整理发布。

【摘要】：设G是边集为E(G)且有完美匹配的简单连通图。G的全局强迫集指的是G的一个边子集S,使得S限制到G的任何完美匹配上都两两不同。基数最小的全局强迫集中的边数称为G的全局强迫数。类似地,G的完全强迫集指的是G的一个边子集S,使得S限制到G的任何完美匹配上都是该完美匹配的一个强迫集。基数最小的完全强迫集中的边数称为G的完全强迫数。本文考虑了几类图的全局强迫数或完全强迫数,主要分为三部分。第一部分介绍了图的全局强迫数和完全强迫数的研究背景及研究现状；第二部分通过构造性证明,给出了手枪形状苯系统的全局强迫数的具体计算公式；第三部分研究了原始coronoid图的完全强迫数,然后给出了全偶圈链的完全强迫数的计算公式,最后通过递归分解,给出了关于cata-型多米诺骨牌图的完全强迫数的计算公式及相应的分解算法和计算复杂度。
【关键词】：完美匹配 凯库勒结构 全局强迫数 完全强迫数 苯系统 手枪形状苯系统 原始coronoids图 cata-型多米诺骨牌图
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 中文摘要3-4
• Abstract4-6
• 第一章 绪论6-10
• 1.1本文研究背景6-8
• 1.2 本文研究问题和主要结果8-10
• 第二章 手枪形状苯系统的全局强迫数10-17
• 2.1 引言10-11
• 2.2 手枪形状苯系统的全局强迫数11-15
• 2.3 进一步的讨论15-17
• 第三章 原始coronoid图和cata-型多米诺骨牌图的完全强迫数17-32
• 3.1 引言17
• 3.2 原始coronoid图的完全强迫数17-21
• 3.3 cata-型多米诺骨牌图的完全强迫数21-26
• 3.4 进一步的讨论26-32
• 第四章 总结32-33
• 参考文献33-36
• 在读期间完成的主要论文36-37
• 致谢37

【相似文献】

中国期刊全文数据库 前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年

  本文关键词：几类图的全局强迫数和完全强迫数，由笔耕文化传播整理发布。

，

本文编号：266454