趙相佩，李月清，葉永升，黃杜娟

（1.淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000；2.北京工業(yè)職業(yè)技術(shù)學(xué)院 基礎(chǔ)教育學(xué)院，北京 100042；3.淮北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000 ）

1 預(yù)備知識(shí)

本文考慮的圖都是有限無向簡(jiǎn)單圖.設(shè)G=(V(G),E(G))是一個(gè)圖，分別用V(G),E(G)表示圖G的頂點(diǎn)集和邊集，|V(G)|,|E(G)|表示頂點(diǎn)數(shù)和邊數(shù)，dG(u)表示頂點(diǎn)u在G中的度數(shù)，dG(x,y)表示兩頂點(diǎn)x和y之間的距離，Diam(G)表示圖G的直徑.圖G的Wiener指標(biāo)在圖G中，兩邊f(xié)=uv的頂點(diǎn)和g=xy的頂點(diǎn)間最短路的長(zhǎng)度稱為f=uv和g=xy的距離，記DG(f,g)，即：DG(f,g)=min{dG(u,x),dG(u,y),dG(v,x),dG(v,y)}.據(jù)此，即可給出圖G的邊Wiener 指標(biāo)的定義在連通圖G中，DG′(f,g)表示任意兩條邊f(xié)=uv和g=xy之間平均距離，即

文獻(xiàn)［3］首次引進(jìn)圖G的邊平均Wiener指標(biāo)

文獻(xiàn)［4-6］已研究了n階單圈圖、n階連通圖及有m條邊連通圖的邊平均Wiener指標(biāo).本文將研究并給出扇圖中任意兩邊之間的平均距離的算法程序.

2 n階扇圖Fn的邊平均Wiener指標(biāo)

定義1［7］設(shè)Pn-1是有n-1個(gè)頂點(diǎn)的路，P1與Pn-1的聯(lián)圖P1∨Pn-1稱為扇圖Fn.設(shè)

記vivi+1=ei(i=1,2,…,n-2),v0vj=en-2+j(j=1,2,…,n-1)(如圖1所示).

由圖的邊平均Wiener指標(biāo)的定義可知，一個(gè)圖的邊平均Wiener指標(biāo)就是這個(gè)圖的任意兩邊之間的平均距離之和.為了計(jì)算扇圖的邊平均Wiener 指標(biāo)，我們把扇圖的邊分為兩類，即{e1,e2,…,en-2}和{en-1,en,…,e2n-3}.下面分三種情形討論.

情形1：任取ei,ej∈{e1,e2,…,en-2}時(shí)，

圖1 扇圖 Fn

情形2：任取ei∈{e1,e2,…,en-2}，ej∈{en-1,en,…,e2n-3}時(shí)，

情形3：任取ei,ej∈{en-1,en,…,e2n-3}時(shí)

容易驗(yàn)證，F(xiàn)3的邊平均Wiener 指標(biāo)當(dāng)n很大時(shí)，需要計(jì)算對(duì)邊的平均距離，由此可見計(jì)算量是很大的，手工計(jì)算起來非常繁瑣且易出錯(cuò).我們用Microsoft Visual C++6.0計(jì)算扇圖中任意兩邊之間的平均距離，核心程序如下：

下面是該程序在n=20 時(shí)的運(yùn)算結(jié)果部分截圖：

注1需要說明的是程序不僅輸出了兩邊的平均距離，還輸出了平均距離為的每對(duì)邊和所有平均距離為的每對(duì)邊.

定理1

證明對(duì)n進(jìn)行數(shù)學(xué)歸納.

（1）當(dāng)n=4 時(shí)，

（2）假設(shè)等式對(duì)于n-1成立，即則

等式對(duì)于n也成立，定理得證.

3 n階輪圖Wn的邊平均Wiener指標(biāo)

定義2［7］Wn=Cn-1·V0表示具有n個(gè)頂點(diǎn)的輪圖，其中Cn-1表示有n-1個(gè)頂點(diǎn)的圈，記

Cn-1的每一個(gè)頂點(diǎn)都與中心頂點(diǎn)V0連接，E(Wn)={v1v2,v2v3,…,vn-2vn-1,vn-1v1,v0v1,v0v2,…,v0vn-1}.記vivi+1=ei(i=1,2,…,n-2),v0vj=en-2+j(j=1,2,…,n-1),vn-1v1=e2n-2（如圖2所示）.

圖2 輪圖Wn

Wn可以看做是在Fn的基礎(chǔ)上連接e2n-2得到的.為了計(jì)算輪圖的邊平均Wiener指標(biāo)，我們對(duì)輪圖的邊分為三類{e1,e2,…,en-2}，{en-1,en,…,e2n-3}和{e2n-2} 三類.計(jì)算的基礎(chǔ)上，加需要注意的是，增加e2n-2，會(huì)導(dǎo)致在發(fā)生變化.

定理2We′(Wn)=3n2-11n+8 (n≥4).

證明Wn可以看做是在Fn的基礎(chǔ)上連接e2n-2=v1vn-1得到的，故有

其中等式右邊的第二項(xiàng)是由于Diam(Fn)=2，對(duì)任意x,y∈V(Fn)，有

進(jìn)而有，

故定理得證.

［1］DOBRYNIN A A，ENTRINGER R C，GUTMAN I.Wiener index of trees：Theory and applications［J］.Acta Appl Math，2001，66：211-249.

［2］IRANMANESH A，GUTMAN I，KHORMALIA O，et al.The edge versions of the Wiener index［J］.MATCH Commun Math Comput Chem，2009，61：663-672.

［3］WU B.Wiener index of line graphs［J］.MATCH Commun Math Comput Chem，2010，64（3）：699-706.

［4］蔡華，苗杰.n階單圈圖的邊平均Wiener指標(biāo)［J］.山東大學(xué)學(xué)報(bào)：理學(xué)版，2012，47（10）：70-74.

［5］蔡華，苗杰.n階單圈圖的邊平均Wiener指標(biāo)取整數(shù)的充要條件［J］.昌吉學(xué)院學(xué)報(bào)，2011，6：86-88.

［6］蔡華.圖的邊Wiener指標(biāo)［D］.烏魯木齊：新疆大學(xué)，2009.

［7］于玲，葉永升.路和圈的聯(lián)的Wiener指數(shù)［J］.淮北師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，32（1）：1-3.