二部圖的匹配強迫數(shù).pdf

1、設(shè)G是有完美匹配的圖.若G的完美匹配M的子集S僅包含在唯一完美匹配M中，稱S是M的一個強迫集.M的最小強迫集的大小叫做M的強迫數(shù)，記作f(G，M).G的所有完美匹配的強迫數(shù)的最小值叫做G的最小強迫數(shù)，記作f(G)，而最大值叫做G的最大強迫數(shù)，記作F(G).G的所有完美匹配的強迫數(shù)的集合叫做G的匹配強迫數(shù)的譜.P.Adams等人表明對最大度是3的二部圖，最小匹配強迫集問題是NP-完全的. 圖論中的完美匹配相當于有機分子的凱庫勒結(jié)構(gòu)

2、，匹配強迫數(shù)來源于化學(xué)上凱庫勒結(jié)構(gòu)的自由度.圖論和組合數(shù)學(xué)中，有多個問題的研究出現(xiàn)了“強迫”的思想，例如圖的染色，測地集，拉丁方和區(qū)組設(shè)計等.近幾年來關(guān)于完美匹配方面的強迫概念也得到了一定的擴展，提出了全局強迫數(shù)，反凱庫勒數(shù)，反強迫數(shù)和強迫六角形等概念. 本論文分七章研究二部圖的匹配強迫數(shù)問題.我們給出了M.E.Riddle的尾點法改進，并應(yīng)用于環(huán)面六角系統(tǒng)，環(huán)面方格圖，二部克萊茵瓶六角系統(tǒng)，硼氮富勒烯，矩形方格圖和柱面方格圖等

3、圖類的強迫數(shù)求解. Riddle從Hall定理出發(fā)，通過建立二部圖顏色集的序，給出了強迫數(shù)的一個下界.在第二章中，我們改進了Riddle顏色集序的概念和最小強迫數(shù)下界的結(jié)論，給出標準序的概念，并得到自然數(shù)κ是二部圖的某個完美匹配的強迫數(shù)的必要條件，和最小強迫數(shù)等于顏色集的所有標準序尾點數(shù)最小值的充要條件. 環(huán)面六角系統(tǒng)是環(huán)面上的3-正則二部圖，其每個面都是六角形面.環(huán)面六角系統(tǒng)能夠由三元組(p，q，t)來表示(p≥1，q

4、≥1，0≤t≤p-1)，故記作H(p，q，t).在第三章中，我們用尾點法得到f(H(p，q，t))≥ min｛p,q｝，等號成立當且僅當p≤q或p>q且t=0，p-l，…，p-q.一般地，我們得到環(huán)面六角系統(tǒng)的最小強迫數(shù)等于其上可作出的最大三角形的邊長.基于此結(jié)果，我們設(shè)計了一個線性算法來計算H(p，q，t)的最小強迫數(shù). Ridlle曾研究了環(huán)面方格圖C2m×C2n的最小強迫數(shù).在第四章中，我們對C2m xC2n進行擴充，增加

5、一個旋轉(zhuǎn)參數(shù)t，定義了環(huán)面方格圖S(p，q，t)，其中p≥1，q≥1，0≤t≤p-1.與H(p，q，t)是3-正則的不同，S(p，q，t)是環(huán)面4-正則二部圖.我們得到：當p≤q時，f(S(p，q，t))=2p；當p＞q且0≤tq且p-q+1≤t≤p-1時，f(S(p，q，t))=2q；當p＞q，q≤t≤p-q時，f(s(p，q，t))等于S(p，q，t)上周長最小的特征矩形的半周長加1. 二部克萊茵瓶六角系統(tǒng)也可以

6、由一個六角格子網(wǎng)絡(luò)L上的平行四邊形P通過底邊的粘貼來生成，由兩個參數(shù)p和q確定，記為K(p，q).在第五章我們得到：若p≤q，則f(K(p，q))=p；若q2q時，q≤f(K(p，q))≤「p/2」+「q/2」。 硼氮富勒烯圖是含有六個四邊形面及若干六邊形面的3-正則平面二部圖.在第六章中，我們表明了硼氮富勒烯圖的最大強迫數(shù)與面獨立數(shù)和共振數(shù)都是相等的.利用尾點法，給出了硼氮富勒烯B1