关于树的若干计数的渐进性及其应用

来源 :南开大学 | 被引量 : 0次 | 上传用户:beilei
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在图论中,树是一类非常重要的图。直到现在,它仍然是一个非常活跃的研究领域。在实际应用当中,许多问题都跟树相联系。正如其他一些图类,我们主要关注的是树的结构性质。在本篇论文中,我们将从概率的角度考察树的结构计数问题,即相关计数的渐近性质。让Tn表示n个顶点的树所形成的集合。假设在Tn中,每一棵树都是等概率的。那么,我们就定义了一个概率空间,Tn的每一个子集就是一个事件。我们在这个空间上定义一个随机变量Xn(Tn)(简记为Xn),并将分析相应的概率分布。设Xn为树中某个给定度数的顶点的数目。在概率空间Tn中,已经证明了Xn是近似正态的,它的期望值~μn以及方差值~σn。因此,对于几乎所有的树,某个给定度数的顶点数目是(μ+o(1))n.对于更复杂的情形,我们定义模式为一个给定的小树,它的点标记为内点(度大于1)和外点(度为1)。在树中,某个给定的模式的数目为对应点同所有模式内点度数相匹配的生成子树的数目。特别地,某个星模式的数目就是拥有某个固定度数的顶点数目,它相应的分布是正态的。但是对于一个任意的模式,还没有像星模式那样证明相应的分布近似为正态。尽管很多关于特殊模式的结论都证实了这一点。并且,对有根树,如果对其有根树集定义类似的概率空间,其近似正态性同样成立。然而,对于Tn上的任一模式,我们只是得到了它极限分布的密度函数为(A0+B0t2)eC0t2,其中A0, B0,C0为常数。模式数目的期望和方差仍然是n的线性表出。显然,如果证明了B0=0,那么分布就是正态的。但证明这一点似乎非常困难。接下来,在本论文中,对于一个双星模式,我们将通过一个传统的办法证实上述结论,这种办法包含了一个复杂的计算过程。在进一步的研究中,我们通过一个新的办法完全解决了这个问题。我们得到了:对于几乎所有的树,它所对应的有根树的数目为(μ(R)+o(1))n。结合着有根树上的正态分布的结论,在Tn中,对任一模式,极限分布也是正态的。再者,我们集中精力于另外一个树集合(?)n,它表示最大顶点的度是有界的树的集合。我们同样考察了模式的性质。另外,我们转向一个给定小树的数目,即,在树中,相应的生成子树(对应点的度不再要求匹配)的数目。事实上,当我们转向在Tn中给定小树的对应子树的数目时,这个问题是非常困难。但在中,我们也可以建立类似于模式的结论。作为应用,我们使用这些渐近结论去估计(?)n者(?)n中几乎所有的树的一些化学指标的值:广义的Randi指标,广义的Zagreb指标以及Estrada指标。实际上,先前的一些研究人员仅仅只是考虑了这些指标的上下界或者某些特殊图的准确值,而我们是从概率角度建立关于这些指标的整体性质。第一章是引言。我们介绍了关于树的一些结论的历史和背景,并且给出了在本文中出现的概念和记号。再者,我们在这一部分呈现了本篇论文的主要结果。第二章是来给出一些本文所涉及到的预备知识,包括:生成函数,概率,组合以及一些主要的引理。在第三章,通过在[1]中使用过的方法,我们证明了对于一个双星模式,在Tn中出现的数目是一个近似正态分布。然后,我们应用这个结论,对Tn中几乎所有的树,当广义Ranci指标的指数变量α≤0时,指标值满足(λα ε)n≤Rα(Tn)≤(λα+ε)n a.e.,其中ε是任一正数。并且我们证明了Fajtlowicz [2]的猜想:任意的图G,R(G)≥D(G),它对Tn中几乎所有的树都是成立的,其中D(G)表示平均距离。我们还类似地给出了广义Zagreb指标的估计。在第四章中,我们通过计算树所对应的有根树数目的近似值,证明了在(?)n中任意模式的极限分布都是正态的。在第五章,我们证明了在Tn中,星模式(双星模式)的数目也同样拥有n的线性形式的期望和方差。特别地,星模式的分布仍然被证实是近似正态的。然后,对于广义的Zagreb指标,我们得到了在(?)n中Dα=(dα(△)+o(1))n a.e.,其中dα(△)是一个常数。并且,对广义的Randi指标,我们有Rα=(rα()+o(1))n a.e..在最后一章,我们考虑,在Tn中,任意给定子树H的数目,并且证明相应的分布类似地拥有期望(μH+o(1))n,方差(σHt+o(1))n.作为一个应用,对(?)n中几乎所有的树,我们给出了Estrada指标值的估计:(μ ε)n <EE(Tn)<(μ+ε)n a.e.,并且我们证实了EE(Tn)≈aD2+b a.e.,其中a, b是常数。
其他文献
老有所养是我国广大劳动者们的共同心愿,而现阶段中国的养老金制度正遭遇着十分大的危机。人口老龄化、职工个人账户空账运行造成的巨额隐性债务都是我国政府需要急于解决的
目的:(1)探索MALAT-1相关信号通路是否与急性髓细胞白血病(Acute myeloid leukemia,AML)的发生、发展及预后具有相关性,从而揭示MALAT-1可能介导的表观遗传调控对急性髓细胞
购租并举成为当前中国住房制度改革的重要方向。本文对美国和德国的住房租赁市场的现状特点、调控机制、操作工具、法律保障、市场监管等进行了深入研究,从制度设计、住房保
社会的进步与经济的增长有效推动了科学技术的发展,使得智能家居网关被广泛的应用到家庭生活当中,为人们的生活带来了便利。基于此,本文以基于ARM平台智能家居网关设计为主要
前体mRNA的多聚腺苷酸化(Polyadenylation)是指当mRNA转录出来之后,由Poly(A)因子组成的多聚腺苷酸化机器在其3’端剪切位点进行切割,并由Poly(A)聚合酶添加Poly(A)尾巴形成
2014年10月至2015年10月,在贺兰山国家级自然保护区,利用红外相机技术对同域分布阿拉善马鹿(Cervus elaphus alasiacus)与岩羊(Pseudoisnayaur)的活动规律、的集群行为进行了研究。探讨了阿拉善马鹿与岩羊的日活动节律模式及季节变化;从时间角度分析两者在生态位上的分化,揭示两者在时间生态位上的分化方式和共存机制;分析了马鹿与岩羊的集群类型和大小及其出现的频次和
气体水合物储氢是一项具备大规模工业化应用前景的储氢技术。为优化水合储氢条件、提升水合储氢量,近年来已经开发出了三代水合储氢技术。这三代水合储氢技术均存在一个问题:
近年来,随着中国住房制度的改革,经济的快速发展,城镇居民的住房条件总体上有了很大的改善,但是房价一直不断的持续上涨,许多地方的房价已经远远超出了普通居民的购买能力,住
目的颅缝早闭,是指颅骨间的纤维连接或软骨连接过早融合或骨化,进而影响颅骨形状的一种生长模式。颅顶、颅底和面部骨骼结构在生长过程中相互作用,对彼此的形态学发育产生影
本文简要介绍了白云鄂博铁矿主要成分、分布状况,简单叙述了白云鄂博是内蒙古地区最大的钢铁能源基地,是以铁、稀土、钍、铌等为主的多元素共生矿,及储量分布。概述了铁矿浮