图的生成树多项式的计算及性质研究

来源 :哈尔滨工业大学 | 被引量 : 0次 | 上传用户:guihaiyidao1
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,图论作为组合数学的一个重要分支,与量子场论、组合优化、运筹学、物理通讯、计算机科学,统计物理等领域的联系越来越密切。而图论中一个重要问题——关于生成树的研究一直吸引着人们的关注,其中关于生成树的计数问题的研究,也是一个重要的方向。虽然也出现了很多的算法去计算生成树,这些算法大多是基于分析方法的,如Greedy算法、Fleury算法。矩阵树定理则用代数方法解答了图的生成树个数的计算问题。本文在此基础上,进一步考虑推广形式下的矩阵树定理及某些相应的性质。  在关于图的生成树问题的研究中,把生成树每条边赋予不同的变量,把同一生成树上的这些变量相乘,再把所有的这种生成树单项式相加,得到图的Kirchhoff多项式,又称图的生成树多项式。当把每个变量赋予数值1时,则可以得到关于生成树个数的矩阵树定理。关于图的Kirchhoff多项式,一直是图论中关于生成树的重要课题,它的结构是依据图的生成树定义而来,因为图的类型不同,所以可以得到很多种不同类型的生成树多项式,如果把生成树多项式中的变量定义在有限域上,并考虑它的零点个数,则便是Kontsevich猜想所考虑的一个问题。而对偶Kirchhoff多项式则与特殊情形下的Feynman积分相关的某些不变量的问题相关。  在本文中,我们计算了某些特殊图的Kirchhoff多项式,并得到了平面图的Kirchhoff多项式与其对偶图的对偶Kirchhoff多项式之间的关系。给出了关于图的Kirchhoff多项式可约的充要条件,并由此得到了两个图的Kirchhoff多项式互质的充要条件。证明了Aztec钻石图的两部分子图的Kirchhoff多项式之间并不存在整除关系。给出了Kirchhoff多项式在某种图运算下的运算,并计算了某些特殊图的Kirchhoff多项式在有限域上的零点个数,及在概率条件下的关于图的生成函数。
其他文献
生产计划是复杂经济环境下的常见问题.做好生产计划是企业实现发展的关键.合理地安排生产不仅能使企业生产有序进行,而且能在一定程度上(甚至有可能大幅度)提高经济效益.本文在前人工作的基础上,对模糊环境下的生产计划问题做了以下研究:(1)对白进达等在文献[18]中提出的生产计划模型做了合理的改进,给出了一个有助于提高经济效益的带有劳动生产率的模糊生产计划新模型(3.6);(2)运用可信性理论与期望值理论
本文从两个方面研究了一类具有实际物理背景的非线性微分方程,一是在现有非线性微分方程求解的主要方法的基础上,我们对非线性微分方程孤立波解的求解方法进行了研究,利用微分方