【摘 要】
:
近年来,图论作为组合数学的一个重要分支,与量子场论、组合优化、运筹学、物理通讯、计算机科学,统计物理等领域的联系越来越密切。而图论中一个重要问题——关于生成树的研究一
论文部分内容阅读
近年来,图论作为组合数学的一个重要分支,与量子场论、组合优化、运筹学、物理通讯、计算机科学,统计物理等领域的联系越来越密切。而图论中一个重要问题——关于生成树的研究一直吸引着人们的关注,其中关于生成树的计数问题的研究,也是一个重要的方向。虽然也出现了很多的算法去计算生成树,这些算法大多是基于分析方法的,如Greedy算法、Fleury算法。矩阵树定理则用代数方法解答了图的生成树个数的计算问题。本文在此基础上,进一步考虑推广形式下的矩阵树定理及某些相应的性质。 在关于图的生成树问题的研究中,把生成树每条边赋予不同的变量,把同一生成树上的这些变量相乘,再把所有的这种生成树单项式相加,得到图的Kirchhoff多项式,又称图的生成树多项式。当把每个变量赋予数值1时,则可以得到关于生成树个数的矩阵树定理。关于图的Kirchhoff多项式,一直是图论中关于生成树的重要课题,它的结构是依据图的生成树定义而来,因为图的类型不同,所以可以得到很多种不同类型的生成树多项式,如果把生成树多项式中的变量定义在有限域上,并考虑它的零点个数,则便是Kontsevich猜想所考虑的一个问题。而对偶Kirchhoff多项式则与特殊情形下的Feynman积分相关的某些不变量的问题相关。 在本文中,我们计算了某些特殊图的Kirchhoff多项式,并得到了平面图的Kirchhoff多项式与其对偶图的对偶Kirchhoff多项式之间的关系。给出了关于图的Kirchhoff多项式可约的充要条件,并由此得到了两个图的Kirchhoff多项式互质的充要条件。证明了Aztec钻石图的两部分子图的Kirchhoff多项式之间并不存在整除关系。给出了Kirchhoff多项式在某种图运算下的运算,并计算了某些特殊图的Kirchhoff多项式在有限域上的零点个数,及在概率条件下的关于图的生成函数。
其他文献
随机处理网络广泛地出现在电话呼叫中心、万维网服务器等系统中。本文考虑一个具有多服务池的随机处理网络,在该网络中接受服务的工作(客户)有多个类别,可以要求多个处理环节,工
教育心理学认为,教育者的个人威信与教育效果呈现出较为明显的一致性.因此,班主任在学生中享有较高的威信,是搞好班级工作和教育好学生的前提和保证.班主任是塑造学生心灵的
请下载后查看,本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
生产计划是复杂经济环境下的常见问题.做好生产计划是企业实现发展的关键.合理地安排生产不仅能使企业生产有序进行,而且能在一定程度上(甚至有可能大幅度)提高经济效益.本文在前人工作的基础上,对模糊环境下的生产计划问题做了以下研究:(1)对白进达等在文献[18]中提出的生产计划模型做了合理的改进,给出了一个有助于提高经济效益的带有劳动生产率的模糊生产计划新模型(3.6);(2)运用可信性理论与期望值理论
能行实数是可计算理论的基本概念之一。可计算有理数序列的极限称为能行实数,又称为△02实数。若该可计算有理数序列递增,则其极限称为可计算可枚举实数(c.e.或left-computab
合作现象是生物化学中非常重要的现象,它反映了小分子底物与酶结合时对酶与底物结合能力的影响。通常合作现象会使产物产生速率-底物浓度的图像呈S形,这有利于生物体用以加强对
本文共分三章,第一章主要回顾了模的覆盖包络以及余挠对的基本概念和相关性质。对任一正整数n,假设Pn,表示左投射维数小于等于n的模构成的类,第二章,我们着重研究了Pn-包络与
本文从两个方面研究了一类具有实际物理背景的非线性微分方程,一是在现有非线性微分方程求解的主要方法的基础上,我们对非线性微分方程孤立波解的求解方法进行了研究,利用微分方
英语需要一定的学习环境来实践。农村小学英语学习环境的创设尤为重要,这对激起小学生学习英语的兴趣,提高小学英语教学质量的影响很大,它对培养小学生的语感起着关键的作用
向量值加细方程指的是形式为的函数方程,这里向量函数φ(x)=(φ1(x),φ2(x),…,φr(x))T是该方程对应的加细函数,{Hk}k∈Zs是该方程的加细系数,N(x)为方程的非齐次项。如果N(x)=0,方