特殊图类的偶匹配可扩性

论文摘要

匹配理论是图论的核心内容之一.由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论结果.例如,刻画偶图具有完美匹配的Hall定理、刻画一般图具有完美匹配的Tutte定理、不具有完美匹配图的Gallai-Edmonds结构定理、求偶图最大权匹配的匈牙利方法、求非偶图最大权匹配的开花算法等,都是影响深远的传世之作.同时关于匹配的一系列研究专题不断涌现出来.例如,匹配多面体、基本图（elementary graph）、因子临界图、完美匹配计数等都成为活跃的研究领域.匹配可扩性―包括k-可扩性、导出匹配可扩性和k-因子临界性―也是其中之一. k-因子临界图和k-可扩图有密切的关系: 2k-临界图是k-可扩的;对于每一个连通的非偶图,如果它是k-可扩的,k是偶数,那么它是k-因子临界的.在k-可扩图、导出匹配可扩图和k-因子临界图的研究工作基础上,考虑到非偶图匹配问题与偶图匹配问题有本质差别的事实,王秀梅[1]在2005年提出另外一个新的概念―偶匹配可扩图.称图G的匹配M是偶匹配,是指M关联的顶点集在G中的导出子图是偶图.称图G是偶匹配可扩的（简称BM-可扩的）,是指G的每一个偶匹配都可以扩充为G的一个完美匹配.基于以下两方面的动机,BM-可扩图是值得深入研究的.一方面,BM-可扩图与其他匹配可扩图的关系很密切,构成了一个整体:其中m（G）是图G的最大匹配的基数.事实上,对BM-可扩图的任何研究进展都是对整个匹配可扩性理论的贡献.特别地,揭示从偶图匹配到非偶图匹配的演变规律也是有重要意义的.另一方面,BM-可扩图在化学图论中也有潜在的应用.在量子化学中,一个分子图G的Kekul′e结构就是完美匹配M;所谓共振圈就是M-交错圈.共振圈中的匹配实际上是一个偶匹配,它包含于G的完美匹配之中.因此共振圈概念与BM-可扩图有着自然的联系.正因如此,在已知的BM-可扩图中,其Clar指标（两两不相交的共振圈的最大数目）达到最大,可见对应分子结构具有最大可能的谐振能量.从Kekul′e结构计数的观点上看,这类分子结构由于完美匹配数目很大,也有良好的稳定性.在已有的理论中,关于k-可扩图、导出匹配可扩图、k-因子临界图的研究内容,除了基本性质外主要集中在:结构特征、与图参数的关系、特殊图类的刻画、极图问题等.在系统地掌握该领域的文献资料和前沿工作的基础上,本学位论文对王秀梅提出的新概念― BM-可扩图的研究也是围绕上述主流课题（特殊图类Halingraphs、K1,3-free bicritical graphs）进行的,本学位论文主要取得如下两个方面的创新成果.1.哈林图是偶匹配可扩的充要条件本文证明了判定哈林图H = （T C）是否为偶匹配扩图的充分必要条件问题:哈林图H = （T C）是BM-可扩的充分必要条件是它的特征树T同构于K1,3、K1,5或者K1,7.2.无爪双临界偶匹配可扩图的结构特征本文主要证明了无爪双临界偶匹配可扩图的几个性质.所有的这些结果在以后的研究中会起到基础作用.关于BM-可扩图与因子临界图及双临界图的关系,王秀梅已经证明了:如果G是BM-可扩图,那么G或者是双临界的或者是可均衡分解的.如果G是可均衡分解的,那么G?S的每一个分支都是因子临界的,其中S是G的一个极大屏障.本文得到的结果如下: （1.）对于任意临界偶匹配可扩图G,如果{u,v}是G的点割,那么点{u}邻接点{v}. （2.）无爪双临界偶匹配可扩图是3连通的. （3.）对于任意无爪临界偶匹配可扩图G,如果{x,y,z}是G的点割,那么点割{x,y,z}是G的独立集,并且G?{x,y,z}仅有两个分支,奇分支G1、偶分支G2,这里|G1| = 1、|G2|≥6.

论文目录

• 中文摘要
• 英文摘要
• 引言
• 第一章 绪论
• 第一节 基本概念与常用记号
• 第二节 简单地回顾匹配可扩性的发展状况
• 第二章 Halin 图的偶匹配可扩性
• 第一节 Halin 图的概念与基本结构特征
• 第二节 Halin 图偶匹配可扩的充要条件
• 第三章 关于偶匹配可扩图的一些其它结果
• 第一节 无爪双临界偶匹配可扩图的性质
• m×K_n 的偶匹配可扩性'>第二节 C_m×K_n的偶匹配可扩性
• 结论
• 参考文献
• 攻读硕士学位期间的研究成果
• 致谢