几类树的距离和及平均距离

1、收稿日期:2009212210作者简介:卢永红(1977,女,山西朔州人,山西大同大学数学与计算机科学学院讲师,硕士,主要从事图论及其应用方面的研究.山西师范大学学报(自然科学版第24卷第2期Journal of Shanxi Nor mal University Vol .24No .22010年6月Natural Science Editi on June 2010文章编号:100924490(2010022*几类树的距离和及平均距离卢永红,刘宏英(山西大同大学数学与计算机科学学院,山西大同037009摘要:树是图论中的一个极其有趣且重要的研究课题,有着较好的应用价值和广阔的研究前景,由于

2、其本身研究的多样性特点,也使得研究者们纷纷沉醉于其中.本文求出了几类树的距离和及平均距离.关键词:树;距离和;平均距离中图分类号:O157.5文献标识码:A1预备知识引入研究内容之前,我们首先给出本篇论文常用的一些基本术语和记号.论文中未加说明的术语和记号参见1.设G 为n 阶简单图,V (G 和E (G 分别表示G 的顶点集和边集.图G 的一个点边交替的非空有限序列w =v 0e 1v 1e 2v 2e n v n 称为G 的一个途径,若顶点互不相同,则称w 为一条路,路v 0v 1v n 的长度为n,n 也就是这条路中边的数目.对G 的两个顶点u 和v,如果在G 中存在一条(u,v 路,则

3、称顶点u 和v 是连通的.如果图G 中的任意一对顶点都是连通的,则称G 为连通图.无圈的连通图称为树,记为T .设G 的顶点u 和v 是连通的,则G 中最短的(u,v 路的长就称为u 和v 的距离,记为d G (u,v 或d (u,v 1.称W (G =6u v,u,v (G d G (u,v 为G 的距离和.显然有W (G =6D (G i =1in i ,其中n i 是G 中距离为i 的顶点对的个数,直径D (G =m axd G (u,v |u v,u,v V (G .W (G =W (G /C 2n 为G 的平均距离,n 为G 的顶点数.这里距离和与平均距离都是就连通图而言.W (G

4、和W (G 作为图的重要参数,在结构化学2、建筑学3、通讯网络等领域都有重要应用,在理论研究方面亦有丰硕的研究成果,可参看综述性文献4.定义1如果删去树T 的所有悬挂点及与其相关联的边后是一条路或一个孤立点,则称T 为毛毛虫(caterp illar ,如果毛毛虫T 的非悬挂点都是4度,则我们称T 为优毛毛虫,非悬挂点数为n 的优毛毛虫记为T 1(n ,见图1.定义2路为孤立点的毛毛虫就是星(star .顶点数为n 的星记为S n ,见图2.定义3如果一个树T 删去所有的悬挂边后是一个毛毛虫,则称T 为龙虾树(lobster tree ,在优毛毛虫T 1(n 的每个悬挂点都增加r 条悬挂边所得

5、到的龙虾树称为等足龙虾树,记为T 2(n,r ,见图3.显然路是树.路的距离和为W (P n =16n (n -1(n +13.星的距离和为W (S n =(n -12.事实上,在星S n 中,n 1=n -1,n 2=C 2n -1=12(n -1(n -2,则W (S n =1(n -1+2C 2n -1=(n -12.我们有理由猜想:在点数相同的所有树中,路的距离和最大,星的距离和最小,其他树的距离和介于此二者之间.在本文中我们计算优毛毛虫T 1(n 和等足龙虾树T 2(n,r 的距离和及平均距离 .2主要结果定理1优毛毛虫T 1(n 的距离和为W (T 1(n =32n 3+9n 2+

6、92n +1W (T 1(n =3n 3+18n 2+9n +2(3n +2(3n +1定理2等足龙虾树T 2(n,r 的距离和为W (T 2(n,r =23r 2n 3+10r 2n 2+373r 2n +5r 2+2rn 3+21rn 2+17rn +4r +32n 3+9n 2+92n +1W (T 2(n,r =2W (T 2(n,r (3n +2+2n r +2r (3n +1+2n r +2r 3证明定理1的证明.优毛毛虫T 1(n 有3n +2个点,点的记号如图1.T 1(n 的边数为3n +1.直径D (T 1(n =n +1.距离为1的点对数n 1=边数=3n +1.距离为2

7、的点对数n 2:v 20与v 11,v 22,v 31的距离都是2,v 20为n 2所做的贡献为3,和v 20性质相同的有v 11,v 31,v 1n ,v 2(n +1,v 3n ,所以此类点为n 2所做的贡献为36=18.v 12与v 21,v 32,v 23的距离都是2,v 12为n 2所做的贡献为3,和v 12性质相同的有v 13,v 1(n -1,v 32,v 3(n -1,共计2(n -2个,此类点为n 2所做的贡献为32(n -2=6(n -2.v 21与v 32,v 23,v 12的距离都是2,v 21为n 2所做的贡献为3,和v 21性质相同的有v 2n ,此类点为n 2所做

8、的贡献为32=6.v 22与v 11,v 20,v 31,v 13,v 24,v 33的距离都是2,v 22为n 2所做的贡献为6,和v 22性质相同的有v 23,v 2(n -1,共计n -2个,此类点为n 2所做的贡献为6(n -2.由于以上点对计算数量时重复2次,所以n 2=18+6(n -2+6+6(n -22=6n .下文语言适当简化.距离为3的点对数n 3.v 20:36=18,v 12:62(n -2=12(n -2,v 21:32=6,v 22:32=6,v 23:71第2期卢永红刘宏英:几类树的距离和及平均距离6(n -4=6(n -4,此5项和之一半为n 3=18+12(n

9、 -2+6+6+6(n -42=9n -9.距离为4的点对数n 4.v 20:36=18,v 12:34=12,v 13:62(n -4=12(n -4,v 21:32=6,v 22:34=12,v 24:6(n -6=6(n -6,则n 4=18+12+12(n -4+6+12+6(n -62=9n -18.距离为i 的点对数n i .v 20:36=18,v 12:34(i -3=12(i -3,v 1(i-1:6(2n -4i +8,v 21:32=6,v 22:32(i -2=6(i -2,v 2i :6(n +2-2i ,则n i =18+12(i -3+6(2n -4i +8+6+

10、6(i -2+6(n +2-2i 2=9n -9i +18.i =3,4,n +1.W (T 1(n =1(3n +1+26n +n +1i =3i (9n -9i +18=32n 3+9n 2+92n +1W (T 1(n =W (T 1(n /C 23n +2=3n 3+18n 2+9n +2(3n +2(3n +1定理2的证明.等足龙虾树T 2(n,r 的边数为3n +1+r (2n +2,点数为3n +2+r (2n +2,直径为n +3.点的记号如图3.距离为1的点对数n 1=边数=3n +1+r (2n +2.距离为2的点对数n 2.v 111:r r (2n +2=2r 2(n

11、+1,v 11:3(2n +2=6(n +1,v 21:(3r +32=6(r +1,v 22:(2r +6(n -2=2(r +3(n -2,则n 2=2r 2(n +1+6(n +1+6(r +1+2(r+3(n -22=r 2n +r 2+rn +r +6n .距离为3的点对数n 3.v 111:3r (2n +2=6r (n +1,v 11:(2r +36=6(2r +3,v 12:(r +62(n -2=2(n -2(r +6,v 21:(3+2r 2=2(3+2r ,v 22:(5r +32=2(5r +3,v 23:(4r +6(n -4=2(2r +3(n -4,则n 3=6r

12、 (n +1+6(2r +3+2(n -2(r +6+2(3+2r +2(5r +3+2(2r +3(n -42=6rn +6r +9n -9.距离为4的点对数n 4.v 111:(3+2r 6r =6r (3+2r ,v 121:(6+r 2r (n -2=2r (n -2(6+r ,v 11:(2r +36=6(2r +3,v 12:(5r +34=4(5r +3,v 13:(4r +62(n -4=4(2r +3(n -4,v 21:(3+2r 2=2(3+2r ,v 22:(3+2r 2=2(3+2r ,v 23:(5r +32=2(5r +3,v 24:(4r +6(n -6=2(2

13、r +3(n -6,上述9项之和的一半为n 4=r 2n +4r 2+12rn -6r +9n -18.距离为5的点对数n 5.v 111:(3+2r 6r =6r (3+2r ,v 121:(3+5r 4r ,v 131:(4r +62r (n -4,v 11:(3+2r 6,v 12:(3+2r 4,v 13:(3+5r 4,v 14:(4r +62(n -6,v 21:(3+2r 2,v 22:(3+2r 2,v 23:(3+2r 2,v 24:(5r +32,v 25:(4r +6(n -8,上述12项之和的一半为n 5.距离为6的点对数n 6.v 111:(3+2r 6r ,v 12

14、1:(3+2r 4r ,v 131:(3+5r 4r ,v 141:(4r +62r (n -6,v 11:(3+2r 6,v 12:(3+2r 4,v 13:(3+2r 4,v 14:(3+5r 4,v 15:(4r +62(n -8,v 21:(3+2r 2,v 22:(3+2r 2,v 23:(3+2r 2,v 24:(3+2r 2,v 25:(5r +32,v 26:(4r +6(n -10,上述15项之和的一半为n 6.距离为i 的点对数n i .2n i =(2r +36r +4r (i -5+6+4(i -4+2(i -2+(4r +62r (n -2i +6+2(n -2i +

15、4+(n -2i +2+(5r +3(4r +6=(2r +3(20r -4ir -6i +4n r +12+6n n i =(2r +3(10r -2ir -3i +2n r +6+3n i =5,6,n +2距离为n +3的点对数n n +3.v 111:3r 6r ,则n n +3=9r 2.W (T 2(n,r =1(3n +1+2rn +2r +2(r 2n +r 2+rn +rt 6n +3(9rn +6r +9n -9+4(r 2n +4r 2+12rn -6r +9n -18+n +2i =5i (2r +3(10r -2ir -3i +2n r +6+3n +(n +39r2

16、81山西师范大学学报(自然科学版2010年=23r2n3+10r2n2+373r2n+5r2+2rn3+21rn2+17rn+4r+32n3+9n2+92n+1W(T2(n,r=2W(T2(n,r(3n+2+2n r+2r(3n+1+2n r+2r参考文献:1Bondy J A,Murty U S R.Graph Theory with App licati onsM.London:Mac m illan Press,1976.1213.2W iener H.Structural deter m inati on of paraffin boiling pointsJ.J Amer Che m

17、 Soc,1947,69(1:1720.3Doyle J K.Mean distance in a graphJ.D iscrete Math.,1977,17(2:147154.4Chung F R K.The average distance and the independence numberJ.Graph Theory,1988,12(3:229235.The Su m of A ll D ist ances and AverageD ist ance on Severa l K i n ds of TreesL U Y ong2hong,L I U Hong2y i n g(Sch

18、ool of M athe m atical and Co m puter Sciences,D atong U niversity,D a tong037009,S hanxi,ChinaAbstract:A s an i m portant directi on of graph theory,the research on tree has been a great active branch according t o its app li2 cati on and has re markable theoretic and app lied value.Because of its multi p le and flexibility many researchers have fall in it.The su m of all distances and average distance on t w o kinds of trees had been calculated in this p