葉銀珠,陳海燕

(集美大學(xué)理學(xué)院,福建 廈門(mén) 361021)

圖的完美匹配不僅在圖論和計(jì)算科學(xué)中起著重要的作用,而且在統(tǒng)計(jì)物理和量子化學(xué)中占有重要的地位.在統(tǒng)計(jì)物理中,完美匹配被稱(chēng)為dimer構(gòu)型[1],在量子化學(xué)中,完美匹配被稱(chēng)為Kekulé結(jié)構(gòu)[2-4].眾所周知,計(jì)算圖的完美匹配數(shù)是一個(gè)NP-hard問(wèn)題[5-7],受到學(xué)者高度的關(guān)注.

給定一個(gè)圖G=(V,E),圖G的線圖用L(G)表示,是頂點(diǎn)集V(L(G))=E(G)的圖,其中L(G)中的頂點(diǎn)e和f相鄰當(dāng)且僅當(dāng)e和f是G中相鄰的邊.Sumner[8]和Vergnas[9]證明了每個(gè)具有偶數(shù)個(gè)頂點(diǎn)的連通無(wú)爪圖至少有一個(gè)完美匹配.因?yàn)槊總€(gè)線圖都是無(wú)爪的,所以具有偶數(shù)條邊的連通圖的線圖一定有完美匹配.Dong等[10]給出了偶數(shù)條邊樹(shù)的線圖完美匹配數(shù)表達(dá)式.本文主要利用此表達(dá)式來(lái)確定一類(lèi)繁星樹(shù)線圖的完美匹配數(shù)的最大值和最小值.

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

給定任何非負(fù)整數(shù)k,定義

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

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

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

1 繁星樹(shù)線圖的完美匹配數(shù)

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

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

其中r表示t1,t2,…,tk中偶數(shù)的個(gè)數(shù).

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

由引理1得

證畢.

2 繁星樹(shù)線圖完美匹配數(shù)的最小值

π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))).

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

(1)

當(dāng)ti和tj都是偶數(shù)時(shí),式(1)等于

當(dāng)ti和tj都是奇數(shù)時(shí),式(1)等于

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

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

(i)得證.

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

(2)

當(dāng)ti為偶數(shù),tj為奇數(shù)時(shí),式(2)等于

當(dāng)ti為奇數(shù),tj為偶數(shù)時(shí),式(2)等于

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

令

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

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

當(dāng)b+x1-x3=k,即c=a+1,這時(shí)

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

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

證明注意到k+l是偶數(shù),由l=ka+b得,當(dāng)a是偶數(shù)時(shí),k-b一定是偶數(shù),當(dāng)a是奇數(shù)時(shí),b一定為偶數(shù).所以由引理3和定理1,結(jié)論馬上得證.

(i) 若a是偶數(shù),

M(L(T))≥

(ii) 若a是奇數(shù),

M(L(T))≥

(i) 當(dāng)a是偶數(shù)時(shí),由引理4,當(dāng)0≤x

所以當(dāng)0≤a≤k-b時(shí),x=a是f(x)在其定義域內(nèi)的最小值點(diǎn),即

(ii) 當(dāng)a是奇數(shù)時(shí),由引理4,當(dāng)0≤x

所以當(dāng)a≥k-1時(shí),f(x)在整個(gè)定義域上是增函數(shù).

當(dāng)b-1≤a≤k-1,

當(dāng)a≤b-1,

結(jié)論得證.

3 繁星樹(shù)線圖完美匹配數(shù)的最大值

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

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

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

所以由定理1可得,

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

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

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

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

問(wèn)題：分別確定出定理3和定理4中等號(hào)成立的所有極圖.