二部图的匹配强迫数

论文摘要

设G是有完美匹配的图．若G的完美匹配M的子集S仅包含在唯一完美匹配M中，称S是M的一个强迫集．M的最小强迫集的大小叫做M的强迫数，记作f（G，M）．G的所有完美匹配的强迫数的最小值叫做G的最小强迫数，记作f（G），而最大值叫做G的最大强迫数，记作F（G）．G的所有完美匹配的强迫数的集合叫做G的匹配强迫数的谱．P.Adams等人表明对最大度是3的二部图，最小匹配强迫集问题是NP-完全的．图论中的完美匹配相当于有机分子的凯库勒结构，匹配强迫数来源于化学上凯库勒结构的自由度．图论和组合数学中，有多个问题的研究出现了“强迫”的思想，例如图的染色，测地集，拉丁方和区组设计等．近几年来关于完美匹配方面的强迫概念也得到了一定的扩展，提出了全局强迫数，反凯库勒数，反强迫数和强迫六角形等概念．本论文分七章研究二部图的匹配强迫数问题．我们给出了M．E．Riddle的尾点法改进，并应用于环面六角系统，环面方格图，二部克莱茵瓶六角系统，硼氮富勒烯，矩形方格图和柱面方格图等图类的强迫数求解．Riddle从Hall定理出发，通过建立二部图颜色集的序，给出了强迫数的一个下界．在第二章中，我们改进了Riddle颜色集序的概念和最小强迫数下界的结论，给出标准序的概念，并得到自然数k是二部图的某个完美匹配的强迫数的必要条件，和最小强迫数等于颜色集的所有标准序尾点数最小值的充要条件．环面六角系统是环面上的3-正则二部图，其每个面都是六角形面．环面六角系统能够由三元组（p,q,t）来表示（p≥1，q≥1，0≤t≤p-1），故记作H（p，q，t）.在第三章中，我们用尾点法得到f（H（p，q，t））≥min{p，q}，等号成立当且仅当p≤q或p>q且t=0，p-1，…，p-q．一般地，我们得到环面六角系统的最小强迫数等于其上可作出的最大三角形的边长．基于此结果，我们设计了一个线性算法来计算H（p，q，t）的最小强迫数．Ridlle曾研究了环面方格图C2m×C2n的最小强迫数．在第四章中，我们对C2m×C2n进行扩充，增加一个旋转参数t，定义了环面方格图S（p,q,t），其中p≥1，q≥1，0≤t≤p-1．与H（p，q，t）是3-正则的不同，S（p，q，t）是环面4-正则二部图．我们得到：当p≤q时，f（S（p，q，t））=2p；当p>q且0≤t<q，或p>q且p-q+1≤t≤p-1时，f（S（p，q，t））=2q；当p>q，q≤t≤p-q时，f（S（p，q，t））等于S（p，q，t）上周长最小的特征矩形的半周长加1．二部克莱茵瓶六角系统也可以由一个六角格子网络L上的平行四边形P通过底边的粘贴来生成，由两个参数p和q确定，记为K（p，q）．在第五章我们得到：若p≤q，则f（K（p，q））=p；若q<p≤2q，则f（K（p，q））=q；当p>2q时，q≤f（K（p，q））≤（?）p/2（?）+（?）q/2（?）．硼氮富勒烯图是含有六个四边形面及若干六边形面的3-正则平面二部图．在第六章中，我们表明了硼氮富勒烯图的最大强迫数与面独立数和共振数都是相等的．利用尾点法，给出了硼氮富勒烯B12N12，B16N16，B22N22，B27N27和B28N28的强迫数，并确定了三类管长任意的戴帽硼氮纳米管的最大强迫数，以及最小强迫数上界．在第七章，我们给出二部图Pm×Pn的一个匹配强迫集构造方法，得到f（Pm×Pn）的上界，并部分解决了P．Afshani等人提出的一个公开问题，即确定了Pm×C2n的强迫数的谱．

论文目录

• 摘要
• ABSTRACT（英文摘要）
• 第一章 引言
• 1.1 基本概念,术语和记号
• 1.2 匹配强迫数的背景和研究进展
• 1.3 本论文主要结论
• 1.3.1 二部图的强迫数基本理论
• 1.3.2 环面六角系统H（p,q,t）的强迫数
• 1.3.3 环面方格图S（p,q,t）的强迫数
• 1.3.4 克莱茵瓶六角系统K（p,q,t）的匹配强迫数
• 1.3.5 硼氮富勒烯的强迫数
• 1.3.6 二部矩形方格图和柱面方格图的强迫数
• 第二章 二部图匹配强迫数基本理论
• 2.1 尾点法的基本理论
• 2.2 匹配强迫数是k的必要条件
• 2.3 点集的强迫域
• 2.4 匹配强迫数和交错圈的关系
• 第三章 环面六角系统H（p,q,t）的最小匹配强迫数
• 3.1 环面六角系统和基本性质
• 3.2 f（H（p,q,t））的下界和几类特殊情形的强迫数
• q≥1,1≤t≤p-q-1,的强迫数'>3.3 H（p,q,t）,p>q≥1,1≤t≤p-q-1,的强迫数
• 3.3.1 H（p,q,t）,1≤t≤p-q-1,的强迫数
• 3.3.2 求f（H（p,q,t））的算法和计算复杂性
• 第四章 环面方格图S（p,q,t）的强迫数
• 4.1 环面方格图和基本性质
• 4.1.1 圈结构
• 4.1.2 强迫域引理
• 4.1.3 同构性
• q且0≤t4.2 p≤q,p>q且0≤t
• q,q≤t≤p-q时S（p,q,t）的强迫数'>4.3 p>q,q≤t≤p-q时S（p,q,t）的强迫数
• 4.3.1 准备工作
• 4.3.2 主要结论
• 第五章 二部克莱茵瓶六角系统K（p,q,t）的强迫数
• 5.1 基本概念和预备知识
• 5.2 克莱茵瓶六角系统K（p,q）,p≤2q,的强迫数
• 2q,的强迫数'>5.3 克莱茵瓶六角系统K（p,q）,p>2q,的强迫数
• 第六章 硼氮富勒烯图的匹配强迫数
• 6.1 硼氮富勒烯及预备知识
• 6.2 BN-富勒烯的最大强迫数和面独立数
• 6.2.1 基本概念和预备知识
• 6.2.2 面独立数,完美凯库勒结构和完美Clar结构
• 6.2.3 BN-富勒烯的最大强迫数
• 6.2.4 常见BN-富勒烯的最大强迫数和面独立数
• 12N₁₂和B₁₂N₁₂-Armchair型BN-SWNT的强迫数'>6.3 B₁₂N₁₂和B₁₂N₁₂-Armchair型BN-SWNT的强迫数
• 12N₁₂的匹配强迫数的谱'>6.3.1 B₁₂N₁₂的匹配强迫数的谱
• 12N₁₂-Armchair型BN-SWNT的强迫数'>6.3.2 B₁₂N₁₂-Armchair型BN-SWNT的强迫数
• 16N₁₆和B₁₆N₁₆-Zigzag型BN-SWNT的强迫数'>6.4 B₁₆N₁₆和B₁₆N₁₆-Zigzag型BN-SWNT的强迫数
• 16N₁₆的强迫数'>6.4.1 B₁₆N₁₆的强迫数
• 22N₂₂的强迫数'>6.4.2 B₂₂N₂₂的强迫数
• 28N₂₈的强迫数'>6.4.3 B₂₈N₂₈的强迫数
• 16N₁₆-Zigzag型BN-SWNT的强迫数'>6.4.4 B₁₆N₁₆-Zigzag型BN-SWNT的强迫数
• 27N₂₇和B₂₇N₂₇-Zigzag型BN-SWNT的强迫数'>6.5 B₂₇N₂₇和B₂₇N₂₇-Zigzag型BN-SWNT的强迫数
• 27N₂₇的强迫数'>6.5.1 B₂₇N₂₇的强迫数
• 27N₂₇-Zigzag型BN-SWNT的强迫数'>6.5.2 B₂₇N₂₇-Zigzag型BN-SWNT的强迫数
• 第七章 二部矩形方格图和柱面方格图的匹配强迫数
• m×P_n的强迫数'>7.1 P_m×P_n的强迫数
• m×C_2n的强迫数的谱'>7.2 P_m×C_2n的强迫数的谱
• 参考文献
• 附录A 在读期间发表和完成的主要论文
• 致谢