论文部分内容阅读
在图论中,树是一类非常重要的图。直到现在,它仍然是一个非常活跃的研究领域。在实际应用当中,许多问题都跟树相联系。正如其他一些图类,我们主要关注的是树的结构性质。
在本篇论文中,我们将从概率的角度考察树的结构计数问题,即相关计数的渐近性质。让Uo表示o个顶点的树所形成的集合。假设在U。中,每一棵树都是等概率的。那么,我们就定义了一个概率空间,Uo的每一个子集就是一个事件。我们在这个空间上定义一个随机变量Yo)Uo*(简记为Yo),并将分析相应的概率分布。
设Yo为树中某个给定度数的顶点的数目。在概率空间Uo中,已经证明了Yo是近似正态的,它的期望值~μo以及方差值~σo。因此,对于几乎所有的树,某个给定度数的顶点数目是)μ,p)2**o.
对于更复杂的情形,我们定义模式为一个给定的小树,它的点标记为内点(度大于1)和外点(度为1)。在树中,某个给定的模式的数目为对应点同所有模式内点度数相匹配的生成子树的数目。特别地,某个星模式的数目就是拥有某个固定度数的顶点数目,它相应的分布是正态的。但是对于一个任意的模式,还没有像星模式那样证明相应的分布近似为正态。尽管很多关于特殊模式的结论都证实了这一点。并且,对有根树,如果对其有根树集定义类似的概率空间,其近似正态性同样成立。然而,对于Uo上的任一模式,我们只是得到了它极限分布的密度函数为)B1,C1U3*fD1u3,其中B1<C1<D1为常数。模式数目的期望和方差仍然是o的线性表出。显然,如果证明了C1>1,那么分布就是正态的。但证明这一点似乎非常困难。
接下来,在本论文中,对于一个双星模式,我们将通过一个传统的办法证实上述结论,这种办法包含了一个复杂的计算过程。在进一步的研究中,我们通过一个新的办法完全解决了这个问题。我们得到了:对于几乎所有的树,它所对应的有根树的数目为)μ)S*,p)2**o。结合着有根树上的正态分布的结论,在Uo中,对任一模式,极限分布也是正态的。
再者,我们集中精力于另外一个树集合uoE,它表示最大顶点的度是有界的树的集合。我们同样考察了模式的性质。另外,我们转向一个给定小树的数目,即,在树中,相应的生成子树(对应点的度不再要求匹配)的数目。事实上,当我们转向在Uo中给定小树的对应子树的数目时,这个问题是非常困难。但在uoE中,我们也可以建立类似于模式的结论。
作为应用,我们使用这些渐近结论去估计uo或者uoE中几乎所有的树的一些化学指标的值:广义的Randi(c)指标,广义的Zagreb指标以及Estrada指标。实际上,先前的一些研究人员仅仅只是考虑了这些指标的上下界或者某些特殊图的准确值,而我们是从概率角度建立关于这些指标的整体性质。
第一章是引言。我们介绍了关于树的一些结论的历史和背景,并且给出了在本文中出现的概念和记号。再者,我们在这一部分呈现了本篇论文的主要结果。
第二章是来给出一些本文所涉及到的预备知识,包括:生成函数,概率,组合以及一些主要的引理。
在第三章,通过在[1]中使用过的方法,我们证明了对于一个双星模式,在Uo中出现的数目是一个近似正态分布。然后,我们应用这个结论,对Uo中几乎所有的树,当广义Ranci(c)指标的指数变量α≤1时,指标值满足)λα口-e*o≤Sα)Uo*≤)λα,ε*oa.e.,其中ε是任一正数。并且我们证明了Fajtlowicz[2]的猜想:任意的图H,S)H*≥E)H*它对Uo中几乎所有的树都是成立的,其中E)H*表示平均距离。我们还类似地给出了广义Zagreb指标的估计。
在第四章中,我们通过计算树所对应的有根树数目的近似值,证明了在Uo中任意模式的极限分布都是正态的。
在第五章,我们证明了在uoE中,星模式(双星模式)的数目也同样拥有o的线性形式的期望和方差。特别地,星模式的分布仍然被证实是近似正态的。然后,对于广义的Zagreb指标,我们得到了在uoE中Eα>)ea)E*,p)2**oa.e.<其中eα)E*是一个常数。并且,对广义的Randi(c)指标,我们有Sα>)sα)E*,p)2**oa.e..
在最后一章,我们考虑,在uoE中,任意给定子树I的数目,并且证明相应的分布类似地拥有期望)μI,p)2**o,方差)σuI,p)2**o.作为一个应用,对uoE中几乎所有的树,我们给出了Estrada指标值的估计:)μE-ε*o=FF)uoE*=)μE,ε*oa.e.(<)并且我们证实了FF)UoE*≈bE3,ca.e.,其中b<c是常数。