李建喜, 雷思宇

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

§1 引 言

設(shè)G=(V,E)為具有n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖,對(duì)于任意頂點(diǎn)u,v∈V(G),兩點(diǎn)間的距離d(u,v)為u和v之間的最短路徑長(zhǎng)度,還可記為dG(u,v).對(duì)v∈V(G),頂點(diǎn)v的離心率ε(v)=max{d(u,v)|u∈V(G)},圖G的直徑d(G)=max{ε(v)|v∈V(G)}.外圍頂點(diǎn)集P(G)指圖中滿足ε(v)=d(G)的頂點(diǎn)的集合.用dG(x)記為在G中頂點(diǎn)x到其余頂點(diǎn)的距離和,即.用W(G)表示圖G的Wiener指標(biāo),PW(G)表示圖G的外圍Wiener指標(biāo).對(duì)于圖G中的割邊e∈E(G),分別用n1(e),n2(e)表示G中分布在邊e兩側(cè)的頂點(diǎn)數(shù)目,p1(e),p2(e)分別表示G中分布在邊e兩側(cè)的外圍頂點(diǎn)數(shù)目;若e∈E(G)且邊e不為G的割邊時(shí),規(guī)定分布在邊e兩側(cè)的頂點(diǎn)數(shù)目分別為0.用|G|表示圖G中頂點(diǎn)的數(shù)目.頂點(diǎn)數(shù)目和邊數(shù)目相同的簡(jiǎn)單連通圖稱為單圈圖.

圖的Wiener指標(biāo)是由著名的化學(xué)家Wiener在1947年首次提出的基于距離不變量的一種拓?fù)渲笜?biāo),其與圖的結(jié)構(gòu)性質(zhì)之間有著密切的聯(lián)系,相關(guān)結(jié)果和進(jìn)展可參見文獻(xiàn)[1-4].圖G的Wiener指標(biāo)在文獻(xiàn)[1]被定義為圖中所有不同頂點(diǎn)對(duì)間的距離之和,即

而外圍Wiener指標(biāo)是Wiener指標(biāo)的一部分,是2017年由K.P.Narayankar和S.B.Lokesh在文獻(xiàn)[5]中在Wiener指標(biāo)的基礎(chǔ)上首次提出.其定義為圖G中所有不同外圍頂點(diǎn)對(duì)間的距離之和,即

文獻(xiàn)[6]研究了簡(jiǎn)單連通圖的Wiener指標(biāo)和外圍Wiener指標(biāo)的差的上界和下界;文獻(xiàn)[7]主要探究了樹圖的外圍Wiener指標(biāo),得到了樹圖外圍Wiener指標(biāo)的上界和下界,還有當(dāng)給定外圍頂點(diǎn)數(shù)目和直徑時(shí)樹圖的外圍Wiener指標(biāo)的上界和下界.在文獻(xiàn)[7]中求樹圖的外圍Wiener指標(biāo)的上下界時(shí)用得更多的公式不是定義式,而是求和每條邊對(duì)Wiener指標(biāo)貢獻(xiàn)的一個(gè)式子,一條邊對(duì)Wiener指標(biāo)的貢獻(xiàn)是指在這條邊的一側(cè)的所有頂點(diǎn)到另外一側(cè)的所有頂點(diǎn)的距離之和中,該條邊被經(jīng)過的次數(shù).因?yàn)闃鋱D中任意邊都是割邊,所以其貢獻(xiàn)為分布在其兩側(cè)的頂點(diǎn)數(shù)目的乘積,即

這個(gè)式子是由文獻(xiàn)[1]中樹圖的Wiener指標(biāo)的計(jì)算公式

而導(dǎo)出的.

文獻(xiàn)[8]給出了一個(gè)關(guān)于單圈圖Wiener指標(biāo)的計(jì)算公式,且刻畫出了最大,最小,次大,次小,第三大,第三小的Wiener指標(biāo)的單圈圖的特征.這個(gè)公式主要是通過對(duì)頂點(diǎn)的分類而得到的,其形式較為復(fù)雜,且沒有獲得相應(yīng)外圍Wiener指標(biāo)的計(jì)算公式.本文將通過將單圈圖的邊分成兩類(圈上的邊和不在圈上的邊),分別考察這兩類邊對(duì)其Wiener指標(biāo)的貢獻(xiàn),從而得到一個(gè)形式相對(duì)簡(jiǎn)潔的單圈圖的Wiener指標(biāo)的計(jì)算公式,同時(shí)也獲得單圈圖的外圍Wiener指標(biāo)的計(jì)算公式.其形式類似于樹圖上的(外圍)Wiener指標(biāo)的計(jì)算公式.

§2 主要結(jié)論

在給出新的單圈圖的Wiener指標(biāo)計(jì)算公式之前,首先回顧一下文獻(xiàn)[8]中的關(guān)于單圈圖的Wiener指標(biāo)計(jì)算公式,設(shè)G為具有n個(gè)頂點(diǎn)單圈圖,其所含的圈記為Cm=v0v1···vm?1v0.設(shè)T1,T2,···,Tk(1≤k≤m)為G?E(Cm)中的非平凡分支,其中V(Ti)∩V(Cm)=ui,i=1,2,···,k.令|Ti|=li+1,wi=dTi(ui),w=dCm(u),u∈V(Cm),其中i=1,2,···,k.則單圈圖G的Wiener指標(biāo)可表示為

圖1 單圈圖Un

證對(duì)于單圈圖Un的Wiener指標(biāo),可將其邊分為不在圈上的邊和在圈上的邊兩類,然后分別算出這兩類邊對(duì)其外圍Wiener指標(biāo)的貢獻(xiàn),進(jìn)而求和來獲得.

對(duì)于e∈E(Un),若eE(Cm),則顯然e為Un的割邊,這時(shí)邊e對(duì)W(Un)的貢獻(xiàn)是在其邊e的一側(cè)的所有頂點(diǎn)到其另外一側(cè)所有的頂點(diǎn)的距離之和中,e被經(jīng)過的次數(shù),即這條邊兩側(cè)頂點(diǎn)數(shù)目的乘積.將所有這些邊對(duì)W(Un)的貢獻(xiàn)記為W1(Un);若e∈E(Cm),則顯然e不為Un的割邊,由規(guī)定可知,其邊兩側(cè)頂點(diǎn)數(shù)目為0.所以有

若考慮從Ti中任意頂點(diǎn)到Tj中任意頂點(diǎn)對(duì)W(Un)的貢獻(xiàn),在W1(Un)中已經(jīng)分別考慮了Ti,Tj中的邊的貢獻(xiàn),故接下來只需要再考慮圈上的邊對(duì)W(Un)的貢獻(xiàn).那么從頂點(diǎn)vi到頂點(diǎn)vj的路徑上的任一邊e∈E(Cm),其對(duì)W(Un)的貢獻(xiàn)為經(jīng)過該邊e的次數(shù),而Ti中的頂點(diǎn)到Tj中頂點(diǎn)經(jīng)過這條邊e次數(shù)共有|Ti|·|Tj|次.接著考慮頂點(diǎn)vi到頂點(diǎn)vj的邊數(shù),其中j>i,若,那么頂點(diǎn)vi到頂點(diǎn)vj的邊數(shù)為j?i;若,那么頂點(diǎn)vi到頂點(diǎn)vj的邊數(shù)為m?(j?i),即其邊數(shù)為

故從Ti中頂點(diǎn)到Tj中頂點(diǎn)中圈上的邊對(duì)W(Un)的貢獻(xiàn)為|Ti|·|Tj|·gij.而對(duì)于任意的兩個(gè)Ti,Tj,(i

故W(Un)=W1(Un)+W2(Un),證畢.

接著用定理1中的公式來求W(G).W1(G)=1·1·8·3+2·7+3·6·2=74,W2(G)=1·4·1+1·4·1+4·4·1=24.故W(G)=74+24=98.通過兩種方式對(duì)比會(huì)發(fā)現(xiàn),用定理1來求圖的Wiener指標(biāo)時(shí)會(huì)更加簡(jiǎn)潔,不需要求一些中間量的值,而是直接簡(jiǎn)單利用頂點(diǎn)的數(shù)目就能求得結(jié)果.

圖2 單圈圖G

事實(shí)上,公式(1)與公式(6)是可以相互轉(zhuǎn)化.注意到公式(1)中,對(duì)于Un?E(Cm)剩下來的所有分支樹沒有區(qū)分平凡與非平凡,所以在式(2)與式(4)可以放在一塊討論.此時(shí)的wi=dTi(vi),i=0,1,···,m?1.當(dāng)分支樹Ti平凡時(shí),則W(Ti)=0,wi=0.

致謝:本文得到數(shù)字福建氣象大數(shù)據(jù)研究所和數(shù)據(jù)科學(xué)與統(tǒng)計(jì)重點(diǎn)實(shí)驗(yàn)室的資助.