恰有2個圈的雙圈圖的覆蓋花費(fèi)極小值

潘向峰

(安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601)

陳海波

(長沙市岳麓實驗中學(xué)，湖南 長沙 410208)

盧健

(安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601)

只考慮簡單連通圖G=(VG,EG)，其中G的頂點(diǎn)集為VG={u1,u2,…,un},邊集為EG={e1,e2,…,em}。若2個頂點(diǎn)相鄰，則用符合～表示。設(shè)NG(x)={u:u～x,u∈VG}為圖G當(dāng)中頂點(diǎn)x的鄰點(diǎn)集，頂點(diǎn)x的度為dG(x)=|NG(x)|。當(dāng)dG(u)=1時，稱頂點(diǎn)u是一個懸掛點(diǎn)。圖G中頂點(diǎn)x和y之間的距離為2個頂點(diǎn)間最短路的長度，記為dG(x,y)。若圖G為簡單連通圖，且有|EG|=|VG|+1，則稱圖G為雙圈圖。為了方便，在不會造成混淆時，一般會省略定義中的下標(biāo)G。

Wiener指數(shù)是基于距離提出的一個拓?fù)渲笖?shù)，定義為所有點(diǎn)對之間距離的和，即：

1 基本概念

若x∈VG,令G-x表示圖G刪去頂點(diǎn)x和所有與x相鄰的邊后得到的新圖。類似地，若X?EG，令G-X表示圖G刪去集合X中所有的邊后得到的新圖。記Cn,Pn和Sn分別為頂點(diǎn)數(shù)為n的圈，路和星圖，星圖Sn為一個中心點(diǎn)為u，余下的頂點(diǎn)皆為與u相鄰的懸掛點(diǎn)組成的圖。

圖1 恰有2個圈的雙圈圖及極圖

為了計算的簡潔，筆者引用如下類似D(x)和Dw(x)的定義:

引理1[1]設(shè)G是一個簡單連通圖，x是G的一個割點(diǎn)，a和b是刪除點(diǎn)x后分屬2個連通分支的頂點(diǎn)，則有：

rG(a,b)=rG(a,x)+rG(x,b)

引理2 設(shè)T是一個以vi為根點(diǎn)，頂點(diǎn)個數(shù)為n的樹，則對任意一點(diǎn)x∈V(T)及k≥0,取x距離根點(diǎn)vi更近的鄰點(diǎn)x′,有：

DT(x)-(n+k)dT(x,vi)

證明 設(shè)T-x包含根點(diǎn)vi的部分共有k1個點(diǎn)，不含根點(diǎn)vi的部分共有k2個點(diǎn)，顯然有k1+k2+1=n。則由定義有：

DT(x′)-(n+k)dT(x′,vi)=DT(x)-k1+k2-(n+k)(dT(x,vi)-1)

=DT(x)-(n+k)dT(x,vi)+n+k-k1+k2

>DT(x)-(n+k)dT(x,vi)

引理3[24]設(shè)G是一個連通圖，v是其一個割點(diǎn)。G1和G2是G以v為公共點(diǎn)的2個子圖，且G1∪G2=G。設(shè)n1=|VG1|,n2=|VG2|,則：

Kf(G)=Kf(G1)+Kf(G2)+(n1-1)RG2(v)+(n2-1)RG1(v)

圖2 頂點(diǎn)v的σ-變換

定義1[7]設(shè)v為圖G中一個度為p+1的頂點(diǎn)，vv1,vv2,…,vvp都是與v相鄰的懸掛邊，u是v的與頂點(diǎn)v1,v2,…,vp都不相同的鄰點(diǎn)。刪除邊vv1,vv2,…,vvp并且添上新的邊vv1,vv2,…,vvp構(gòu)造一個新圖G′=σ(G，v)，則稱圖G′是由圖G通過σ-變換得來的(如圖2)。

引理4 設(shè)G是一個頂點(diǎn)數(shù)為n≥6的簡單連通圖，G′=σ(G，v)是由圖G經(jīng)過σ-變換得到的，u是圖G的一個割點(diǎn)，H是包含頂點(diǎn)u的子圖(如圖2)。則對x∈VH，有：

RG′(x)≤RG(x)Kf(G′)≤Kf(G)

證明 由定義，有：

顯然RG′(x)≤RG(x)，等號成立當(dāng)且僅當(dāng)p=0。不失一般性，設(shè)|VH|=n1,則由引理3，有：

Kf(G)=Kf(H)+Kf(Tu)+(n1-1)Kfu(Tu)+(p+1)Kfu(H)

=Kf(H)+(p+1)Kfu(H)+2n1p+n1+p2

=Kf(H)+(p+1)Kfu(H)+n1p+n1+p2+p

于是：

Kf(G)-Kf(G′)-(n1-1)p≥0

引理5 設(shè)G是一個頂點(diǎn)數(shù)為n≥6的簡單連通圖，G′=σ(G,v)是由圖G經(jīng)過σ-變換得到的，u是圖G的一個割點(diǎn)，如圖2。設(shè)x∈{v1,v2,…,vp}，則當(dāng)p≥1時，有：

證明 不失一般性，設(shè)|H|=n1。類似引理4的證明，由定義有：

Kf(G)=Kf(H)+(p+1)Kfu(H)+2n1p+n1+p2

同時有DTu(u)=1+2p,故可得：

+4n1+4n1p+2p2+6p+1-4n

(1)

同理：

Kf(G′)=Kf(H)+(p+1)Kfu(H)+(n1+1)p+n1+p2

+3n1+2n1p+2p2+6p+2-2n

(2)

又n1+p+1=n，由式(1)減去(2)有：

Δ=n1(2p-1)-2p-3

經(jīng)過簡單計算可知，當(dāng)n1≥3,n=n1+p+1≥6時，Δ>0，從而引理5得證。

圖3 β-變換

定義2[7]設(shè)u,v是圖G的2個頂點(diǎn)，u1,u2,…,us是與u相鄰的懸掛點(diǎn)，v1,v2,…,vt是與v相鄰的懸掛點(diǎn)。圖G′和圖G″是2個由圖G通過β-變換得到的圖，具體為G′=G-{vv1,vv2,…,vvt}+{uv1,uv2,…,uvt},G″=G-{uv1,uv2,…,uvs}+{vv1,vv2,…,vvs}(如圖3)。

引理6 設(shè)G′，G″是由圖G經(jīng)過β-變換得到的，G0是G的一個子圖(如圖3)。則對x∈VG0,有RG′≤RG(x)或RG″(x)≤RG(x)，且有Kf(G′)≤Kf(G)或Kf(G″)≤Kf(G)。

證明 由定義，有：

同樣，可得：

若RG(x)-RG′(x)=tr(x,v)-tr(x,u)<0,則RG(x)-RG″(x)=s(r(x,u)-r(x,v))>0。用類似的方法可得，若Kf(G′)>Kf(G),則Kf(G″)≤Kf(G)

引理7[25]設(shè)G是一個簡單連通圖，邊數(shù)為m。則對x,y∈VG,有：

引理8[26]設(shè)T是一個邊數(shù)為m的樹，則對x∈VT,有Dw(x)=2D(x)-m。

2 主要結(jié)果

2.1 首達(dá)時間和覆蓋花費(fèi)與圖不變量之間的關(guān)系

結(jié)論1 設(shè)G是屬于B(p,l,q)中的一個雙圈圖，x是圈Cp,Cq或路Pl上的一點(diǎn)，則：

Rw(x)=2R(x)+r(x,u)+r(x,v)-(n-p-q-l+2)

證明 通過對頂點(diǎn)個數(shù)n用數(shù)學(xué)歸納法來證明。當(dāng)n=p+q+l-2時，雙圈圖G中除了頂點(diǎn)u,v的度為3，其余頂點(diǎn)的度都為2。因此：

一方面，通過引理1有：

另一方面：

結(jié)合可得：

=2RG(x)+r(x,u)+r(x,v)-(n-p-q-l+2)

更一般地，對雙圈圖B(p,l,q)上每一個點(diǎn)，可以得到以下關(guān)系。

結(jié)論2 設(shè)圖G是B(p,l,q)中的一個雙圈圖，則對x∈VTk，有:

證明 首先：

結(jié)合引理1可得：

(3)

又：

=(n-nk)dG(x,vk)+RG(vk)-DTk(vk)+DTk(x)

(4)

因此，綜合考慮式(3)、(4)以及引理9和結(jié)論1，可得：

結(jié)論3 設(shè)圖G是B(p,l,q)中的一個雙圈圖，則對x∈VTi,y∈VTj,有：

Hxy=(n+1)r(x,y)+RG(y)-RG(x)+2(dG(y,vj)-dG(x,vi))

證明 由于雙圈圖|EG|=n+1。因此由引理7及結(jié)論3可知：

=(n+1)r(x,y)+RG(y)-RG(x)+2(dG(y,vj)-dG(x,vi))

結(jié)論4 設(shè)圖G是B(p,l,q)中的一個雙圈圖，則對x∈VTi,有：

證明 由定義及結(jié)論3，有：

2.2 CC(x)在雙圈圖B(p,l,q)中的極小值

證明 首先由結(jié)論4及等式(4)可得：

CC(x)=DTi(x)-(n+ni)dG(x,vi)+RG(vi)-DTi(vi)+2Kf(G)

(5)

圖4 將懸掛點(diǎn)x變?yōu)轫旤c(diǎn)v的鄰點(diǎn)

由式(3)可知，頂點(diǎn)x的選取只與DTi(x)-(n+nTi)dG(x,vi)有關(guān)，再由引理2可知，頂點(diǎn)x為分支Ti上的懸掛點(diǎn)時，CC(x)的值將取得極小值。不失一般性，不妨設(shè)|VCq|≤|VCp|,取vi∈VCq，則由結(jié)論4及引理4，5和6可知，除Cp、Cq及路Pl上的點(diǎn)及頂點(diǎn)x外，其余頂點(diǎn)皆為同一個鄰點(diǎn)的懸掛點(diǎn)，且該共同鄰點(diǎn)在路Pl上時，CC(x)將取得極小值，這里取共同鄰點(diǎn)為v如圖4中的G1。

斷言1 設(shè)G2是將圖G1中包含x的所有懸掛點(diǎn)皆與v相鄰構(gòu)成的新圖，則CCG2(x)

設(shè)H是G1-Cq-x+v的導(dǎo)出子圖，由引理10有：

同時，由引理3有：

Kf(G1)=Kf(G-x)+1+(n-2)+RG-x(vi)

Kf(G2)=Kf(G-x)+1+(n-2)+RG-x(v)

因此:

=(2n-3q-2)r(vi,v)-3

由RG(x)和Kf(G)的定義可得：

因此：

首先由Kf(G)的定義及引理3有：

同樣由定義有：

再由結(jié)論4與引理10可得：

同理，可得：

因此：

由于3≤q≤n-2易知當(dāng)n≥14時，Δ>0。重復(fù)以上過程，即可得證。

綜上可得定理1成立。