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

发布时间：2023-01-30 22:22

　　图G的完美匹配M的强迫数由Klein和Randic与Harary等分别在化学与数学中先后引入,具体定义为M中边的最少条数,使得这些边的集合不包含在G的其它完美匹配里.而M的反强迫数是指不在M中边的最少条数,使得从G中删除这些边之后得到的子图有唯一的完美匹配M.一般地,二部图的完美匹配的强迫数与反强迫数的计算问题都是NP-完全的.研究表明,一个六角系统的最大强迫数等于它的Clar数,而最大反强迫数等于它的Fries数,且Clar数与Fries数都可以用来衡量芳香烃的分子稳定性.在一般图中,每个完美匹配的强迫数不小于最多不交交错圈的个数,Guenin和Thomas表明对不含K3,3或希伍德图的偶剖分作为好子图的二部图前面两者有相等关系;每个完美匹配的反强迫数不小于最大相容交错集的大小,并且对不含K3,3的剖分的二部图前面两者有相等关系.近几年,关于图的最大最小强迫数与反强迫数,以及强迫谱与反强迫谱的研究有了一些较深入的讨论.然而,计算一个图中有多少个完美匹配具有相同的强迫数与反强迫数是匹配强迫问题的一个新领域.在此基础上,本文提出了图的强迫多项式,即将具有相同强迫数的完美匹配个数作为系数的... 

【文章页数】：125 页

【学位级别】：博士

【文章目录】：
中文摘要
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.1 2×n格子图的强迫多项式
    5.2 2×n格子图的反强迫多项式
    5.3 3×2n格子图的强迫多项式
    5.4 3×2n格子图的反强迫多项式
第六章 一类广义彼得森图的强迫谱
    6.1 两类完美匹配
    6.2 第一类完美匹配的强迫数
        6.2.1 强迫数的最大值
        6.2.2 强迫数的最小值
        6.2.3 连续性
    6.3 第二类完美匹配的强迫数
        6.3.1 强迫数的最大值
        6.3.2 强迫数的最小值
        6.3.3 连续性
参考文献
在学期间的研究成果
致谢


【参考文献】：
期刊论文
[1]石墨烯的生物安全性研究进展[J]. 田甜,吕敏,田旸,孙艳红,李晓霞,樊春海,黄庆.  科学通报. 2014(20)
[2]FORCING BONDS OF A BENZENOID SYSTEM[J]. 张福基，李学良.  Acta Mathematicae Applicatae Sinica（English Series）. 1996(02)
[3]A THEOREM CONCERNING PERFECT MATCHINGS IN HEXAGONAL SYSTEMS[J]. 张福基,陈荣斯.  Acta Mathematicae Applicatae Sinica（English Series）. 1989(01)
[4]THE CONNECTIVITY OF Z-TRANSFORMATION GRAPHS OF PERFECT MATCHINGS OF HEXAGONAL SYSTEMS[J]. 张福基,郭晓峰,陈容思.  Acta Mathematicae Applicatae Sinica（English Series）. 1988(02)



本文编号：3733481