盧永紅，劉宏英

(山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同 037009）

橄欖樹(shù)距離和及平均距離的求解

盧永紅，劉宏英

(山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同 037009）

樹(shù)是圖論中一個(gè)極其有趣且重要的研究課題，有著較好的應(yīng)用價(jià)值和廣闊的研究前景，由于其本身的多樣性，使得研究者們紛紛沉醉其中.本文求出了一類(lèi)樹(shù)——橄欖樹(shù)的距離和及平均距離.

橄欖樹(shù) 距離和 平均距離

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

W（G）和W（G）作為圖的重要參數(shù)，在結(jié)構(gòu)化學(xué)[2]、建筑學(xué)[3]、通訊網(wǎng)絡(luò)等領(lǐng)域都有重要應(yīng)用，在理論研究方面亦有豐碩的研究成果，可參看文獻(xiàn)[4-9].

定義1 設(shè)T是以v為根的樹(shù)，若T在v的分支分別是T1，T2，…，Tk，其中Ti是長(zhǎng)為i的路 (i＝1，2，…，k)，則稱(chēng)T是一棵橄欖樹(shù)(olive tree).在v的分支數(shù)為n的橄欖樹(shù)記為OT（n）.OT（4）見(jiàn)圖1.

定義2 一個(gè)圖的頂點(diǎn)集V若能分為兩個(gè)非空子集X和Y，使X∪Y＝V，X∩Y＝?，且G的每條邊的兩個(gè)端點(diǎn)分居在X和Y中，則稱(chēng)此圖為二分圖.對(duì)于簡(jiǎn)單二分圖G=(X,Y;E)，若對(duì)任意xi∈X, yj∈Y,有(xi,yi)∈E，則稱(chēng)G為完備二分圖.若，這樣的完備二分圖記作Km,n.

定義3 K1,n稱(chēng)為星(star).星S7見(jiàn)圖2.

圖2 星S7

圖1 橄欖樹(shù)OT(4)

在本文中主要計(jì)算橄欖樹(shù)OT(n)的距離和及平均距離.

2 主要結(jié)果

定理:橄欖樹(shù)OT(n)的距離和為

3 證明

求距離為i(i=1,2,…,n-2)的點(diǎn)對(duì)數(shù)ni，兩點(diǎn)在同一分支的點(diǎn)對(duì)數(shù)為1+2+…+(n-i+1)，兩點(diǎn)在不同分支的點(diǎn)對(duì)數(shù)為(n-i+2)[1+2+…+(i-2)]+(i-1)，此二項(xiàng)之和為

上式中和號(hào)上下標(biāo)[]為取整符號(hào)，下同.

求距離為n的點(diǎn)對(duì)數(shù)，

[1]Bondy JA，Murty U SR.Graph Theory with Applications[M].London:Macmillan Press，1976.

[2]Wiener H.Structural determination of paraffin boiling points[J].Amer Chem Soc，1947，69(2):17-20.

[3]Doyle JK.Mean distance in a graph[J].Discrete Math，1977，17(2):147-154.

[4]Chung FR K.The average distance and the independence number[J].Journal of Graph theory，1988，12(5):229-235.

[5]盧永紅，楊?lèi)?ài)民，管宏生.均勻θ-圖邊距離和的求解[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版，2009，25(4):5-9.

[6]王仲梅，孟獻(xiàn)青，王世英.(mg+1，m f)-圖的(g，f)-因子分解[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版，2009，25(5):4－5.

[7]閆瑞華，許三星.圈長(zhǎng)為3的k圈圖laplacian矩陣譜的界[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版，2007，23(2):11－13.

[8]李秀蘭，王振義.圖的譜半徑的上界[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版，2007，23(1):3－4.

[9]劉小蘭，許三星.與k4-e有關(guān)的一類(lèi)圖的鄰點(diǎn)可區(qū)別全染色[J].山西大同大學(xué)學(xué)報(bào):自然科學(xué)版，2009，25(1):13－15.

The Solution of the Sum of All Distances and Average Distance on Olive Trees

LU Yong-hong，LIU Hong-ying
(School of Mathematical and Computer Sciences，Shanxi Datong University，Datong Shanxi，037009)

As an important direction of graph theory，the research on tree has been a great active branch according to its application，It has remarkable theoretic and applied value.And because of itsmultiple and flexibilitymany researchers have fall in it.This paper has calculated the sum of all distances and average distance on olive trees.

olive tree;the sum of distance;average distance

O157.5

A

〔編輯 高?！?/p>

1674－0874（2010）02－0015－03

2010-01-08

盧永紅(1977-)，女，山西朔州人，碩士，講師，研究方向:圖論及其應(yīng)用.