圖的匹配強迫譜與匹配反強迫譜研究.pdf

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

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

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