繁星樹線圖的完美匹配數

葉銀珠,陳海燕

(集美大學理學院,福建 廈門 361021)

圖的完美匹配不僅在圖論和計算科學中起著重要的作用,而且在統計物理和量子化學中占有重要的地位.在統計物理中,完美匹配被稱為dimer構型[1],在量子化學中,完美匹配被稱為Kekulé結構[2-4].眾所周知,計算圖的完美匹配數是一個NP-hard問題[5-7],受到學者高度的關注.

給定一個圖G=(V,E),圖G的線圖用L(G)表示,是頂點集V(L(G))=E(G)的圖,其中L(G)中的頂點e和f相鄰當且僅當e和f是G中相鄰的邊.Sumner[8]和Vergnas[9]證明了每個具有偶數個頂點的連通無爪圖至少有一個完美匹配.因為每個線圖都是無爪的,所以具有偶數條邊的連通圖的線圖一定有完美匹配.Dong等[10]給出了偶數條邊樹的線圖完美匹配數表達式.本文主要利用此表達式來確定一類繁星樹線圖的完美匹配數的最大值和最小值.

令G=(V,E)是頂點數為n,邊數為m的圖,對于v∈V,v的度表示為dG(v)或d(v).若dG(v)=1,則頂點v稱為G的懸掛點,其關聯的邊稱為懸掛邊.邊子集M?E稱為G的一個匹配,如果M中沒有兩條邊關聯同一個頂點.一個匹配M稱為G的一個完美匹配,如果G的每個頂點都與M中的一條邊相關聯.G的完美匹配數用M(G)表示.對任意圖G,令p(G)表示G的具有偶數條邊的分支數.令S1,k表示k+1個頂點的星形樹.一棵樹T被稱為繁星,如果它可以通過在一棵星形樹的懸掛點添加懸掛邊得到.

給定任何非負整數k,定義

(2k)!!=(2k-1)!!=(2k-1)(2k-3)…3·1,

其中0!!=(-1)!!=1.

引理1[10]設T是頂點集為{v1,v2,…,vn}的一棵樹,其中n>1且為奇數,那么

1 繁星樹線圖的完美匹配數

圖1 星和繁星Fig.1 Star and blossomed star

定理1設k和l是兩個正整數,對任意T=T(t1,t2,…,tk)∈Tk,l有

其中r表示t1,t2,…,tk中偶數的個數.

證明?v∈V(T),很顯然若dT(v)≤2,則p(T-v)!!=1.因此只需要考慮p(T-u)和p(T-vi)(i=1,2,…,k).T-u有k個分支,每個分支的邊數分別為t1,t2,…,tk,所以p(T-u)=r.T-vi有ti+1個分支,其中ti個為孤立點,剩下的一個分支有l+k-ti-1條邊,所以

由引理1得

證畢.

2 繁星樹線圖完美匹配數的最小值

πi,j(T(t1,…,ti,…,tj,…,tk))=

T(t1,…,ti-2,…,tj+2,…,tk),ti≥2;

θi,j(T(t1,…,ti,…,tj,…,tk))=

T(t1,…,ti-1,…,tj+1,…,tk),ti≥1.

(i) 若ti與tj有同樣的奇偶性,則

M(L(T))≥M(L(πi,j(T))).

(ii) 若ti與tj有不同的奇偶性,則

M(L(T))≥M(L(θi,j(T))).

證明對(i),由πi,j的定義和定理1易得

(1)

當ti和tj都是偶數時,式(1)等于

當ti和tj都是奇數時,式(1)等于

所以只要ti與tj同奇偶,都有

M(L(T))≥M(L(πi,j(T))),

(i)得證.

對(ii),由θi,j的定義和定理1可得

(2)

當ti為偶數,tj為奇數時,式(2)等于

當ti為奇數,tj為偶數時,式(2)等于

因此M(L(T))≥M(L(θi,j(T))).(ii)得證.

令

?i,j,|ti-tj|≤2}.

0≤x≤k-b且與k-b同奇偶};

當b+x1-x3=k,即c=a+1,這時

M(L(T*))=f(x)=

M(L(T*))=f(x)=

證明注意到k+l是偶數,由l=ka+b得,當a是偶數時,k-b一定是偶數,當a是奇數時,b一定為偶數.所以由引理3和定理1,結論馬上得證.

(i) 若a是偶數,

M(L(T))≥

(ii) 若a是奇數,

M(L(T))≥

(i) 當a是偶數時,由引理4,當0≤x

所以當0≤a≤k-b時,x=a是f(x)在其定義域內的最小值點,即

(ii) 當a是奇數時,由引理4,當0≤x

所以當a≥k-1時,f(x)在整個定義域上是增函數.

當b-1≤a≤k-1,

當a≤b-1,

結論得證.

3 繁星樹線圖完美匹配數的最大值

φi,j(T(t1,…,ti,…,tj,…,tk))=

T(t1,…,ti+tj,…,0,…,tk),ti,tj≥1.

證明令r,r′分別表示T-u,φi,j(T)-u中偶數條邊的分支個數,則由φ-變換的定義得

所以由定理1可得,

因此M(L(T))≤M(L(φi(T))).結論得證.

定理4設k和l是兩個正整數,對任意T=T(t1,t2,…,tk)∈Tk,i,有

M(L(T(t1,t2,…,tk)))≤

注：定理3和定理4證明過程中借助了一系列變換,但這些變換不是嚴格單調的,除了證明中給出的繁星達到最值外,還可能存在其他繁星達到最值,因此存在下面的問題.

問題：分別確定出定理3和定理4中等號成立的所有極圖.