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

发布时间：2020-06-06 05:29

【摘要】：近年来,图论作为组合数学的一个重要分支,与量子场论、组合优化、运筹学、物理通讯、计算机科学,统计物理等领域的联系越来越密切。而图论中一个重要问题——关于生成树的研究一直吸引着人们的关注,其中关于生成树的计数问题的研究,也是一个重要的方向。虽然也出现了很多的算法去计算生成树,这些算法大多是基于分析方法的,如Greedy算法、Fleury算法。矩阵树定理则用代数方法解答了图的生成树个数的计算问题。本文在此基础上,进一步考虑推广形式下的矩阵树定理及某些相应的性质。在关于图的生成树问题的研究中,把生成树每条边赋予不同的变量,把同一生成树上的这些变量相乘,再把所有的这种生成树单项式相加,得到图的Kirchhoff多项式,又称图的生成树多项式。当把每个变量赋予数值1时,则可以得到关于生成树个数的矩阵树定理。关于图的Kirchhoff多项式,一直是图论中关于生成树的重要课题,它的结构是依据图的生成树定义而来,因为图的类型不同,所以可以得到很多种不同类型的生成树多项式,如果把生成树多项式中的变量定义在有限域上,并考虑它的零点个数,则便是Kontsevich猜想所考虑的一个问题。而对偶Kirchhoff多项式则与特殊情形下的Feynman积分相关的某些不变量的问题相关。在本文中,我们计算了某些特殊图的Kirchhoff多项式,并得到了平面图的Kirchhoff多项式与其对偶图的对偶Kirchhoff多项式之间的关系。给出了关于图的Kirchhoff多项式可约的充要条件,并由此得到了两个图的Kirchhoff多项式互质的充要条件。证明了Aztec钻石图的两部分子图的Kirchhoff多项式之间并不存在整除关系。给出了Kirchhoff多项式在某种图运算下的运算,并计算了某些特殊图的Kirchhoff多项式在有限域上的零点个数,及在概率条件下的关于图的生成函数。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 高文宇;;最多叶子生成树问题的核化算法[J];计算机学报;2010年12期

2 赵星明;王萱;;环状给水管网自动生成树的研究[J];中国农村水利水电;2018年06期

3 黄河;刘海;;关于网络图的MCST问题探讨[J];交通与计算机;1990年02期

4 吴龙树;王勤;;基于最小代价和生成树的算法研究[J];微计算机信息;2010年12期

5 夏小云;郭肇禄;杨书新;王吉源;;(μ+λ)EA算法关于最多叶子生成树问题的近似性能[J];江西理工大学学报;2016年03期

6 姚国辉;朱大铭;马绍汉;;有向无环图最小度生成树问题的一种近似算法[J];计算机研究与发展;2009年06期

7 高静;李实秋;陈云;;用母函数求解图的生成树问题[J];重庆邮电大学学报(自然科学版);2007年S1期

8 赵玲;张建科;;基于蚁群系统的双目标最小生成树算法[J];西安邮电学院学报;2008年05期

9 崔建群;陈爱玲;夏振厂;吴黎兵;;一种高稳定性低延迟的应用层组播生成树算法[J];计算机科学;2016年06期

10 高文宇;;有向图最多叶子生成树问题研究[J];计算机应用;2010年06期

相关博士学位论文 前1条

1 李幸福;最大内部点生成树问题的算法及复杂性[D];山东大学;2015年

相关硕士学位论文 前4条

1 董阳;图的生成树多项式的计算及性质研究[D];哈尔滨工业大学;2018年

2 徐忆晨;最小标记生成树问题的研究与拓展[D];复旦大学;2009年

3 钟玉文;求解两类图论问题的P系统研究[D];重庆大学;2016年

4 陈智豪;遗传算法在最小steiner生成树问题中的研究和应用[D];安徽工业大学;2012年

，

本文编号：2699229