二部圖的匹配強迫數.pdf

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

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

3、圖類的強迫數求解. Riddle從Hall定理出發(fā)，通過建立二部圖顏色集的序，給出了強迫數的一個下界.在第二章中，我們改進了Riddle顏色集序的概念和最小強迫數下界的結論，給出標準序的概念，并得到自然數κ是二部圖的某個完美匹配的強迫數的必要條件，和最小強迫數等于顏色集的所有標準序尾點數最小值的充要條件. 環(huán)面六角系統是環(huán)面上的3-正則二部圖，其每個面都是六角形面.環(huán)面六角系統能夠由三元組(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)面六角系統的最小強迫數等于其上可作出的最大三角形的邊長.基于此結果，我們設計了一個線性算法來計算H(p，q，t)的最小強迫數. Ridlle曾研究了環(huán)面方格圖C2m×C2n的最小強迫數.在第四章中，我們對C2m xC2n進行擴充，增加

5、一個旋轉參數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. 二部克萊茵瓶六角系統也可以

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