关于图的积和多项式若干问题的研究

摘要

图的积和多项式是对图的邻接矩阵的特征矩阵求积和式运算而得到的多项式，即per(xI-A(G))，这里A(G)是图G的邻接矩阵，I是单位矩阵，关于矩阵积和式的计算，Valiant已经证明是#P-完全问题，即使限定在(0，1)矩阵中，因为计算上的困难，尽管图的积和多项式概念的提出已三十年有余，但该领域的研究进展非常缓慢．本文考虑了图的积和多项式的三个问题：用积和多项式确定图、图的积和多项式根的性质以及定向图的斜邻接矩阵的积和多项式．　　Mcrris等认为布区分不是树的图时积和多项式可能要比特征多项式好一些，他们发现有五对不能被特征多项式所区分的图可以被积和多项式所区分，利用积和多项式去区分图，之前并没有系统的研究，本文首先探讨在区分不是树的图时积和多项式是不是确实要优于特征多项式，或者更一般地我们去研究哪图可以被它们的积和多项式所确定，这里一个图G称为能被它的积和多项式所确定是指对于任意与G有相同积和多项式的图H，总有H与G是同构的.　　我们首先给出了由图的积和多项式可确定的一些性质．利用这些性质，证明了完全图、星、正则完全二部图以及奇圈可以被它们的积和多项式所确定．然后我们表明了路、偶圈以及棒棒糖图不能被积和多项式所确定，而它们已证明均可被特征多项式所确定．如果限定存连通图中考虑，我们证明了路、不能被4整除的偶圈、奇棒棒糖图以及围长等于4的偶棒棒糖图可以被积和多项式所确定.　　由于积和式的定义与行列式很相似，我们考虑图的积和根（积和多项式的根）与特征根之问是不是有着相似的性质.我们知道图的特征根伞为实数，二部图的特征根关于坐标原点对称，那么这些性质对于图的积和根是否也成立？本文对这些问题给出了明确的回答．我们证明了任意图不会有负的积和根：二部图没有非零的实积和根；对于至少有一条边的图，它一定存在非实的复秋和根；二部图的积和根在复平面上关于坐标实轴和虚轴对称.　　我们知道定向图的斜邻接矩阵在图的完美匹配计数中起着重要的作用．本文研究了定向图斜邻接矩阵的积和多项式，得到了其系数的Saclis-型公式，并将该结果推广到赋权的定向图上，这为计算一般实斜对称矩阵的积和多项式提供了一种图论的方法．我们证明了一个图的所有定向图的斜邻接矩阵有相同的积和多项式当且仅当这个图没有偶圈，进一步地，当一个图没有偶圈时，它的任意定向图的斜邻接矩阵的积和多项式恰好等于这个图的匹配多项式．最后对定向图的积和根与其底图的积和根之间的关系做了探讨.

目录

第一个书签之前