图的匹配强迫和反强迫问题的研究

摘要

图G的每个完美匹配M 都有一个最小子集S,使得S 不包含在G的其他完美匹配中,该子集S的势称为M的强迫数. 从对立面考虑,在E (G)\M 中有一个最小集合S,使得G?S 有唯一完美匹配M ,该集合S的势称为M的反强迫数.G中所有完美匹配的强迫数(反强迫数)的最小和最大值分别称为G的最小和最大强迫数(反强迫数). 图的匹配强迫和反强迫数的研究来源于有机分子的Kekulé 结构的内自由度，先由 Randi? 和 Klein 提出. 近年来在图理论及应用研究方面都取得了重要进展. Adams 等和邓凯等分别证明了确定二部图的一个完美匹配的强迫数和反强迫数是 NP-完备的. 邓凯和张和平证明了图的最大反强迫数不超过图的基圈数. 徐丽琼等证明了有完美匹配的六角系统H的最大强迫数等于其Clar数,即,一个最大不交共振六边形面的集合 (由尽可能多的不交六边形面构成的集合，使得其中每个面的边界都是 H的同一个完美匹配的交错圈)的势. 雷洪川等证明了 H的最大反强迫数等于其 Fries 数，即，最大共振六边形面集合的势. 苯类碳氢化合物的Clar 数和 Fries 数是衡量其稳定性的化学指标. 对新型碳族球形分子–富勒烯,张和平等和杨琴等分别研究了其最小强迫数和反强迫数. 本文我们首先考虑了图的最大反强迫数的新上界. 其次讨论了(4，6)-富勒烯图的最大强迫数和最大反强迫数,并且研究了(4，6)-富勒烯图的最大不交共振六边形面的集合. 最后我们致力于刻画最小强迫数等于3的富勒烯图. 全文共分五章,具体如下: 第一章，我们首先介绍了文中用到的一些基本概念、术语和记号. 其次介绍了匹配强迫数和反强迫数问题的研究背景及研究进展. 最后概述了本文的主要结论. 第二章，我们得到了有完美匹配的图 G的最大反强迫数的一个新的严格上界,这个上界只依赖于G的顶点数和边数. 当图G的边数比较多时,这个上界优于已有的上界. 如果G的一个完美匹配的反强迫数达到这个新上界,那么称这个完美匹配是 “nice”的. 我们刻画了图的nice完美匹配，并且证明了图的nice完美匹配的个数等于它的各个卡氏积因子的nice完美匹配的个数之和. 此外,我们定义了图的两种扩张运算，并且证明了以一条边为初始图，每个达到最大反强迫数上界的图都可以通过这两种扩张运算得到. (4，6)-富勒烯图G是一个连通平面3-正则图,它的每个面是四边形或者六边形. 将六角系统Clar数的概念推广到图G得到G的共振数，即，最大不交共振面集合的势. 类似地，G的Fries数是其最大共振面集合的势. 在第三章中,我们把有完美匹配的六角系统的结论推广到了 (4，6)-富勒烯图 G，证明了 G的最大强迫数等于其共振数,最大反强迫数等于其Fries数. 进一步,我们分别给出了G的最大强迫数和反强迫数的仅依赖于G的顶点数的计算公式. 称(4，6)-富勒烯图G的一个最大不交共振六边形面的集合为G的一个Clar公式,其中所含六边形的个数记为Cl6(G). G的一个Clar公式H和G?V (H)的一个完美匹配构成G的一个Clar结构. 第四章中,对(4，6)-富勒烯图G,我们首先得到了Cl6(G)的仅依赖于G中顶点数的计算公式. 其次刻画了G的Clar公式. 最后应用该结论,我们给出了G的Clar公式和Clar结构的计数公式,这些公式只依赖于G的顶点数和G的一些容易识别的固定子图的个数. 富勒烯图是一个连通平面3-正则图,它的每个面是五边形或者六边形. 张和平等证明了富勒烯图的最小强迫数大于等于 3. 他们提出了一个公开问题: 刻画最小强迫数为 3的富勒烯图. 我们知道有 24 个顶点的富勒烯图只有一个，记为F24 . 在第五章中，我们发现 F24的最小强迫数为 2，并且说明了这是唯一一个反例. 应用富勒烯图的环5-边割、环6-边割、环7-边割等已知结论,通过图扩充的方法我们解决了上述公开问题. 特别地，除 F24 外，每个反强迫数等于 4的富勒烯图的最小强迫数都等于3.

目录

第一个书签之前

Abstract

第一章 引言

1.1 基本概念与记号

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

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

1.4 本文主要结论

1.4.1 图的最大反强迫数的一个新的严格上界

1.4.2 (4, 6)-富勒烯图的最大强迫数和最大反强迫数

1.4.3 (4, 6)-富勒烯图的Clar结构的计数

1.4.4 刻画最小强迫数等于3的富勒烯图

第二章 图的最大反强迫数的一个新的严格上界

2.1 引言

2.2 新上界和nice完美匹配

2.3 构造极值图

2.4 卡氏积分解

2.5 进一步的应用

第三章 (4, 6)-富勒烯图的最大强迫数和最大反强迫数

3.1 引言

3.2 (4, 6)-富勒烯图的最大反强迫数

3.3 (4, 6)-富勒烯图的最大强迫数

第四章 (4, 6)-富勒烯图的Clar结构的计数

4.1 引言

4.2 准备工作

4.3 刻画Clar公式

4.4 计算Clar公式和Clar结构的个数

第五章 刻画最小强迫数等于3的富勒烯图

5.1 引言

5.2 准备工作

5.3 最小强迫数为3的富勒烯图的性质

5.4 最小强迫数为3的富勒烯图的广义补丁

5.5 构造最小强迫数为3的所有富勒烯图

参考文献

在学期间的研究成果

致 谢