论文部分内容阅读
图多项式是研究满足某些性质的图结构计数问题的有力工具，可追溯到一百多年前Birkhoff为解决四色猜想所引入的色多项式.尽管四色猜想尚未能借助色多项式而获得证明，由色多项式发展而来的各种图多项式理论在图的理论研究及实际计数问题中已扮演了重要的角色. 色多项式引入的初衷是研究平面图顶点着色的方法数，后被证明是一个多项式.由此，该多项式的某些代数性质成为了重要的研究内容，其中最经典的是对其系数的代数性质及组合含义的研究.与色多项式显著不同的是，许多经典的图多项式，如独立多项式、匹配多项式、覆盖多项式等，是首先赋予系数以明确的组合含义而定义的.另一类图多项式则是以图的某种形式的子图而展开的多项式，例如著名的Tutte多项式.研究表明，这些从不同角度定义的图多项式相互间有着密切的关联.一般来说，它们均可表为边子图或点子图的展开式，其中容斥原理扮演着重要的角色.容斥原理也为探索更具一般性的图多项式提供了一个有效的思路，例如Dohmen等引入的双变量色多项式、Averbouch等引入的边消去多项式以及Tutte多项式等. 图多项式大多与一些重要的计数问题密切相关.因而图多项式的计算是一个重要的研究课题.早在1932年，Whitney给出的色多项式破圈定理是图多项式研究中一个经典且重要的结果，它事实上也给出了色多项式的系数一个很好的组合解释.其主要思想也深刻地影响了后继的研究者，如Stanley正是受Birkhoff和Whitney的影响和启发，定义了色对称函数.在很多领域的计数问题中，均能看到破圈定理的各种推广形式.Dohmen，Trinks和Naiman，Wynn等分别从计数和代数拓扑结构的角度给出了抽象化的破圈定理，且统一了前人的若干研究成果. 本文基于容斥原理的基本思想研究一些经典图多项式之间的内在关联.首先提出了‘补集对偶’与‘点-边对偶’的思想.基于这一思想，任何以点子集展开式或边子集展开式在关联关系下均有其对偶形式，如点独立多项式和点覆盖多项式是补集对偶的，而点覆盖多项式和边覆盖多项式是点-边对偶的.作为应用，我们确定了色多项式、独立多项式、覆盖多项式及控制多项式等经典的图多项式的对偶形式.其中有一些是已知多项式，而另一些则是从未被定义和研究过的.特别地，运用对偶思想，本文的第二部分给出了Alexander和Mink计算独立多项式的一个重要结果的一个非常简单的证明，并将它推广到超图上，得到了关于超图的t阶独立集数目的计数公式. 在第三部分，我们建立了图的匹配结构与基于容斥原理的抽象‘破圈’结构之间的联系，给出了破圈定理的简单证明.作为应用，利用该匹配表示和独立多项式的边子集展式，提出了较之于破圈更一般的结构，即破星结构.由此，给出了独立多项式的破星定理.最后，我们给出了抽象化破圈定理的一种递归表示，并进一步改进了独立多项式的计算.