【摘 要】
:
设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-完全的.图论中的完美
论文部分内容阅读
设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的强迫数的谱.
其他文献
图的谱理论是代数图论的主要研究领域之一,涉及图的谱和laplacian谱,前者起源于量子化学.1931年,E.Hückel提出了分子轨道理论,建立了分子轨道能级和分子图的谱之间的联系,大大推动了图的谱理论研究.图的谱理论主要是利用矩阵论,结合组合论和图的结构性质研究图的各种矩阵的谱,讨论这些谱与图的结构性质及图的不变量之间的关系.L.Collatz和U.Sinogowitz的数学论文“Spektr
曲面Fullerene图是嵌入到曲面上的3-正则有限图,它的每个面的边界为5长或6长圈.这样的嵌入只能在球面、环面、克莱因瓶和射影平面上实现,其五边形面的个数分别为12,0,0和6.而球面Fullerene图就是通常的Fullerene图,即碳族Fullerene的分子图.关于Fullerene图的与匹配理论相关的问题已得到广泛关注和研究.本文分四章对曲面Fullerene图进行了研究.我们确定了
本文主要研究E-反演半群的性质和同余,全文共分六章。第一章我们引入并研究了E-反演半群S上的正则同余.同时引入了E-反演半群上的核正规系,证明了S上的每一个正则同余都是由其核正规系所唯一确定的,并用核正规系刻画了E-反演半群S上的正则同余.第二章研究了E-反演半群S上正则同余与其特征迹的关系,确定了具有相同特征迹的最小和最大正则同余.同时也刻画了具有相同特征迹(?)的所有正则同余.建立了S上具有特
本博士论文主要是研究具p(x)-Laplacian算子的在RN中的有界光滑域上的形如下面的椭圆方程问题的解的存在性,多解性及本征值问题。这是一个新的而有趣的课题。本文的特点之一是在边界(?)Ω上有包含|u|p(x)-2u的项。我们根据b(x)的形式,考虑了Robin边值问题与Steklov本征值问题。在Robin边值问题中,根据非线性项h(x,u)的特点,我们分四种情况进行讨论。即,Robin本征
如果图G的一个子图F是G的一个支撑子图,则称F是G的一个因子.Akiyama和Kano将图的因子问题分为两类,分别称为:度因子问题和分支因子问题.如果用因子的度来描述这个因子,则称该因子为度因子.例如,如果一个因子F的所有度都等于1,F是一个1-因子.与此同时,哈密尔顿圈问题可以看成是寻找一个连通的因子使得每个点的度恰好等于2.另一个方面,如果一个因子是用图的概念来描述,则成该因子为分支因子.例如
测度链上动力方程理论不但可以统一微分方程和差分方程、更好地洞察二者之间的本质差异,而且还可以更精确地描述那些有时在连续时间出现而有时在离散时间出现的现象。所以,研究测度链上动力方程既有理论意义,又有现实基础。类似于微分方程和差分方程,非线性项变号的边值问题同样是一个困难且重要的问题。为此,我们研究了测度链上非线性项变号的p-Laplacian奇异多点边值问题正解的存在性。借助于上下解方法和Scha
由于模式和初始场不可避免的误差,气候模拟仍然存在明显误差。本文研究了在这种形势下利用区域气候模拟气候变化,特别是模拟局地的外强迫变化改变引起的气候变化时可能出现的问题。数值试验表明,尽管现有的区域气候模式能够较好地模拟气候的空间分布和季节变化的基本特征,但是用于研究局地外强迫变化的气候效应而进行的敏感性试验时可能造成大的相对误差,使研究结果失去可信性。本文认为在研究外强迫变化的气候效应时,在某些条
这篇博士学位论文主要研究了两类非线性发展方程的动力学行为。一类是带有黏弹性项和非线性项的波方程:我们使用两种不同的方法克服了在[60]中Salim所采用的方法面临的困难,证明了如果黏弹项满足:且那么当初始能量E(0)(2p)/κE(0)时,其中κ是某个正数,则方程(1)的解u(t)在有限时间内依H01(Ω)范数爆破.另外我们利用Salim[63]中的方法
本论文主要研究了毕竟正则半群上的R-unipotent同余和纯整同余、Einversive半群上的正则同余以及周期半群簇子簇格上的同余与算子。具体工作如下:首先利用弱逆把研究正则半群同余的核-迹方法推广到了毕竟正则半群上,分别引入了毕竟正则半群的R-unipotent同余对和纯整同余对,并证明了毕竟正则半群上的R-unipotent同余(纯整同余)由R-unipotent同余对(纯整同余对)唯一确
图的边连通度和超边连通性常用来度量网络的可靠性,但是当两个图具有相同的边连通度和超边连通性时,就无法对其可靠性进行比较.因此,为了更精确地度量网络可靠性,人们提出了m-限制边连通度的概念:设m是正整数,连通图G的边割S称为m-限制边割,如果G-S的每个连通分支都至少包含m个顶点:G中最小m-限制边割的基数称为图G的m-限制边连通度,记为λm(G).当m=2时,λ2(G)称为图G的限制边连通度,通常