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

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

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

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

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

5、一個(gè)旋轉(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-正則二部圖.我們得到：當(dāng)p≤q時(shí)，f(S(p，q，t))=2p；當(dāng)p＞q且0≤tq且p-q+1≤t≤p-1時(shí)，f(S(p，q，t))=2q；當(dāng)p＞q，q≤t≤p-q時(shí)，f(s(p，q，t))等于S(p，q，t)上周長最小的特征矩形的半周長加1. 二部克萊茵瓶六角系統(tǒng)也可以

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