馬海成， 攸曉杰

青海民族大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，西寧 810007

本文僅考慮有限無向的簡單圖． 設(shè)G是有n個點的圖． 若G的一個生成子圖的每個分支是一個孤立點或者一條邊, 則稱此生成子圖為G的一個匹配． 恰有k條邊的匹配稱為k-匹配． 飽和了G的所有頂點的匹配稱為G的完美匹配, 圖G的完美匹配的個數(shù)記為pm(G)． 文獻(xiàn)[1]定義了圖G的匹配多項式為

(1)

這里W=(x,y),x和y分別是點和邊的權(quán)重,p(G,k)是G的所有k-匹配的數(shù)目, 且約定p(G, 0)=1． 假如令y=-1, 我們便得到文獻(xiàn)[2]中定義的匹配多項式

(2)

(1),(2)式互相確定, 本文使用(2)式為圖G的匹配多項式, 并將μ(G,x)簡記為μ(G)． 匹配多項式在數(shù)學(xué)、 統(tǒng)計物理和化學(xué)中都有很重要的應(yīng)用． 在統(tǒng)計物理領(lǐng)域, 匹配多項式是描述一種物理系統(tǒng)的數(shù)學(xué)模型, 首先由文獻(xiàn)[3]引入． 在理論化學(xué)領(lǐng)域, 匹配多項式的根的絕對值之和稱為該圖的匹配能量, 與這個圖所表示的芳香烴的活性有關(guān)[4]． 匹配多項式的所有系數(shù)的絕對值之和(即所有匹配的總數(shù))就是這個圖表示的碳?xì)浠衔锏腍osoya指標(biāo), 與這個化合物的沸點有關(guān)[5]． 匹配多項式是一種組合計數(shù)多項式, 它與圖的特征多項式、 色多項式和其他多項式有許多聯(lián)系[6-9]． 對于給定的圖, 計算這個圖的匹配多項式是一個困難的問題, 文獻(xiàn)[10-13]計算了許多圖的匹配多項式． 關(guān)于Hosoya指標(biāo)的研究可參見文獻(xiàn)[14], 關(guān)于匹配多項式對圖的刻畫的研究可參見文獻(xiàn)[15-19]． 截至目前, 還有許多基本圖的匹配多項式仍然未知, 如本文所涉及的柱面和M?bius帶, 這是兩個較為基本的圖, 但其匹配多項式未知． 作為對匹配多項式研究的補充, 本文給出了這兩個圖的匹配多項式, 并計算了這些圖上的完美匹配的個數(shù)．

設(shè)G=(V(G),E(G))是一個簡單圖,V(G)是其頂點集,E(G)是其邊集, 其中E(G)的每一個元素是V(G)上的無序?qū)? 稱為一條邊． 如果e∈E(G), 以Ge表示從圖G中刪除邊e后得到的圖． 如果v∈V(G), 以Gv表示刪去點v以及與之相關(guān)聯(lián)的所有邊后得到的圖． 以Pn,Cn分別表示n個點的路、 圈． 給兩條n個點的路, 其頂點從左向右分別標(biāo)記為1,2,…,n和1′,2′,…,n′, 將這兩條路上的點i和i′(i=1,2,…,r)分別用一條邊連接, 得到的圖記為Ln,r(見圖1)． 把Ln,n稱為梯子, 簡記為Ln． 將圖Ln,r的頂點1和n, 1′和n′分別用一條邊連接得到的圖記為Zn,r,Zn,n稱為柱面, 簡記為Zn． 將圖Ln,r的頂點1和n′, 1′和n分別用一條邊連接得到的圖記為Mn,r,Mn,n稱為M?bius帶, 記為Mn(見圖2)． 從梯子Ln中刪去點n后得到的圖記為Sn(見圖3)． 設(shè)G和H是兩個點不交的圖, 定義圖G和H的乘積圖為G×H, 其頂點集為V(G)×V(H), 兩個點(u1,v1),(u2,v2)∈V(G×H)在圖G×H中鄰接當(dāng)且僅當(dāng)u1=u2,v1與v2在圖H中鄰接, 或u1與u2在G中鄰接,v1=v2． 于是, 梯子Ln,n=Pn×P2, 柱面圖Zn,n=Cn×P2．

圖1 圖Ln,r

圖2 圖Zn,n和Mn,n

圖3 圖Sn

1 柱面和M?bius帶的匹配多項式

引理1[9]設(shè)圖G有k個連通分支:G1,G2,…,Gk, 則

μ(G,x)=μ(G1,x)μ(G2,x)…μ(Gk,x)

引理2[9]設(shè)G是一個圖,u∈V(G),e=uv∈E(G), 則:

(ii)μ(G,x)=μ(Ge,x)-μ(G{u,v},x)．

引理3[9]

引理4[14]設(shè)G是有n個點的圖, 則

其中i是復(fù)數(shù)單位,i2=-1．

定理1

證對Ln的邊e=(n-1,n)、Sn的邊e′=((n-1)′,n′)使用引理2, 便得到(3)式的前兩個式子． 為了使(3)式的系數(shù)矩陣是一個方陣, 我們填上第3個式子．

(3)

令(3)式的系數(shù)矩陣為

設(shè)矩陣A的特征多項式為

f(λ)=λ3-d1λ2+d2λ-d3

(4)

其中d1=μ(P2)-1=x2-2,d2=-μ(P2)+2μ(P1)2-1=x2,d3=1．

μ(Ln)滿足遞推關(guān)系式

μ(Ln)=d1μ(Ln-1)-d2μ(Ln-2)+d3μ(Ln-3)

(5)

初始條件為

μ(L0)=1μ(L1)=μ(P2)=x2-1μ(L2)=μ(C4)=x4-4x2+2

(6)

因為(5)式的變量為t的生成函數(shù)

且

由生成函數(shù)的定義, 定理 1得證．

定理2

其中μ(L0,0)=1．

證對Ln,r的邊er=(r,r′),er-1=(r-1, (r-1)′),…,e1=(1, 1′)依次使用引理2(ii), 便得到下列式子:

μ(Ln,r)=μ(Ln,r-1)-μ(Lr-1,r-1)(μ(Pn-r))2

μ(Ln,r-1)=μ(Ln,r-2)-μ(Lr-2,r-2)(μ(Pn-r+1))2

…

μ(Ln,1)=μ(P2n)=(μ(Pn))2-(μ(Pn-1))2

將以上各式相加, 得到

定理3

其中Ln-1,0=2Pn-1．

證對Zn,n的邊en=(n,n′),en-1=(n-1, (n-1)′),…,e1=(1, 1′) 依次使用引理2(ii), 便得到下列式子:

μ(Zn,n)=μ(Zn,n-1)-μ(Ln-1,n-1)

μ(Zn,n-1)=μ(Zn,n-2)-μ(Ln-1,n-2)

…

μ(Zn,1)=μ(Cn)2-μ(Pn-1)2

相加上面各式, 定理 3得證．

定理4

其中Ln-1,0=2Pn-1．

證對Mn,n的邊en=(n,n′),en-1=(n-1, (n-1)′),…,e1=(1, 1′)依次使用引理2(ii), 便得到下列式子:

μ(Mn,n)=μ(Mn,n-1)-μ(Ln-1,n-1)

μ(Mn,n-1)=μ(Mn,n-2)-μ(Ln-1,n-2)

…

μ(Mn,1)=μ(C2n)-μ(Pn-1)2

相加上面各式, 定理 4得證．

推論1(i)μ(Mn,n)-μ(Zn,n)=μ(C2n)-μ(Cn)2;

(ii)

(iii)Z(Mn,n)-Z(Zn,n)=Z(C2n)-Z(Cn)2．

證由定理3和定理4, (i)顯然．

(ii)由匹配多項式的定義知

由(i)和引理3知

當(dāng)n為奇數(shù)時, (-1)n(μ(C2n, 0)-μ(Cn, 0)2)=(-1)n((-1)n×2-0)=2．

(iii)由引理4和(i)知

推論1得證．

2 梯子、 柱面和M?bius帶的完美匹配數(shù)

推論2

證在定理1中令k2=0,x=0, 便得該表達(dá)式的常數(shù)項為

由于Ln的完美匹配數(shù)pm(Ln)等于多項式μ(Ln,x)的常數(shù)項乘(-1)n, 于是

注1很容易計算Ln的完美匹配數(shù)就是著名的斐波那契數(shù), 其前幾項的值L1,L2,L3,L4的完美匹配數(shù)分別為1,2,3,5, 與推論2計算的值是吻合的． 推論2給出了斐波那契數(shù)的另外一種表示法．

推論3(i) 當(dāng)n為偶數(shù)時,

(ii) 當(dāng)n為奇數(shù)時,

證眾所周知, 當(dāng)n=4m或n=4m+2時, 路Pn的匹配多項式的常數(shù)項為1或-1; 當(dāng)n為奇數(shù)時, 路Pn的匹配多項式的常數(shù)項均為0． 令x=0, 便得:

當(dāng)n為偶數(shù)時, 定理2中表達(dá)式的常數(shù)項為

于是

當(dāng)n為奇數(shù)時, 定理 2中表達(dá)式的常數(shù)項為

推論4(i) 當(dāng)n為偶數(shù)時,

(ii) 當(dāng)n為奇數(shù)時,

證眾所周知, 當(dāng)n=4m或n=4m+2時, 圈Cn的匹配多項式的常數(shù)項為2或-2; 當(dāng)n為奇數(shù)時, 圈Cn的匹配多項式的常數(shù)項均為0, 令x=0, 便得:

當(dāng)n為偶數(shù)時, 由推論3知, 定理3中表達(dá)式的常數(shù)項為

當(dāng)n為奇數(shù)時, 定理3中表達(dá)式的常數(shù)項為

注2容易驗證圖Z3和Z4的完美匹配數(shù)分別為4和9, 與推論4計算的值是吻合的．

推論5(i) 當(dāng)n為偶數(shù)時,

(ii) 當(dāng)n為奇數(shù)時,

證令x=0, 便得:

當(dāng)n為偶數(shù)時, 由推論3知, 定理4中表達(dá)式的常數(shù)項為

當(dāng)n為奇數(shù)時, 定理4中表達(dá)式的常數(shù)項為

注3容易驗證圖M3和M4的完美匹配數(shù)分別為6和7, 與推論5計算的值是吻合的．