三類笛卡兒積圖的完美匹配計(jì)數(shù)

許麗麗

（閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,福建漳州 363000）

設(shè)G=(V(G),E(G))，其中V(G)表示G的頂點(diǎn)集，E(G)表示G的邊集.子集M?E(G)，若M中任意兩條邊在圖G均不相鄰，則稱M是圖G的一個(gè)匹配.與M中的邊相關(guān)聯(lián)的點(diǎn)稱為被M飽和的點(diǎn).若圖G的一個(gè)匹配飽和了圖G的所有頂點(diǎn)，則稱這個(gè)匹配為完美匹配.設(shè)C是圖G的偶圈，若圖G去掉該圈C上的點(diǎn)以及與這些點(diǎn)相關(guān)聯(lián)的邊后仍存在完美匹配，則稱C是圖G的好圈.設(shè)表示圖G的一個(gè)定向，沿著一個(gè)方向在圈上走，定向與所走的方向相同的邊的數(shù)目為奇數(shù)（偶數(shù)），則稱這個(gè)圈在是奇定向（偶定向）的.若G中每一個(gè)好圈在都是奇定向的，則稱這個(gè)定向?yàn)镻faffian定向，具有Pfaffian定向的圖為Pfaffian圖.

圖的完美匹配計(jì)數(shù)問題是圖論的一個(gè)重要研究課題.基于化學(xué)家對芳香碳?xì)浠衔锏难芯?，圖的完美匹配的計(jì)數(shù)問題從20世紀(jì)中葉開始受到了化學(xué)家的高度關(guān)注，他們發(fā)現(xiàn)化合物對應(yīng)的共軛分子圖是否具有完美匹配與該化合物的穩(wěn)定性有一定的關(guān)系[1].所以研究圖的完美匹配數(shù)具有重要的理論和應(yīng)用的意義.

Valiant[2]證明了一般圖中的完美匹配計(jì)數(shù)問題是NP—完全的.Kasteleyn[3]首次提出利用Pfaffian定向的方法去計(jì)算圖的完美匹配數(shù).若G中每一個(gè)好圈在都是奇定向的，則稱這個(gè)定向?yàn)镻faffian 定向，具有Pfaffian定向的圖為Pfaffian圖.

Kasteleyn[3]證明了所有平面圖都具有Pfaffian 定向.而對于非平面圖是否具有Pfaffian 定向這個(gè)問題還是一個(gè)公開問題.晏衛(wèi)根等[4-5]證明了卡氏乘積圖C4×T,P4×T以及P3×T（Ci表示頂點(diǎn)數(shù)為i的圈，Pi表示i-1長的路，T表示存在完美匹配的樹）具有Pfaffian定向，并得到了其完美匹配計(jì)數(shù)公式.林峰根等[6]進(jìn)一步證明了C4×G（G表示單圈非二部圖）具有Pfaffian 定向，從而計(jì)算得到了它的完美匹配數(shù)的表達(dá)式.盧福良等[7]根據(jù)圖G的禁止子圖刻畫了任意圖G的卡式乘積圖G×P2n和G×C2n的Pfaffian性質(zhì).本文證明了三類乘積圖具有Pfaffian定向，并利用其斜鄰接矩陣行列式得到了它們的完美匹配數(shù)的顯示表達(dá)式.

1 乘積圖的Pfaffian定向

設(shè)圖G的頂點(diǎn)集為(v1,v2,…,v2p)，表示G的一個(gè)定向.定義的斜鄰接矩陣為，1≤i,j≤n，其中

容易看出，當(dāng)PM對應(yīng)的劃分不是圖的一個(gè)完美匹配時(shí)，Pf(A)=0；Pf(A)的非零項(xiàng)對應(yīng)圖G的完美匹配.PM的符號定義為wPM的符號.如果中所有完美匹配的符號都相同，則這時(shí)稱為Pfaffian 定向，具有該定向的圖稱為Pfaffian圖.目前仍沒有好的算法去判斷一個(gè)圖是否有Pfaffian定向.

一般地，一個(gè)圖是否具有Pfaffian定向，以下幾個(gè)條件等價(jià).

定理1[8]若圖G的頂點(diǎn)個(gè)數(shù)為偶數(shù)，是它的一個(gè)定向，下面四個(gè)條件等價(jià)：

3)圖G中每個(gè)好圈在圖都是奇定向的；

4)對于圖G中任意一個(gè)完美匹配交錯圈在圖都是奇定向的.

Muir[9]得到了斜對稱鄰接矩陣的Pfaffian與該矩陣的行列式的關(guān)系.

定理2[9]令Α=(aij)m×m為一個(gè)斜對稱矩陣，則A的行列式det(A)=(Pf(A))2.

定理3[8]若G是一個(gè)Pfaffian 圖，是G的一個(gè)Pfaffian 定向，則G的完美匹配數(shù)w(G)=|Pf(A)|=.

如果一個(gè)圖是Pfaffian圖，那么它的完美匹配數(shù)可以通過某一定向下的矩陣的行列式得到.也就是它的完美匹配計(jì)數(shù)就能在多項(xiàng)式時(shí)間內(nèi)算出.

定理4[10]若G是連通的Pfaffian 圖，T是G的生成樹，e∈E(G)是T中兩端點(diǎn)距離為偶數(shù)的邊.那么T+e的任意定向都可以擴(kuò)展為G的一個(gè)Pfaffian定向.

引理1K1,m×P2n具有Pfaffian定向.

圖1 K1,m×P2n的一個(gè)Pfaffian定向Fig.1 A Pfaffian orientation of K1,m×P2n

引理2K4×Pn具有Pfaffian定向.

圖2 K4×Pn的一個(gè)Pfaffian定向Fig.2 A Pfaffian orientation of K4×Pn

引理3若G是由有一條公共邊的兩個(gè)奇圈組成的圖，則G×P4具有Pfaffian定向.

圖3 G×P4的一個(gè)Pfaffian定向Fig.3 A Pfaffian orientation of G×P4

2 三類圖的完美匹配數(shù)

在本節(jié)中，計(jì)算了K1,m×P2n,K4×Pn和G×P4（G是由有一條公共邊的兩個(gè)奇圈組成的）的完美匹配數(shù).根據(jù)上節(jié)中所描述的Pfaffian 定向方法，給這些圖的頂點(diǎn)采用適當(dāng)?shù)臉?biāo)號方式，得到它們的斜鄰接矩陣如下所示：

其中，

將矩陣A(G)進(jìn)行初等變換，先將A(G)的分塊矩陣的第一列乘-1，然后是第三行、第四行，接著是第四列、第五列，第七行、第八行分別乘-1，繼續(xù)此操作，我們不改變行列式的絕對值，得到矩陣V,

令

那么可以得到V=-I?B+C?I，其中?表示矩陣的克羅內(nèi)克積，I表示單位矩陣.如果B的特征值為x1,x2,…,xm，C的特征值為y1,y2,…,yt.那么可以得到V的特征值為yj-xi,i=1,2,…,m;j=1,2,…,t.所以V的行列式為.

可以得到這幾類乘積圖的斜對稱矩陣的特征值：

1)若G是K4×Pn，那么B的特征值為（它們的重?cái)?shù)都是2）；

2)若G是K1,m-1×P2n，那么B的特征值為；

3)矩陣C的特征值為2cos((kπ)/(t+1)),(k=1,2,…,t)[11].

因此可以得到下面的結(jié)果.

定理5K4×Pn,K1,m×P2n的完美匹配數(shù)可以表示為

其中xi(i=1,…,s)是G的所有特征值.注意到，實(shí)斜對稱矩陣的特征值要么為0，要么是虛數(shù).如果x是實(shí)斜矩陣的特征值，則它的共軛也是實(shí)斜矩陣的特征值.因此我們有

其中x*(G)是A(G)的所有特征值的非負(fù)虛部的集合.所以可以得到定理6.

定理6如果G由具有一條公共邊的兩個(gè)奇圈組成的圖，那么w(G×P4)=,其中x的取值范圍為A(G)的所有特征值的非負(fù)虛部.