線性亞苯基系統(tǒng)的強迫和反強迫多項式

鄧 凱

(北方民族大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,寧夏銀川 750027)

§1 引言

設(shè)G是一個無向圖,V(G)和E(G)分別表示圖G的頂點集和邊集.圖G中任一沒有公共端點的邊集合或獨立邊集合,稱作是圖G的一個匹配,覆蓋了圖G的所有頂點的匹配叫做圖的完美匹配.完美匹配在資源優(yōu)化安排,理論化學(xué)中Kekul′e結(jié)構(gòu),統(tǒng)計力學(xué)中Dimer模型等方面都有重要的應(yīng)用,是圖論中一個基本的研究對象.文獻[1]系統(tǒng)的總結(jié)了匹配理論的發(fā)展結(jié)果.

圖的完美匹配強迫問題源自理論化學(xué)研究.化學(xué)實驗證實穩(wěn)定的苯類碳?xì)浠衔镏刑继茧p鍵的集合是其分子圖中的一個完美匹配,化學(xué)家稱其為Kekul′e結(jié)構(gòu).1987年,Klein和Randi′c[2]發(fā)現(xiàn)共軛分子中一個Kekul′e結(jié)構(gòu)的部分雙鍵固定后其它雙鍵的分配是唯一確定的,他們將確定一個Kekul′e結(jié)構(gòu)所需固定的最少雙鍵數(shù)目稱為該Kekul′e結(jié)構(gòu)的內(nèi)自由度.1991年,Harary等[3]將共軛分子圖上Kekul′e結(jié)構(gòu)的內(nèi)自由度概念拓展到一般圖的完美匹配上,稱為完美匹配的強迫數(shù).

設(shè)M是圖G的一個完美匹配,子集S ?M稱作是M的強迫集,如果S不被G中其它完美匹配所包含,也就是說,S作為M的內(nèi)部子結(jié)構(gòu)決定了M.M的最小強迫集的勢稱作M的強迫數(shù),記為f(G,M).圖G的所有完美匹配強迫數(shù)的最小值和最大值分別稱為G的最小強迫數(shù)和最大強迫數(shù),分別記為f(G)和F(G).完美匹配強迫數(shù)的計算十分困難,Adams等[4]證明了求解最大度為3的二部圖中完美匹配的強迫數(shù)是NP-完全的,Afshani等[5]進一步證明了求解最大度為4的二部圖的最小強迫數(shù)是NP-完全的,而圖的最大強迫數(shù)的計算復(fù)雜性仍然未知.徐麗瓊,邊紅和張?；鵞6]證實了六角系統(tǒng)的最大強迫數(shù)等于其Clar數(shù),六角系統(tǒng)是苯類碳?xì)浠衔锏姆肿訄D,Clar數(shù)是六角系統(tǒng)中最多可能的共振苯環(huán)個數(shù),反映了分子的穩(wěn)定性.

圖中完美匹配數(shù)目通常是指數(shù)多的,實際上一般圖的完美匹配計數(shù)問題是#P-完全的[1].一個自然的問題是圖中所有完美匹配的強迫數(shù)如何分布? Adams等[4]首先提出了圖G的強迫譜,它是G中所有完美匹配強迫數(shù)的集合(不考慮重數(shù)),記為Specf(G).進一步考慮強迫譜中強迫數(shù)的重數(shù)是對強迫數(shù)分布的完整研究,為此張和平等[7]定義了圖G的強迫多項式

其中w(G,i)表示圖G中強迫數(shù)等于i的完美匹配數(shù)目.

設(shè)M(G)表示圖G中所有完美匹配的集合,M是圖G的一個完美匹配,則公式(1)可改寫為

圖的強迫多項式完整地反映了完美匹配強迫數(shù)的分布情況,蘊含了圖的完美匹配計數(shù),圖的強迫譜,強迫數(shù)的重數(shù)計算等困難問題.目前僅有一些零星的特殊圖類的強迫多項式是已知的,例如cata-型六角系統(tǒng)[7],平行四邊形六角系統(tǒng)[8],方格子圖P3×P2k[9],芘系統(tǒng)[10]等.

2007年,Vukiˇcevi′c和Trinajsti′e[11]從完美匹配強迫問題的反面考慮,提出了圖的反強迫數(shù),它是從圖中刪邊使得到的圖有唯一的完美匹配所需要刪除的最少邊數(shù).Klein與Rosenfeld[12],雷洪川,葉永南與張和平[13]分別以不同的方式,進一步提出了單個完美匹配的反強迫數(shù).設(shè)M是圖G的一個完美匹配,子集S′ ?E(G)M稱作是M的反強迫集,如果M是圖G ?S′中唯一的完美匹配,也就是說,S′從M的外部確定了M.M的最小反強迫集的勢稱作M的反強迫數(shù),記為af(G,M).圖G中所有完美匹配強迫數(shù)的最小值和最大值分別稱為G的最小反強迫數(shù)和最大反強迫數(shù),分別記為af(G)和Af(G).因此,圖的反強迫數(shù)就是圖的最小反強迫數(shù).鄧凱與張和平[14]證明了確定最大度為4的二部圖中完美匹配的反強迫數(shù)是NP-完全問題,而圖的最小和最大反強迫數(shù)的計算復(fù)雜性仍然未知.六角系統(tǒng)的最大反強迫數(shù)也被證實等于其Fries數(shù)[13],Fries數(shù)是六角系統(tǒng)中最多可能的交錯六角形的個數(shù),它也是反映分子穩(wěn)定性的指標(biāo).

圖G的反強迫譜定義為G中所有完美匹配反強迫數(shù)的集合,記作Specaf(G)[13].反強迫多項式[15]的概念也被提出,它是反映圖G中所有完美匹配反強迫數(shù)分布的計數(shù)多項式,定義為

其中u(G,i)表示圖G中反強迫數(shù)等于i的完美匹配數(shù)目.

公式(3)可改寫為

目前僅有幾類特殊圖的反強迫多項式是已知的,例如最小強迫數(shù)為1的極值六角系統(tǒng)[15],平面方格子圖P3×P2k[9],芘系統(tǒng)[10]等.

本文將計算線性亞苯基系統(tǒng)的強迫多項式和反強迫多項式,并給出它們精確的表達式.

§2 預(yù)備知識

亞苯基系統(tǒng)是由苯環(huán)和環(huán)丁二烯交錯構(gòu)成的[16],其分子圖由六邊形和四邊形交替串聯(lián)生成,其中六邊形僅與四邊形相鄰,且一個四邊形恰好與兩個六邊形相鄰.內(nèi)對偶圖是一條直線段的亞苯基系統(tǒng)叫做線性亞苯基系統(tǒng),含有n個苯環(huán)的線性亞苯基系統(tǒng)記為Ln(見圖1).

圖1 含有n個苯環(huán)的線性亞苯基系統(tǒng)Ln

設(shè)M是圖G的一個完美匹配,G中的一個圈C稱作是M-交錯圈,如果C中的邊在M和E(G)M中交替出現(xiàn).設(shè)Φ(Ln)表示線性亞苯基系統(tǒng)Ln中完美匹配數(shù)目,則有下面的遞推關(guān)系.

定理2.1Φ(Ln)=2Φ(Ln?1)+Φ(Ln?2),其中n ≥2,Φ(L0)=1,Φ(L1)=2.

證L0代表空圖,可定義Φ(L0)=1.L1表示一個苯環(huán),所以Φ(L1)=2.當(dāng)n ≥2時,設(shè)M ∈M(Ln),分兩種情形討論(見圖1).

情形1Ln中左邊第一個六邊形h1是M-交錯圈.從Ln中刪去h1的6個頂點,得到一個含有n?1個苯環(huán)的線性亞苯基系統(tǒng)Ln?1.此時M在Ln?1上的限制是Ln?1的一個完美匹配,且h1形成M-交錯圈的方式有2種,所以這類完美匹配的個數(shù)為2Φ(Ln?1).

情形2h1不是M-交錯圈.此時{v3v4,u3u4} ?M,且由六邊形h1,h2和四邊形s1生成的線性亞苯基L2的邊界是M-交錯圈.從Ln中刪去h1,h2的12個頂點,得到一個含有n ?2個苯環(huán)的線性亞苯基系統(tǒng)Ln?2,且M在Ln?2上的限制是Ln?2的一個完美匹配,所以這類完美匹配的個數(shù)為Φ(Ln?2).

綜上所述,線性亞苯基系統(tǒng)Ln中完美匹配數(shù)目Φ(Ln)=2Φ(Ln?1)+Φ(Ln?2).

利用定理2.1的遞推關(guān)系,容易得到下面的顯式表達式.

推論2.1Φ(Ln)=

令c(M)表示圖G中相互不交M-交錯圈或獨立M-交錯圈的最大個數(shù).Pachter和Kim證明了下面的極大極小定理.

定理2.2[17]設(shè)G是平面二部圖,M是G的一個完美匹配,則f(G,M)=c(M).

平面圖的一個內(nèi)面的邊界稱作是面圈,張和平與張?；C明了下面的結(jié)論.

定理2.3[18]設(shè)M是平面基本二部圖G的一個完美匹配,C是G的一個M-交錯圈,則C的內(nèi)部包含一個M-交錯面圈.

推論2.2設(shè)M是線性亞苯基系統(tǒng)Ln的一個完美匹配,則存在一個勢最大的獨立M-交錯圈集合A,且A中僅包含面圈.

證設(shè)A是Ln中一個勢最大的獨立M-交錯圈集合,且A中包含盡可能多的面圈,則A中僅包含面圈.假設(shè)A包含一個非面圈C,即C既不是六邊形也不是四邊形.Ln是平面基本二部圖,根據(jù)定理2.3,C的內(nèi)部包含一個面圈f.因為Ln是外平面圖,所以A中任意兩個M-交錯圈一個不能在另一個的內(nèi)部.因此(A{C})∪{f}也是一個勢最大的獨立M-交錯圈集合,但是它所包含的面圈比A多一個,這與A中包含面圈個數(shù)的最大性矛盾.

線性亞苯基的面圈只能是六邊形或四邊形,根據(jù)定理2.2和推論2.2,可直接得到下面的推論.

推論2.3設(shè)M是線性亞苯基系統(tǒng)Ln的一個完美匹配,則M的強迫數(shù)等于不交的M-交錯六邊形和M-交錯四邊形的最大個數(shù).

設(shè)M是圖G的一個完美匹配,G中的兩個M-交錯圈稱作是相容的,如果它們不交或僅交于M中邊.令c′(M)表示G中最多可能的相容M-交錯圈的個數(shù),對平面二部圖有下面的極大極小定理.

定理2.4[13]設(shè)M是平面二部圖G中的一個完美匹配,則af(G,M)=c′(M).

設(shè)M是平面圖G中的一個完美匹配,M-交錯圈集A′稱作是相容的,如果A′中任意兩個M-交錯圈都是相容的.相容M-交錯圈集A′中兩個圈C1和C2稱作是交叉的,如果C1和C2有一條M中的公共邊e,且C1經(jīng)由邊e進入C2的內(nèi)部.如果A′中任意兩個圈都不是交叉的,那么稱其為非交叉的相容M-交錯圈集.例如,圖2中的粗邊集合M是亞苯基L2的一個完美匹配,M-交錯圈C1:=v1v2v3v4u4u3u2u1v1和C2:=v3v4v5v6u6u5u4u3v3是兩個交叉的相容M-交錯圈,而L2的邊界和四邊形s是兩個非交叉的相容M-交錯圈.文獻[13]中定理3.1的證明引入了把六角系統(tǒng)的交叉相容交錯圈集轉(zhuǎn)化為勢相同的非交叉相容交錯圈集的方法,文獻[19]指出該方法對平面二部圖也成立,結(jié)合定理2.4,有下面的推論.

圖2 亞苯基L2,粗邊的集合是一個完美匹配

推論2.4設(shè)M是平面二部圖G的一個完美匹配,A′是勢最大的非交叉相容M-交錯圈集,則af(G,M)=|A′|.

為了敘述方便,下面將形如圖2中亞苯基L2的邊界交錯圈稱為L2-型交錯圈.

推論2.5設(shè)M是線性亞苯基系統(tǒng)Ln的一個完美匹配,則Ln中有一個勢最大的非交叉相容M-交錯圈集A′,且A′中的圈要么是面圈,要么是L2-型交錯圈.

證設(shè)A′是Ln中勢最大的非交叉相容M-交錯圈集,且包含盡可能多的面圈和L2-型交錯圈,則A′中的圈要么是面圈,要么是L2-型交錯圈.假設(shè)C′ ∈A′是一個非面圈,根據(jù)定理2.3,C′的內(nèi)部包含一個M-交錯面圈s.如果C′與s不相容,那么(A′{C′})∪{s}仍然是Ln的一個勢最大的非交叉相容M-交錯圈集,但是它比A′多包含1個面圈,與A′包含面圈個數(shù)的最大可能性矛盾.因此C′與s必然相容,所以s是一個四邊形,且s與相鄰的兩個六邊形h1和h2生成的一個亞苯基L2的邊界B(L2)是L2-型交錯圈,如圖2所示.我們斷言C′=B(L2),否則(A′ {C′})∪{B(L2)}仍然是Ln的一個勢最大的非交叉相容M-交錯圈集,但是它比A′多包含1個L2-型交錯圈,與A′包含L2-型交錯圈個數(shù)的最大可能性矛盾.

注意到Ln中任意兩個M-交錯面圈都是相容的,而且任意一個M-交錯面圈都與任何一個L2-型交錯圈相容.根據(jù)推論2.4和2.5,可推出下面的結(jié)果.

推論2.6設(shè)M是線性亞苯基系統(tǒng)Ln的一個完美匹配,則M的反強迫數(shù)等于Ln中所有M-交錯面圈和L2-型交錯圈總個數(shù).

§3 線性亞苯基系統(tǒng)的強迫多項式

定理3.1線性亞苯基系統(tǒng)Ln的強迫多項式滿足遞推關(guān)系

根據(jù)推論2.1和定理3.3,可推出下面反映自由度漸近行為的結(jié)論.

推論3.2設(shè)Ln是含有n個苯環(huán)的線性亞苯基系統(tǒng),則

§4 線性亞苯基系統(tǒng)的反強迫多項式

定理4.1線性亞苯基系統(tǒng)Ln的反強迫多項式滿足遞推關(guān)系

根據(jù)推論2.1和定理4.3,可得到下面關(guān)于反自由度漸近行為的結(jié)果.

推論4.2設(shè)Ln是含有n個苯環(huán)的線性亞苯基系統(tǒng),則

根據(jù)定理3.3和定理4.3,可得到下面反自由度對于自由度的漸近行為.

推論4.3設(shè)Ln是含有n個苯環(huán)的線性亞苯基系統(tǒng),則