許麗麗

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

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

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

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

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

1 乘積圖的Pfaffian定向

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

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

一般地，一個圖是否具有Pfaffian定向，以下幾個條件等價.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，

將矩陣A(G)進行初等變換，先將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的特征值為（它們的重數(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的所有特征值.注意到，實斜對稱矩陣的特征值要么為0，要么是虛數(shù).如果x是實斜矩陣的特征值，則它的共軛也是實斜矩陣的特征值.因此我們有

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

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