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

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

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

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

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

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

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

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

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