圖的匹配強(qiáng)迫譜與匹配反強(qiáng)迫譜研究.pdf

1、圖G中的一個(gè)完美匹配M的強(qiáng)迫數(shù)是指為確定M所需要的最少的M-匹配邊的數(shù)目.圖中完美匹配的強(qiáng)迫數(shù)的概念最早由Harary等提出。Klein和Randi′c也在早期的化學(xué)文獻(xiàn)中提出了同樣的概念,稱作是凱庫(kù)勒結(jié)構(gòu)的內(nèi)自由度,這在化學(xué)共振理論中有重要應(yīng)用。圖G中所有完美匹配的強(qiáng)迫數(shù)的集合稱作是G的強(qiáng)迫譜,強(qiáng)迫譜中最小整數(shù)稱作是圖G的強(qiáng)迫數(shù)或最小強(qiáng)迫數(shù),最大整數(shù)叫做圖G的最大強(qiáng)迫數(shù).從對(duì)立面考慮,M的反強(qiáng)迫數(shù)是指從圖G中刪去最少的不在M中的邊的數(shù)

2、目使得M是刪邊后的圖中唯一的完美匹配.圖G中所有完美匹配的反強(qiáng)迫數(shù)的集合稱作是G的反強(qiáng)迫譜,反強(qiáng)迫譜中最小整數(shù)稱作是圖 G的反強(qiáng)迫數(shù)或最小反強(qiáng)迫數(shù),最大整數(shù)叫做圖G的最大反強(qiáng)迫數(shù).
　　本文共有六個(gè)章節(jié).第一章首先介紹了圖論中的一些基本概念和符號(hào);然后介紹了匹配強(qiáng)迫和匹配反強(qiáng)迫問(wèn)題的研究背景及進(jìn)展;最后我們給出了本文的主要研究結(jié)果.
　　在第二章中,我們證明了強(qiáng)迫數(shù)等于1的六角系統(tǒng)H的強(qiáng)迫譜要么是從1到其Clar數(shù)cl(H)

3、的整數(shù)區(qū)間[1。cl(H)],要么是[1。cl(H)]\{2}.我們還給出了六角系統(tǒng)的強(qiáng)迫譜沒(méi)有間隔的一個(gè)充分條件.
　　在第三章中,我們首先證明了任意一個(gè)正整數(shù)集合都可以是某個(gè)圖的反強(qiáng)迫譜;接著我們刻畫了反強(qiáng)迫數(shù)等于1的平面基本二部圖;然后我們證明了圖的最大反強(qiáng)迫數(shù)不超過(guò)其基圈數(shù),并且刻畫了最大反強(qiáng)迫數(shù)等于基圈數(shù)的極值圖;最后我們證明了確定最大度為4的二部圖中完美匹配的反強(qiáng)迫數(shù)是NP-完全問(wèn)題。
　　在第四章中,我們證明了