橄欖樹距離和及平均距離的求解

盧永紅，劉宏英

(山西大同大學數學與計算機科學學院，山西大同 037009）

橄欖樹距離和及平均距離的求解

盧永紅，劉宏英

(山西大同大學數學與計算機科學學院，山西大同 037009）

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

橄欖樹 距離和 平均距離

1 預備知識

W（G）和W（G）作為圖的重要參數，在結構化學[2]、建筑學[3]、通訊網絡等領域都有重要應用，在理論研究方面亦有豐碩的研究成果，可參看文獻[4-9].

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

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

定義3 K1,n稱為星(star).星S7見圖2.

圖2 星S7

圖1 橄欖樹OT(4)

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

2 主要結果

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

3 證明

求距離為i(i=1,2,…,n-2)的點對數ni，兩點在同一分支的點對數為1+2+…+(n-i+1)，兩點在不同分支的點對數為(n-i+2)[1+2+…+(i-2)]+(i-1)，此二項之和為

上式中和號上下標[]為取整符號，下同.

求距離為n的點對數，

[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]盧永紅，楊愛民，管宏生.均勻θ-圖邊距離和的求解[J].山西大同大學學報:自然科學版，2009，25(4):5-9.

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

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

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

[9]劉小蘭，許三星.與k4-e有關的一類圖的鄰點可區別全染色[J].山西大同大學學報:自然科學版，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

〔編輯 高海〕

1674－0874（2010）02－0015－03

2010-01-08

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