论文部分内容阅读
图G的完美匹配M的强迫数由Klein和Randic与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和Randic得到的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若≡3(mod 7),而其它情况δ(n)= 0,它是两个整区间的并.