在有完美匹配的圖G中，e是G的一條邊,如果e在G的唯一完美匹配中,那么稱e是G的強(qiáng)迫邊;如果C是G的一個(gè)偶圈滿足G-V（C）有唯一完美匹配,那么稱C是G的強(qiáng)迫圈.如果G的任意一個(gè)偶圈都是強(qiáng)迫圈,那么稱G是圈強(qiáng)迫圖.在連通平面二部圖G中,如果s是G的一個(gè)有限面,刪去s的邊界上的所有頂點(diǎn)得到的圖有唯一完美匹配,那么稱s是G的強(qiáng)迫面.對(duì)于強(qiáng)迫邊的研究,已經(jīng)有一些結(jié)果,包括在六角系統(tǒng)中刻畫了每條邊都是強(qiáng)迫邊的圖是單六邊形;對(duì)六角系統(tǒng)和基本平面二部圖中強(qiáng)迫邊的刻畫.對(duì)于強(qiáng)迫面也得到一些很好的結(jié)果,包括基本平面二部圖的強(qiáng)迫面的刻畫;每一個(gè)面都是強(qiáng)迫面的基本平面二部圖的完整刻畫.關(guān)于圈強(qiáng)迫圖的研究成果主要包括圈強(qiáng)迫哈密頓二部圖和有IS-耳的圈強(qiáng)迫二部圖的完整刻畫.本文研究了強(qiáng)迫邊,強(qiáng)迫圈,及圈強(qiáng)迫圖,主要得到如下結(jié)果:·對(duì)沒有IS耳的圈強(qiáng)迫二部圖給出完整刻畫.由此對(duì)圈強(qiáng)迫二部圖得到完整刻畫.·對(duì)每條邊都是強(qiáng)迫邊的圖給出刻畫.·對(duì)某些特殊圖類中的強(qiáng)迫邊給出刻畫.·對(duì)基本平面二部圖中的強(qiáng)迫圈給出刻畫. 

【文章頁數(shù)】：41 頁

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
第一章 引言
    §1.1 問題背景
    §1.2 定義和常用記號(hào)
    §1.3 相關(guān)結(jié)果
    §1.4 本文主要結(jié)果
第二章 圈強(qiáng)迫圖
    §2.1 引言
    §2.2 預(yù)備知識(shí)
    §2.3 圈強(qiáng)迫二部圖
第三章 強(qiáng)迫邊與強(qiáng)迫圈
    §3.1 引言
    §3.2 預(yù)備知識(shí)
    §3.3 強(qiáng)迫邊
    §3.4 強(qiáng)迫圈
參考文獻(xiàn)
致謝


【參考文獻(xiàn)】：
期刊論文
[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]導(dǎo)出匹配問題的NP-完全性以及導(dǎo)出匹配可擴(kuò)問題的CO-NP-完全性（英文）[J]. 原晉江,楊帆.  運(yùn)籌學(xué)學(xué)報(bào). 2000(01)
[3]無爪圖的導(dǎo)出匹配可擴(kuò)性(英文)[J]. 楊帆,原晉江.  數(shù)學(xué)研究. 1999(01)



本文編號(hào)：3676904