用秩1矩陣矯正法計算兩類圖的生成樹數

雷玉娟,楊維玲

(廈門大學數學科學學院,福建 廈門 361005)

Kirchhoff矩陣樹定理[1-2]給出了連通圖的生成樹數和Laplacian矩陣的代數余子式之間的關系[1],進一步,賦權的Kirchhoff矩陣樹定理[1-2]給出了賦權連通圖的生成樹數與賦權Laplacian矩陣代數余子式之間的關系[1-2].然而一個矩陣的代數余子式并不容易計算, Klee等[3]利用Kirchhoff矩陣樹定理和矩陣行列式引理,將Laplacian矩陣加上一個秩為1的矩陣,得到了新的矩陣行列式和生成樹數之間的關系[3], 隨后他們把這個結果擴展到賦權圖上[4], 并計算出了一些特殊圖的生成樹數.

1 預備知識

首先回顧一些符號和定義.

本文所提到的圖均指沒有環(huán)、可以有平行邊的無向有限圖,對于圖G,用V(G)和E(G)分別表示圖G的點集和邊集,|V(G)|和|E(G)|分別表示頂點數和邊數.對于e∈E(G),G-e表示G刪除邊e得到的圖,G/e表示G收縮邊e、刪除環(huán)后得到的圖, 對于?F?E(G),G/F表示G收縮掉F的邊集、刪除環(huán)后得到的圖,這些表示在很多圖論相關的書中都可查詢到,比如參考文獻[5].

對于簡單賦權圖(G;ω),這樣定義函數ω:V(G)×V(G)→R,?vi、vj∈V(G),若vivj∈E(G)且ω(vi,vj)=ω(vj,vi),定義ωi,j=ω(vi,vj)為圖G中邊vivj的權,若vivj?E(G),則定義ωi,j=0.定義頂點vi∈V(G)的權值如下:

此時賦權圖(G;ω)的賦權Laplacian矩陣L(G;ω)是一個V(G)×V(G)的對稱陣,第i行、第j列的元素定義如下:

從上述定義易知,賦權的Laplacian矩陣是奇異的,因為這個矩陣的所有行加起來的和為0,然而它的代數余子式在計算賦權生成樹數時有下面的表達式.

定理1(賦權的矩陣樹定理)[1-2]令G是一個點集為V(G)={v1,v2,…,vn}、邊權函數為ω的簡單圖,對任意的頂點vi、vj∈V(G),允許i=j,以下式成立:

(-1)i+jdet(L(G;ω)i,j),

(1)

由τ(G;ω)的定義可知,方程(1)的左邊就是τ(G;ω),即為圖(G;ω)的賦權生成樹數. 對于沒有環(huán)的無權(即邊權視為1)圖G,可以自然地將其視為賦權簡單圖,其中邊的權值即為平行邊的條數,例如圖1(a)為有平行邊的無權圖K3,其對應的賦權簡單圖為圖1(b).

圖1 有平行邊的無權圖K3(a)和其對應的賦權簡單圖(b)Fig.1 Unweighted graph K3 with multiple edges (a) and its corresponding weighted simple graph K3 (b)

賦權的矩陣樹定理雖然給出了生成樹數和det(L(G;ω)i,j)之間的關系,但是det(L(G;ω)i,j)一般不好計算. 因此將利用下面的矩陣行列式引理,記矩陣M的行列式為det(M),伴隨矩陣為adj(M):

引理1(矩陣行列式引理)[6]令M是一個n階方陣,令a和b是Rn中的列向量. 那么以下等式成立:

det(M+abT)=det(M)+bTadj(M)a,

特別地,若M可逆,有det(M+abT)=det(M)[1+bTadj(M)a].

在文獻[6]中可以找到矩陣行列式引理的證明.

利用賦權的矩陣樹定理和矩陣行列式引理,Klee等[4]得到了以下引理.

引理2[4]令G是點集為V(G)、 邊賦權為ω的圖,L是G的賦權Laplacian矩陣,令a=(ai)vi∈V(G)和b=(bi)vi∈V(G)是RV(G)的列向量,那么以下式成立:

det(L+abT)=(∑vi∈V(G)ai)·

(∑vi∈V(G)bi)·τ(G;ω).

引理2的證明比較簡單,可查詢文獻[4]中的引理1,其實這個引理是文獻[3]中引理1的推廣形式.

由矩陣的知識[3]可知,abT其實就是一個秩為1的矩陣,反過來,任何秩為1的矩陣,也可以寫成abT.若det(L)不容易計算,通過取特殊的a和b,使得det(L+abT)的值比較容易計算,稱方法為秩1矩陣矯正法.賦權的矩陣樹定理雖然給出了生成樹的計算公式,但是det(L(G;ω)i,j)通常不好計算.對于某些圖,利用引理2,通過秩1矩陣矯正法,使其對應的行列式比較容易計算,進而得到其生成樹數.用秩1矩陣矯正法,Klee等[3]得到了完全圖、完全多部圖、Ferrers圖、threshold 圖的生成樹數的計算公式,進一步,Klee等[4]得出了對應賦權圖的生成樹數的計算公式.

在后面的證明過程中,還將多次用到以下引理.

det(M)=det(D)·det(A-BD-1C).

2 幾個定理

設Km,n是一個簡單完全二部無權圖,對任意的整數p≤min{m,n},記P是Km,n的維數p的匹配,運用引理2和3,就可以得到以下兩個生成樹數:τP(Km,n)和τ(Km,n-P).Ge等[7]運用電網絡的相關知識得到了這些公式,本文利用秩1矩陣校正法給出這兩個公式的簡短的新證明.

記Km,n的二部劃分點集分別為V1和V2,其中|V1|=m,|V2|=n.

定理2對Km,n任意邊數為p的任意匹配P,可以得到

τP(Km,n)=(m+n)p-1(m+n-p)mn-p-1nm-p-1.

定理3Km,n-P表示圖G刪掉邊數為p的匹配P后得到的圖,可以得到

τ(Km,n-P)=(mn-m-n+p)(mn-

m-n)mn-p-1nm-p-1.

Zhang等[8]計算了τ(Kn,n-P)=(n2-2n+p)(n-2)p-1n2n-p-3,定理3是這個結果的推廣.

3 定理的證明

記In表示n階單位陣,1m,n為元素全為1的m×n階矩陣,0m,n為元素全為0的m×n階矩陣,1n為Rn中元素全為1的列向量,0n為Rn中元素全為0的列向量.首先說明一點,對于圖G,若只是其頂點順序的標號發(fā)生變化,則變化后的圖仍與圖G同構,而同構圖的生成樹數是相等的.即上述的幾個定理的結果跟頂點的標號無關,這樣就可以對頂點的順序進行特殊的排列,得到所需的矩陣形式.

圖2 K4,5和K4,5/2K2Fig.2 K4,5 and K4,5/2K2

按照之前約定的操作方式,邊的權值等于邊的重數,可將Km,n/P變換成一個賦權的簡單圖.那么Km,n/P的Laplacian矩陣可劃分為矩陣塊:

L(Km,n/P)=

其中矩陣A為對角元素為m+n-2、其余元素為-2的p階方陣.

多次利用引理2可得

mn-p·det(nIm-p)·det(A+1p,p)=

mn-pnm-p·det(A+1p,p),

這里A+1p,p是一個對角元素為m+n-1、其余元素為-1的p階方陣,將這個矩陣所有的列都加到第一列,容易計算出det(A+1p,p)=(m+n-p)(m+n)p-1,即

mn-pnm-p(m+n-p)(m+n)p-1.

(2)

由引理2可知,

τ(Km,n/P)=mn·τ(Km,n/P).

(3)

由方程(2)和(3)可得

τP(Km,n)=τ(Km,n/P)=(m+n)p-1(m+

n-p)mn-p-1nm-p-1.

定理2證明完成.

圖3 K4,5-2K2Fig.3 K4,5-2K2

故可取圖Km,n-P的Laplacian矩陣為:

L(Km,n-P)=

其中B為對角元素為0、其余元素為-1的p階方陣.

det(mIn--p)·det(nIm-p)·

mn-pnm-p·det((m-1)Ip)·

mn-pnm-p·(m-1)pdet(C),

det(C)=(mn-m-n+p)(mn-m-

n)p-1(m-1)-p,

(4)

而由引理2可得

mn·τ(Km,n-P),

(5)

由方程(4)和(5)可得

τ(Km,n-P)=(mn-m-n+p)(mn-

m-n)mn-p-1nm-p-1.

定理3證明完成.