平面图的强迫集、反强迫集与交错集之间的关系

发布时间：2018-01-16 12:09

  本文关键词：平面图的强迫集、反强迫集与交错集之间的关系　出处：《兰州大学》2016年博士论文　论文类型：学位论文

  更多相关文章： 六角系统 方格子图 完美匹配 Clar数 Fries数 强迫数 反强迫数 共振集 交错集 交错圈 非交叉的相容交错集 好子图 三亚苯

【摘要】：设G是一个图.G的完美匹配是指覆盖G中所有顶点的两两不交边的集合.设M是G的一个完美匹配,S?E(G).若S?M且S不被包含于G的其它完美匹配,则称S是M的强迫集;若S?E(G)\M且G-S有唯一的完美匹配M,则称S是M的反强迫集.M的最小强迫集和最小反强迫集的大小分别称为M的强迫数和反强迫数,记作f(G,M)和af(G,M).G中所有完美匹配的强迫数的最大值和反强迫数的最大值分别称为G的最大强迫数和最大反强迫数,记作F(G)和Af(G).边交替出现在M和E(G)\M中的圈称为M-交错圈.两个M-交错圈称为相容的,如果它们要么不相交要么仅相交于M中的边处.对于平面二部图G,Pachter等人证明了f(G,M)等于G中互不相交的M-交错圈的最大个数,雷洪川等人证明了af(G,M)等于G中相容的M-交错圈的最大个数.设R是平面图G中若干内面的集合.若G有一个完美匹配M使得R中所有面的边界都是M-交错圈,则称R是G的一个交错集.进而,若交错集R中的面互不相交,则称R是G的一个共振集.G的最大共振集的大小称为G的共振数,记作res(G).显然,Pachter等人的结果蕴含着F(G)≥res(G).六角系统H是2-连通的有限平面图,它的每个内面都以正六边形为边界.H的最大共振集称为Clar集,其大小称为Clar数,记作Cl(H).郑茂林等人证明了H去掉任意Clar集后所剩图有唯一完美匹配;Salem等人证明了H去掉任意极大交错集后所剩图也有唯一完美匹配.结合Pachter和郑茂林等人的结果,徐丽琼等人证明了:H有达到强迫数最大值的完美匹配M,使得H中互不相交的M-交错面圈(即,M-交错六角形)的最大数目等于M的强迫数;从而证明了Cl(H)=F(H),并且猜想方格子图的最大强迫数能在多项式时间内计算出来.其中方格子图是无限平面方格网上的有限连通子图,它的每个内面都是方格并且每条边被包含在至少一个方格上.六角系统H的最大交错集的大小称为Fries数,记作Fries(H).显然,Af(H)≥F ries(H).雷洪川等人通过证明H有达到最大反强迫数的完美匹配M使得H中M-交错六角形的数目等于M的反强迫数,证明了F ries(H)=Af(H).受上述工作的启发,我们进一步研究六角系统和方格子图中完美匹配的强迫数、反强迫数与交错面圈个数之间的关系.本论文共分为五章.第一章首先给出一些文中用到的概念、术语和记号,而后从物理化学角度介绍共振集和匹配强迫数的提出背景并综述相关的研究进展,最后概述我们所取得的主要结果.第二章我们研究了方格子图的最大共振集和极大交错集的性质,给出并证明共振数与最大强迫数之间的关系.具体地,我们证明了:方格子图去掉任意最大共振集后所剩图有唯一完美匹配;方格子图去掉任意极大交错集后所剩图也有唯一完美匹配;方格子图的共振数等于其最大强迫数,进而证实了徐丽琼等人提出的猜想.第三章我们研究了六角系统H的最大强迫数和交错六角形个数之间的关系.通过改进郑茂林等人的方法,我们证明了:对于H中每个达到强迫数最大值的完美匹配M(即f(H,M)=F(H)),H中两两不交的M-交错六角形的最大数目等于M的强迫数;由Cl(H)=F(H)知,H有一个由M-交错六角形构成的Clar集;进而,对于H中任意F(H)个两两不交的M-交错圈,它们的内部彼此不相交,且每个圈在H中围成一个线性六角链.第四章我们研究了方格子图H中匹配强迫数和交错方格子个数之间的关系.证明了:对于H中每个达到强迫数最大值或次大值的完美匹配M(即f(H,M)=F(H)或f(H,M)=F(H)-1),H中两两不交的M-交错方格子的最大数目等于M的强迫数;当f(H,M)=F(H)时,H中任意f(H,M)个两两不交的M-交错圈彼此有不相交的内部,且每个圈在H中围成一个锯齿形链.第五章我们研究了六角系统H中匹配反强迫数和交错六角形个数之间的关系.证明了:对于H中每个达到反强迫数最大值或次大值的完美匹配M(即af(H,M)=Af(H)或af(H,M)=Af(H)-1),H中M-交错六角形的数目等于M的反强迫数,H中任意af(H,M)个非交叉的相容M-交错圈彼此有不相交的内部,且每个圈在H中围成一个线性六角链.本章最后,我们研究了不含三亚苯作为好子图的六角系统H,证明了:H中每个完美匹配M′的反强迫数都等于M′-交错六角形数目的充要条件是H不含三亚苯作为好子图.
[Abstract]:璁綠鏄�涓�涓�鍥�.G鐨勫畬缇庡尮閰嶆槸鎸囪�嗙洊G涓�鎵�鏈夐《鐐圭殑涓や袱涓嶄氦杈圭殑闆嗗悎.璁綧鏄疓鐨勪竴涓�瀹岀編鍖归叄�

本文编号：1433043