平面圖的強(qiáng)迫集、反強(qiáng)迫集與交錯(cuò)集之間的關(guān)系.pdf

1、設(shè)G是一個(gè)圖.G的完美匹配是指覆蓋G中所有頂點(diǎn)的兩兩不交邊的集合.設(shè)M是G的一個(gè)完美匹配。S?E(G).若S?M且S不被包含于G的其它完美匹配,則稱S是M的強(qiáng)迫集;若S?E(G)\M且G?S有唯一的完美匹配M,則稱S是M的反強(qiáng)迫集.M的最小強(qiáng)迫集和最小反強(qiáng)迫集的大小分別稱為M的強(qiáng)迫數(shù)和反強(qiáng)迫數(shù),記作f(G。M)和af(G。M). G中所有完美匹配的強(qiáng)迫數(shù)的最大值和反強(qiáng)迫數(shù)的最大值分別稱為G的最大強(qiáng)迫數(shù)和最大反強(qiáng)迫數(shù),記作F(G)和Af(

2、G).
　　邊交替出現(xiàn)在M和E(G)\M中的圈稱為M-交錯(cuò)圈.兩個(gè)M-交錯(cuò)圈稱為相容的,如果它們要么不相交要么僅相交于M中的邊處.對(duì)于平面二部圖G。Pachter等人證明了 f(G。M)等于 G中互不相交的M-交錯(cuò)圈的最大個(gè)數(shù),雷洪川等人證明了af(G。M)等于G中相容的M-交錯(cuò)圈的最大個(gè)數(shù).
　　設(shè)R是平面圖G中若干內(nèi)面的集合.若G有一個(gè)完美匹配M使得R中所有面的邊界都是 M-交錯(cuò)圈,則稱 R是 G的一個(gè)交錯(cuò)集.進(jìn)而,若交

3、錯(cuò)集 R中的面互不相交,則稱R是G的一個(gè)共振集.G的最大共振集的大小稱為G的共振數(shù),記作res(G).顯然。Pachter等人的結(jié)果蘊(yùn)含著F(G)≥res(G).
　　六角系統(tǒng)H是2-連通的有限平面圖,它的每個(gè)內(nèi)面都以正六邊形為邊界.H的最大共振集稱為Clar集,其大小稱為Clar數(shù),記作C l(H).鄭茂林等人證明了H去掉任意 Clar集后所剩圖有唯一完美匹配; Salem等人證明了 H去掉任意極大交錯(cuò)集后所剩圖也有唯一完美匹配

4、.結(jié)合Pachter和鄭茂林等人的結(jié)果,徐麗瓊等人證明了: H有達(dá)到強(qiáng)迫數(shù)最大值的完美匹配 M,使得 H中互不相交的M-交錯(cuò)面圈(即。M-交錯(cuò)六角形)的最大數(shù)目等于M的強(qiáng)迫數(shù);從而證明了C l(H)=F(H),并且猜想方格子圖的最大強(qiáng)迫數(shù)能在多項(xiàng)式時(shí)間內(nèi)計(jì)算出來.其中方格子圖是無限平面方格網(wǎng)上的有限連通子圖,它的每個(gè)內(nèi)面都是方格并且每條邊被包含在至少一個(gè)方格上.
　　六角系統(tǒng)H的最大交錯(cuò)集的大小稱為Fries數(shù),記作F ries(

5、H).顯然。Af(H)≥F ries(H).雷洪川等人通過證明 H有達(dá)到最大反強(qiáng)迫數(shù)的完美匹配 M使得 H中M-交錯(cuò)六角形的數(shù)目等于M的反強(qiáng)迫數(shù),證明了F ries(H)=Af(H).
　　受上述工作的啟發(fā),我們進(jìn)一步研究六角系統(tǒng)和方格子圖中完美匹配的強(qiáng)迫數(shù)、反強(qiáng)迫數(shù)與交錯(cuò)面圈個(gè)數(shù)之間的關(guān)系.
　　本論文共分為五章.第一章首先給出一些文中用到的概念、術(shù)語和記號(hào),而后從物理化學(xué)角度介紹共振集和匹配強(qiáng)迫數(shù)的提出背景并綜述相關(guān)的研

6、究進(jìn)展,最后概述我們所取得的主要結(jié)果.
　　第二章我們研究了方格子圖的最大共振集和極大交錯(cuò)集的性質(zhì),給出并證明共振數(shù)與最大強(qiáng)迫數(shù)之間的關(guān)系.具體地,我們證明了:方格子圖去掉任意最大共振集后所剩圖有唯一完美匹配;方格子圖去掉任意極大交錯(cuò)集后所剩圖也有唯一完美匹配;方格子圖的共振數(shù)等于其最大強(qiáng)迫數(shù),進(jìn)而證實(shí)了徐麗瓊等人提出的猜想.
　　第三章我們研究了六角系統(tǒng)H的最大強(qiáng)迫數(shù)和交錯(cuò)六角形個(gè)數(shù)之間的關(guān)系.通過改進(jìn)鄭茂林等人的方法,我

7、們證明了:對(duì)于 H中每個(gè)達(dá)到強(qiáng)迫數(shù)最大值的完美匹配M(即f(H。M)=F(H))。H中兩兩不交的M-交錯(cuò)六角形的最大數(shù)目等于M的強(qiáng)迫數(shù);由C l(H)=F(H)知。H有一個(gè)由M-交錯(cuò)六角形構(gòu)成的Clar集;進(jìn)而,對(duì)于H中任意F(H)個(gè)兩兩不交的M-交錯(cuò)圈,它們的內(nèi)部彼此不相交,且每個(gè)圈在H中圍成一個(gè)線性六角鏈.
　　第四章我們研究了方格子圖H中匹配強(qiáng)迫數(shù)和交錯(cuò)方格子個(gè)數(shù)之間的關(guān)系.證明了:對(duì)于H中每個(gè)達(dá)到強(qiáng)迫數(shù)最大值或次大值的完美

8、匹配M(即f(H,M)=F(H)或f(H。M)=F(H)?1)。H中兩兩不交的M-交錯(cuò)方格子的最大數(shù)目等于M的強(qiáng)迫數(shù);當(dāng)f(H,M)=F(H)時(shí)。H中任意f(H,M)個(gè)兩兩不交的M-交錯(cuò)圈彼此有不相交的內(nèi)部,且每個(gè)圈在H中圍成一個(gè)鋸齒形鏈.
　　第五章我們研究了六角系統(tǒng) H中匹配反強(qiáng)迫數(shù)和交錯(cuò)六角形個(gè)數(shù)之間的關(guān)系.證明了:對(duì)于H中每個(gè)達(dá)到反強(qiáng)迫數(shù)最大值或次大值的完美匹配M(即af(H。M)=Af(H)或 af(H。M)=Af(H)