论文部分内容阅读
图的最小强迫数是指能确定图的某个完美匹配的最小边子集的大小.此概念是由Harary等在研究苯系统的强迫数的过程中提出的.更早地,Randie和Klein曾提出和强迫数有相同思想的概念,即“凯库勒结构的内自由度”,这一概念来源于化学上对分子图的共振结构的研究.设G是一个有完美匹配的图.若G的完美匹配M的子集S只包含在唯一完美匹配M中,则称S是M的一个强迫集.完美匹配M的最小强迫集的大小称作M的强迫数,记作f(G,M).在图G的所有完美匹配中,强迫数的最小值叫做G的最小强迫数,记作f(G);而最大值叫做G的最大强迫数,记作F(G).图G的所有完美匹配的强迫数构成的集合叫做G的强迫谱,即Spec(G)={k|存在一个完美匹配M使得f(G,M)=k}.张和平等证明了任意富勒烯图的强迫数都大于等于3,且有两类管状图达到下界.Kleinerman通过删除点子集的方法证明了环面方格图C2m×C2n的最大强迫数为mn.Afshani等得到了任意列连续子方格子图的强迫谱是连续的.本文主要研究了一些图类的强迫数或强迫谱.我们给出了环边连通度为3的硼氮富勒烯图的强迫谱,刻画了达到下界2的环边连通度为4的硼氮富勒烯图:得到了三类图的最大强迫数,证明了任意偶多边形链的强迫谱是连续的,探讨了两类cata型六角系统的强迫谱的连续性.全文共分为五章.第一章首先介绍本文所用到的一些基本概念,术语和记号,然后主要介绍了图的强迫数的研究背景以及相关问题的提出和研究进展,最后我们总结了本文得到的主要结果.在第二章中,我们主要探讨了硼氮富勒烯图的强迫数.根据环边连通度的不同,分两种情形去考虑.当环边连通度是3时,硼氮富勒烯图是一类特殊的管状图Tn.根据其完美匹配的特性,我们分别得到Tn的最大强迫数和最小强迫数.进一步对区间[f(Tn),F(Tn)]内的任意整数k,构造出一个完美匹配使其强迫数恰为k,从而表明Tn强迫谱是个整区间.当环边连通度为4时,根据2-可扩性得到其强迫数的下界为2,并刻画出强迫数达到下界2的所有硼氮富勒烯图,共有七个在第三章中,我们通过在图中删除特殊独立点集的方法求得非二部图C2n+1×P2m的最大强迫数为m(n+1),解决Afshani等提出的公开问题,表明环面4-8格T(p,q,t)和克莱因瓶4-8格K(p,q,t)的最大强迫数pq为能覆盖其所有顶点的四边形个数.在第四章中,我们运用Z-变换图的连通性来解决图的强迫谱的连续性问题.首先利用Z-变换图证明了任意polyoinino图的强迫谱是连续的,这一结果推广了Afshani等关于列连续子方格子图连续的强迫谱的结果,并简化了其证明过程.进而我们运用匹配可交换证得任意偶多边形链的强迫谱是连续的.另外,我们还求得当kink-面数给定时,由所有偶多边形链构成的集合中图的强迫数的界.在第五章中,我们运用Z-变换图讨论了两类cata-型六角系统的强迫谱,得到其谱要么是连续的,要么强迫谱内任意两个元素都不相继,要么只在一个位置不连续.