图的积和多项式及其相关问题

来源 :兰州大学 | 被引量 : 0次 | 上传用户:rsbgrc
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的邻接矩阵的特征矩阵的积和式称为图的积和多项式(permanental polyno-mial),1981年Kasum等首次研究表明图的积和多项式与分子的结构密切相关.之后,Cash计算了富勒烯的同分异构体的积和多项式及其根,发现在有n个顶点的同分异构体中,每个同分异构体的n/2对根中有10对是常值,其余(n/2-10)对根随同分异构体的结构变化而不同,从而指出图的积和多项式反映了分子的结构信息.众所周知,行列式的计算有很多有效的算法,然而积和式的计算是#P-完全问题.对于一个二部图,其积和多项式的常数项等于该图的完美匹配个数的平方.若一个图G是Pfaffian的,对其进行Pfaffian定向可将其邻接矩阵中的某些1变成-1得到矩阵r,那么G的完美匹配计数就可通过计算r的行列式得到.基于此,晏卫根和张福基证明了如果一个二部图G不包含K2,3的偶剖分,那么存在G的定向e使得G的积和多项式等于G的斜邻接矩阵的特征多项式.本文首先考虑了都有哪些图的积和多项式可以通过其定向图的斜邻接矩阵的特征多项式来计算,刻画了这些图的结构并给出了定向方法.然后计算了路、圈等基本图类的积和多项式,并给出了六角形链等化学图的积和多项式的确切表达式.更一般地,我们还研究了矩阵的积和多项式,主要刻画了可以通过符号矩阵的特征多项式来计算其积和多项式的矩阵.最后,我们讨论了曲面上六角系统的的积和多项式的常数项,即其完美匹配个数的平方,通过定向图的方法,给出了完美匹配计数的具体表达式.全文共分为如下五章.第一章介绍了一些基本定义和符号,阐述了积和多项式的研究背景及进展,并列举了本文的主要研究结果.在第二章中,我们首先得到了一个充分必要条件,即一个二部图的积和多项式等于其定向图的斜邻接矩阵的特征多项式当且仅当这个二部图不包含K2,3偶剖分.进一步证明了一个2-连通的不包含K2,3的偶剖分的二部图等价于可平面1-圈共振图.从而得到一个2连通的不包含K2,3的偶剖分的二部图的任意Pfaffian定向中的任意圈都是奇定向的.基于此,给出了利用Pfaffian定向来计算此类图的积和多项式的方法.第三章计算了特殊图类的积和多项式的计算.利用Pfaffian定向的思想,给出了路、圈等基本图类的积和多项式的确切表达式.对于六角系统,基于递归的思想,以5阶矩阵的连乘积的形式,给出了六角形链及一类有内点的六角系统的积和多项式.同时还得到了广义多边形链的积和多项式的表达式.第四章的目标是研究哪些矩阵的积和多项式可以通过其符号矩阵的特征多项式来计算.对一个m×n阶{0,1}矩阵A(m≤n),如果存在矩阵B(B是将A中的某些1变成-1而得到的)使得对于A的任意m阶的子矩阵A’,均有B中相应的m阶的子矩阵B’使得A’的积和多项式等于B’的特征多项式,则称矩阵A是完全可转换的.通过对{0,1}-方阵A定义二部图GA*,我们证明了A是完全可转换的当且仅当二部图GA*是Pfaffian的,进一步我们将该结果推广到了m×n阶{0,1}-矩阵,并且利用这一结果也可以得到第二章中的充分必要条件.作为应用,我们给出了两类完全可转换矩阵的积和多项式的具体表达式.在第五章中,我们研究了Klein瓶、Mobius带及柱面上的六角系统的完美匹配计数(物理上称为密排二聚体计数).通过对这些六角系统进行Pfaffian定向或交叉定向,并计算定向图的斜邻接矩阵的行列式,得到了Klein瓶、Mobius带及柱面上的六角系统的完美匹配计数的具体表达式.
其他文献
为优化彝良铅锌矿选矿厂磨矿条件,本文主要对影响磨矿动力学参数的4个因素:介质配比、介质充填率、磨矿浓度、球磨机转速率,进行基于响应曲面法的磨矿动力学研究及应用。首先,磨矿动力学方程参数m值和k值与时间单位无关,他们决定于被磨物料的性质和磨矿条件。m值主要取决于被磨物料的均匀性和强度以及球荷粒度特性(磨矿介质配比),k值主要由磨矿粒度决定。对现场的磨矿循环产品粒度分布和矿石力学进行检测分析,基于矿石
硫酸铵是重要的化工副产品之一,其广泛应用于蛋白质提纯、农业等行业。但在硫酸铵的工业生产中,却存在晶体粒径小、粒径分布不均匀、晶体产品品质差等问题,使得硫酸铵收益难以提高。以昆钢新区300m2烧结机烟气氨法脱硫系统为例,硫酸铵结晶工艺存在结晶影响因素多、结晶率低、形核不稳定、硫酸铵品质差等问题。为了解决上述问题,本文在硫酸铵结晶热力学数据的基础上,对影响硫酸铵结晶的主要因素进行了研究,并根据实验结果
本研究针对顶吹浸没喷枪内液态碳氢化合物燃料流动沸腾的现象进行数值模拟。在顶吹浸没熔炼技术中,顶吹浸没喷枪是向熔池添加燃料的关键设备,由不锈钢外管和碳钢内管组成,分别用于向熔池通入富氧的空气和碳氢化合物燃料。顶吹浸没喷枪从炉体顶部垂直插入渣层,喷枪外管被炉体内部的高温烟气和湍流的熔体包围。当采用液态燃料时,高温烟气及熔体的热量经外管传入内管使液态燃料温度升高,并引起流动沸腾。由于喷枪长度通常具有数米
随着社会经济的不断发展,对企业是机遇也是挑战。当前,很多生产型企业都在不断扩大规模,扩张生产经营。因此,加快企业内部全面预算管理工作的步伐是非常有必要的,不仅可以避免外部环境的风险,还可以使企业内部的问题得到有效的解决,实现企业的进一步发展。为此,本文从实际情况出发,针对生产型企业现存的全面预算管理问题进行分析,并提出相应的解决措施,以期对生产型企业的进一步发展做出一定的贡献。
心墙土石坝是水库枢纽工程中广泛使用的一种坝型,选择合适的心墙防渗土料对土石坝的防渗及安全稳定至关重要。红土广泛发育在我国云南、贵州、广西等十几个省区,充分利用当地红土作土石坝的心墙防渗土料意义重大。由于红土工程性质特殊,地震动荷载对红土破坏性较为显著,将导致心墙红土强度降低,进而危及土石坝安全稳定。因此,系统深入研究在地震荷载作用下红土心墙坝的抗震特性,对进一步推动红土心墙土石坝的建设与发展具有非
黄沙,轰鸣。戈壁滩上,随着某机场上空传来凌厉的一等战斗警报,南部战区空军航空兵某旅在某陌生地域下的一场实战化对抗训练拉开了战幕。"雷达截获!目标正沿南部山地低空突防,立即按攻击队形拦截!"正在作战空域内战斗巡逻的双机编队迅速调转机头,对向来犯之"敌"前出拦截。翻转,规避,机动,对头……正当长机即将用火控雷达锁定对向之"敌"时,雷达突然显示受干扰符号,即将锁定的目标也从雷达上消失。"不好!电磁
期刊
近几十年,越来越多的学者考虑用数学模型的方法来研究生物系统,研究并揭示其动力学性质。出于人们生产生活的实际要求,本文第二章考虑一类具有时滞捕捞项的比率依赖模型。我们利用Hopf分支理论,取时滞作为分支参数,当时滞穿过临界点增大时,系统平衡点的稳定性发生改变,分支出周期解。利用Hassard方法和中心流形定理,我们可以进一步得到周期解的分支方向和稳定性的判断公式。近些年,生物系统中出现混沌现象被许多
良宽(一七五七——一八三一),为日本越后国出云崎神宫兼名主山本以南的长子。幼名荣藏,后改孝文。十九岁时出家光照寺,为曹洞宗禅僧。名良宽,号大愚。曾入玉岛圆通寺,后为行脚僧转游各地。良宽擅歌,以歌人兼善书家,名声极高,其书法与寂严、慈云并名,但在开一代风气方面,良宽是更杰出者。无论是诗、歌还是宗教,良宽都有溯本求源的研究倾向。换言之,"反朴归真"就是良宽追究学问之所在。在书法方面也是一样。他
期刊
混沌理论是非线性科学的重要分支,在概率论和确定论两大科学体系之间架起了桥梁。由于在保密通信等多方面的应用,混沌同步吸引了越来越多的人的研究。本文利用理论推导和数值模拟相结合的方法研究了秩一混沌系统及其同步化问题,主要内容如下:1.研究了Chen和Han于2009年提出的整数阶秩一混沌系统的相应的分数阶形式的动力学特性,然后基于Barbalat’s引理,分别通过主动控制、自适应反馈控制和线性控制三种
本文主要研究了一类保序的变换半群及某些图的自同态幺半群的性质和结构,全文共分为六章.第二章主要研究了一类带有限制集的保序变换半群(?)(X,Y),刻画了(?)(X,Y)的格林关系和星格林关系,证明了(?)(X,Y 是富足半群但不是正则半群.并刻画了(?)(X,Y 的正则元,给出了(?)(X,Y 是正则半群的充分必要条件.同时,讨论了(?)(X,Y)上的一些计数问题.第三章继续讨论带有限制集的保序变