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

来源 :南开大学 | 被引量 : 0次 | 上传用户:zxd19811219
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在图论中,树是一类非常重要的图。直到现在,它仍然是一个非常活跃的研究领域。在实际应用当中,许多问题都跟树相联系。正如其他一些图类,我们主要关注的是树的结构性质。   在本篇论文中,我们将从概率的角度考察树的结构计数问题,即相关计数的渐近性质。让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是常数。
其他文献
期刊
我们研究一类无界域上的Helmholtz方程边值问题及其反问题,物理上对应于介质对波场的散射,包括正散射与逆散射.根据散射体的特性,散射现象可以分为简单散射和复杂散射.简单散射
在有限群论中,通过讨论子群的性质来研究群的结构性质是一个非常重要的课题.它也是我们研究群结构一个重要的切入点。例如,许多重要的结果就是通过讨论循环子群,正规子群等特殊
期刊
学位
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
教学改革的发展对教师提出更高的要求,需要教师解决几个方面的问题:明确素描学习的目的和任务;培养学生科学的观察方法;培养艺术趣味;提炼概括,艺术的表现对象;培养创新精神
众所周知,向量优化理论与应用研究中研究的热点之一是向量平衡问题稳定性分析(见文[1-15,17-26,29-53]),而稳定性分析的一个十分重要方面是连续性研究.首先借助集合极限的性质
求解非线性矩阵方程的问题主要是通过分析所给方程参数的性质来得到方程的解,由于Hermite正定解在实际中应用广泛,所以一般只讨论此类解的情况,在众多文献中,大量作者讨论了非线
近年来,混沌同步问题的研究引起了广泛的关注,并成为一个研究热点.本文分别对一类不连续混沌系统,一类含时滞和随机干扰的复杂动力网络,分数阶Lorenz系统的同步问题进行了研