关于一些图类的强迫与反强迫多项式的研究

摘要

图G的完美匹配M的强迫数由Klein和Randi?与Harary等分别在化学与数学中先后引入，具体定义为 M 中边的最少条数，使得这些边的集合不包含在 G的其它完美匹配里. 而 M的反强迫数是指不在 M 中边的最少条数，使得从 G 中删除这些边之后得到的子图有唯一的完美匹配 M. 一般地，二部图的完美匹配的强迫数与反强迫数的计算问题都是NP-完全的. 研究表明，一个六角系统的最大强迫数等于它的Clar 数，而最大反强迫数等于它的Fries 数，且 Clar 数与 Fries 数都可以用来衡量芳香烃的分子稳定性.在一般图中，每个完美匹配的强迫数不小于最多不交交错圈的个数，Guenin 和Thomas 表明对不含 K3,3 或希伍德图的偶剖分作为好子图的二部图前面两者有相等关系; 每个完美匹配的反强迫数不小于最大相容交错集的大小，并且对不含K3,3的剖分的二部图前面两者有相等关系. 近几年，关于图的最大最小强迫数与反强迫数，以及强迫谱与反强迫谱的研究有了一些较深入的讨论. 然而，计算一个图中有多少个完美匹配具有相同的强迫数与反强迫数是匹配强迫问题的一个新领域. 在此基础上，本文提出了图的强迫多项式，即将具有相同强迫数的完美匹配个数作为系数的计数多项式，并从图G的强迫多项式中得到了一些重要的拓扑指标. 比如,其多项式的系数之和是G的完美匹配的个数，将其多项式的导数中变元取值 1 时可以得到 G的所有完美匹配强迫数之和,这两个指标相除可以得到G的平均强迫数. 从图的强迫多项式中也可以得到它的最大与最小强迫数及强迫谱. 类似地，Hwang等将具有相同反强迫数的完美匹配个数作为系数的计数多项式定义为反强迫多项式,从中同样可以得到一系列拓扑指标. 本文计算了一些图类的强迫与反强迫多项式. 方法是首先分析图的组合结构给出递推关系,再结合组合计数方法做出具体表达式. 主要结构如下. 第一章中我们介绍了两类重要的平面二部图,综述了匹配强迫与反强迫数的研究背景. 第二章中我们引入了图的匹配强迫多项式并得到了其基本性质. 给出了cata-型六角系统强迫多项式的递推关系. 特别地，我们利用生成函数的方法推导出了 zigzag 六角链强迫多项式的具体表达式并得到了其平均强迫数的渐近行为,从中推导出了由Klein和Randi?得到的zigzag六角链的自由度. 第三章中我们给出了平行四边形六角系统强迫多项式的递推关系及具体表达式，最大与最小强迫数以及当一个指标趋向于无穷时平均强迫数的渐近行为,并通过组合计数方法也给出了它的强迫多项式. 第四章中我们研究了图的匹配反强迫多项式. 得到了具有强迫边的六角系统的反强迫多项式的递推关系，从中推导出了其反强迫谱的连续性. 特别地，我们给出了平行四边形六角系统反强迫多项式的具体表达式,最大与最小反强迫数以及当一个指标趋向于无穷时平均反强迫数的渐近行为. 第五章中我们分别给出了2×n格子图与3×2n格子图的强迫与反强迫多项式的具体表达式,以及强迫与反强迫谱. 第六章中我们列出了当 3≤n≤36 时广义彼得森图 P (n，2)的强迫多项式以及当n≥37时P (n，2)的强迫谱[「n/12」+1,「n+3/7」+δ(n)]∪[「n+2/6」,「n/4」],其中δ(n)=1若n≡3 (mod 7),而其它情况δ(n)=0,它是两个整区间的并.

目录

第一个书签之前

Abstract

第一章 引言

1.1 图的基本概念, 记号与基本引理

1.2 六角系统与方格子图的性质

1.3 匹配强迫问题的研究背景及进展

1.4 匹配反强迫问题的研究背景及进展

1.5 本文的主要结果

第二章 cata-型六角系统的强迫多项式

2.1 图的强迫多项式的定义及重要引理

2.2 六角链

2.3 zigzag六角链

2.4 cata-型六角系统

第三章 平行四边形六角系统的强迫多项式

3.1 平行四边形六角系统

3.2 与平行四边形六角系统相关的六角系统

第四章 具有强迫边的六角系统的反强迫多项式

4.1 图的反强迫多项式的定义及重要引理

4.2 具有反强迫边的六角系统

4.3 平行四边形六角系统

4.4 具有强迫边的六角系统

第五章 一些格子图的强迫及反强迫多项式

5.2 2n格子图的反强迫多项式

5.3 32n格子图的强迫多项式

5.4 32n格子图的反强迫多项式

第六章 一类广义彼得森图的强迫谱

6.1 两类完美匹配

6.2 第一类完美匹配的强迫数

6.2.1 强迫数的最大值

6.2.2 强迫数的最小值

6.2.3 连续性

6.3 第二类完美匹配的强迫数

6.3.1 强迫数的最大值

6.3.2 强迫数的最小值

6.3.3 连续性

参考文献

在学期间的研究成果

致 谢