圈强迫二部图

发布时间：2022-08-13 11:01

　　在有完美匹配的图G中，e是G的一条边,如果e在G的唯一完美匹配中,那么称e是G的强迫边;如果C是G的一个偶圈满足G-V（C）有唯一完美匹配,那么称C是G的强迫圈.如果G的任意一个偶圈都是强迫圈,那么称G是圈强迫图.在连通平面二部图G中,如果s是G的一个有限面,删去s的边界上的所有顶点得到的图有唯一完美匹配,那么称s是G的强迫面.对于强迫边的研究,已经有一些结果,包括在六角系统中刻画了每条边都是强迫边的图是单六边形;对六角系统和基本平面二部图中强迫边的刻画.对于强迫面也得到一些很好的结果,包括基本平面二部图的强迫面的刻画;每一个面都是强迫面的基本平面二部图的完整刻画.关于圈强迫图的研究成果主要包括圈强迫哈密顿二部图和有IS-耳的圈强迫二部图的完整刻画.本文研究了强迫边,强迫圈,及圈强迫图,主要得到如下结果:·对没有IS耳的圈强迫二部图给出完整刻画.由此对圈强迫二部图得到完整刻画.·对每条边都是强迫边的图给出刻画.·对某些特殊图类中的强迫边给出刻画.·对基本平面二部图中的强迫圈给出刻画. 

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 引言
    §1.1 问题背景
    §1.2 定义和常用记号
    §1.3 相关结果
    §1.4 本文主要结果
第二章 圈强迫图
    §2.1 引言
    §2.2 预备知识
    §2.3 圈强迫二部图
第三章 强迫边与强迫圈
    §3.1 引言
    §3.2 预备知识
    §3.3 强迫边
    §3.4 强迫圈
参考文献
致谢


【参考文献】：
期刊论文
[1]A Characterization of PM-compact Hamiltonian Bipartite Graphs[J]. Xiu-mei WANG,Jin-jiang YUAN,Yi-xun LIN.  Acta Mathematicae Applicatae Sinica. 2015(02)
[2]导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性（英文）[J]. 原晋江,杨帆.  运筹学学报. 2000(01)
[3]无爪图的导出匹配可扩性(英文)[J]. 杨帆,原晋江.  数学研究. 1999(01)



本文编号：3676904