單圈圖(外圍)Wiener指標的計算公式

李建喜, 雷思宇

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

§1 引 言

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

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

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

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

這個式子是由文獻[1]中樹圖的Wiener指標的計算公式

而導(dǎo)出的.

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

§2 主要結(jié)論

在給出新的單圈圖的Wiener指標計算公式之前,首先回顧一下文獻[8]中的關(guān)于單圈圖的Wiener指標計算公式,設(shè)G為具有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指標可表示為

圖1 單圈圖Un

證對于單圈圖Un的Wiener指標,可將其邊分為不在圈上的邊和在圈上的邊兩類,然后分別算出這兩類邊對其外圍Wiener指標的貢獻,進而求和來獲得.

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

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

故從Ti中頂點到Tj中頂點中圈上的邊對W(Un)的貢獻為|Ti|·|Tj|·gij.而對于任意的兩個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.通過兩種方式對比會發(fā)現(xiàn),用定理1來求圖的Wiener指標時會更加簡潔,不需要求一些中間量的值,而是直接簡單利用頂點的數(shù)目就能求得結(jié)果.

圖2 單圈圖G

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

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