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