连通图距离和及平均距离

《连通图距离和及平均距离》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要图的距离和是图中所有点对间的距离之和，这个概念是由化学家Wiener提出的，它是有机化学中定量研究有机化合物构造性关系的一个十分成功的工具．早在1947年，美国化学家HaroldWiener利用距离和提出了碳氢化合物中具有确切的物理化学性质的分子模型．此后，有关这一领域的研究活动在化学界就一直没有停止过．在化学中距离和是用图的理论建立分子模型时最频繁使用的概念之一。与之密切相关的另一量一平均距离，表示图中所有点对间距离的平均值，最初主要作为评价楼层设计的工具，在以后的研究中，用其刻画图的紧凑性，逐渐地这一概念被用于计算

2、机系统连通方面及通讯网络的分析和设计中．在一个网络模型里，从一点到另一点传递信息的时间和信号的衰减程度往往与信息必须经过的线路长度是成比例的。直径反映了最坏可能的情形，而平均距离则反映了它的平均情况。总之这两个量作为图的重要参数已得到了广大图论工作者的重视和广泛的研究，本寡在前人工作的基础之上对这两个量作了一些进一步的研究，并把部分结果作了适当推广．本文在第一章预备知识中主要引入了距离和及平均距离的概念，并综述了目前关于这两个量的一些研究结果．第二章主要通过一些计数技巧给出了几类特殊图的平均距离．第三章举出更简单的反例验证

3、了一个猜想是错误的，并提出了一个新的猜想．关键词：距离和；平均距离；复合图；目一图；如Bruijn图中图分类号t0157．5ABSTRACTTheSUmofdistancesingraphisjustthesumofdistancesbetweenallpairsofverticesofgraph．Thisconcept，introducedbythechemistWiener，isaquitesuccess—fultoolfordesigningquantitativestructure-propertyrelation

4、sinorganicchemistry．Asearlyasin1947inAmericanchemistHaroldWienerproposedthemodelingofcertainphysico-chemiealpropertiesofhydrocarbonmoleculesbymeansofthesumofdistances．Fromthen，theresearchinthisfieldhasneverbeenterminated．Inchemistrythesumofdistancesisoneofmostfreq

5、uently-usedconceptsinconstructingmolecularmodelbytheoryofgraph．Itisclosedrelatedtoanotherquantity·meandistance，denotedtheaveragevalueofthedistancesbetweenallpairsofverticesingraph，itisameasureofthe”compactness”ofagraph，ithadalreadybeeninitiallyusedinarchitectureas

6、atoolfortheevaluationoffloorplans．Furthermore，itisusedasameasureofthee伍ciencyofacommunicationsnetwork．Inanetworkmodel，thetimeusedintransmittinginformationfromonevertextoanothervertexandthedecreasingdegreeofthesignalisalwaysproportionaltothelengthofthelinetheinform

7、ationmustcover．Diameterreflectstheworstpossibleconditionwhilethemeandistancereflectsitsaveragecondition：Inawordthistwoquantitiesasanimportantparameterofgraphhavebeenpaidattentionandfurtherresearchbymanyexperts．Basedontheearliertimesresearchonthistwoquantities，this

8、thesisgivessomeresearches．Inchapter1，wemainlygivetheconceptsofthesumofdistanceandthemeandistance，andthensumupsomeresultsonthistwoquantitiesatpresent．Inc