發(fā)布時間：2018-01-16 12:09

  本文關(guān)鍵詞：平面圖的強(qiáng)迫集、反強(qiáng)迫集與交錯集之間的關(guān)系　出處：《蘭州大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 六角系統(tǒng) 方格子圖 完美匹配 Clar數(shù) Fries數(shù) 強(qiáng)迫數(shù) 反強(qiáng)迫數(shù) 共振集 交錯集 交錯圈 非交叉的相容交錯集 好子圖 三亞苯

【摘要】：設(shè)G是一個圖.G的完美匹配是指覆蓋G中所有頂點(diǎn)的兩兩不交邊的集合.設(shè)M是G的一個完美匹配,S?E(G).若S?M且S不被包含于G的其它完美匹配,則稱S是M的強(qiáng)迫集;若S?E(G)\M且G-S有唯一的完美匹配M,則稱S是M的反強(qiáng)迫集.M的最小強(qiáng)迫集和最小反強(qiáng)迫集的大小分別稱為M的強(qiáng)迫數(shù)和反強(qiáng)迫數(shù),記作f(G,M)和af(G,M).G中所有完美匹配的強(qiáng)迫數(shù)的最大值和反強(qiáng)迫數(shù)的最大值分別稱為G的最大強(qiáng)迫數(shù)和最大反強(qiáng)迫數(shù),記作F(G)和Af(G).邊交替出現(xiàn)在M和E(G)\M中的圈稱為M-交錯圈.兩個M-交錯圈稱為相容的,如果它們要么不相交要么僅相交于M中的邊處.對于平面二部圖G,Pachter等人證明了f(G,M)等于G中互不相交的M-交錯圈的最大個數(shù),雷洪川等人證明了af(G,M)等于G中相容的M-交錯圈的最大個數(shù).設(shè)R是平面圖G中若干內(nèi)面的集合.若G有一個完美匹配M使得R中所有面的邊界都是M-交錯圈,則稱R是G的一個交錯集.進(jìn)而,若交錯集R中的面互不相交,則稱R是G的一個共振集.G的最大共振集的大小稱為G的共振數(shù),記作res(G).顯然,Pachter等人的結(jié)果蘊(yùn)含著F(G)≥res(G).六角系統(tǒng)H是2-連通的有限平面圖,它的每個內(nèi)面都以正六邊形為邊界.H的最大共振集稱為Clar集,其大小稱為Clar數(shù),記作Cl(H).鄭茂林等人證明了H去掉任意Clar集后所剩圖有唯一完美匹配;Salem等人證明了H去掉任意極大交錯集后所剩圖也有唯一完美匹配.結(jié)合Pachter和鄭茂林等人的結(jié)果,徐麗瓊等人證明了:H有達(dá)到強(qiáng)迫數(shù)最大值的完美匹配M,使得H中互不相交的M-交錯面圈(即,M-交錯六角形)的最大數(shù)目等于M的強(qiáng)迫數(shù);從而證明了Cl(H)=F(H),并且猜想方格子圖的最大強(qiáng)迫數(shù)能在多項式時間內(nèi)計算出來.其中方格子圖是無限平面方格網(wǎng)上的有限連通子圖,它的每個內(nèi)面都是方格并且每條邊被包含在至少一個方格上.六角系統(tǒng)H的最大交錯集的大小稱為Fries數(shù),記作Fries(H).顯然,Af(H)≥F ries(H).雷洪川等人通過證明H有達(dá)到最大反強(qiáng)迫數(shù)的完美匹配M使得H中M-交錯六角形的數(shù)目等于M的反強(qiáng)迫數(shù),證明了F ries(H)=Af(H).受上述工作的啟發(fā),我們進(jìn)一步研究六角系統(tǒng)和方格子圖中完美匹配的強(qiáng)迫數(shù)、反強(qiáng)迫數(shù)與交錯面圈個數(shù)之間的關(guān)系.本論文共分為五章.第一章首先給出一些文中用到的概念、術(shù)語和記號,而后從物理化學(xué)角度介紹共振集和匹配強(qiáng)迫數(shù)的提出背景并綜述相關(guān)的研究進(jìn)展,最后概述我們所取得的主要結(jié)果.第二章我們研究了方格子圖的最大共振集和極大交錯集的性質(zhì),給出并證明共振數(shù)與最大強(qiáng)迫數(shù)之間的關(guān)系.具體地,我們證明了:方格子圖去掉任意最大共振集后所剩圖有唯一完美匹配;方格子圖去掉任意極大交錯集后所剩圖也有唯一完美匹配;方格子圖的共振數(shù)等于其最大強(qiáng)迫數(shù),進(jìn)而證實(shí)了徐麗瓊等人提出的猜想.第三章我們研究了六角系統(tǒng)H的最大強(qiáng)迫數(shù)和交錯六角形個數(shù)之間的關(guān)系.通過改進(jìn)鄭茂林等人的方法,我們證明了:對于H中每個達(dá)到強(qiáng)迫數(shù)最大值的完美匹配M(即f(H,M)=F(H)),H中兩兩不交的M-交錯六角形的最大數(shù)目等于M的強(qiáng)迫數(shù);由Cl(H)=F(H)知,H有一個由M-交錯六角形構(gòu)成的Clar集;進(jìn)而,對于H中任意F(H)個兩兩不交的M-交錯圈,它們的內(nèi)部彼此不相交,且每個圈在H中圍成一個線性六角鏈.第四章我們研究了方格子圖H中匹配強(qiáng)迫數(shù)和交錯方格子個數(shù)之間的關(guān)系.證明了:對于H中每個達(dá)到強(qiáng)迫數(shù)最大值或次大值的完美匹配M(即f(H,M)=F(H)或f(H,M)=F(H)-1),H中兩兩不交的M-交錯方格子的最大數(shù)目等于M的強(qiáng)迫數(shù);當(dāng)f(H,M)=F(H)時,H中任意f(H,M)個兩兩不交的M-交錯圈彼此有不相交的內(nèi)部,且每個圈在H中圍成一個鋸齒形鏈.第五章我們研究了六角系統(tǒng)H中匹配反強(qiáng)迫數(shù)和交錯六角形個數(shù)之間的關(guān)系.證明了:對于H中每個達(dá)到反強(qiáng)迫數(shù)最大值或次大值的完美匹配M(即af(H,M)=Af(H)或af(H,M)=Af(H)-1),H中M-交錯六角形的數(shù)目等于M的反強(qiáng)迫數(shù),H中任意af(H,M)個非交叉的相容M-交錯圈彼此有不相交的內(nèi)部,且每個圈在H中圍成一個線性六角鏈.本章最后,我們研究了不含三亞苯作為好子圖的六角系統(tǒng)H,證明了:H中每個完美匹配M′的反強(qiáng)迫數(shù)都等于M′-交錯六角形數(shù)目的充要條件是H不含三亞苯作為好子圖.
[Abstract]:璁綠鏄竴涓浘.G鐨勫畬緹庡尮閰嶆槸鎸囪鐩朑涓墍鏈夐《鐐圭殑涓や袱涓嶄氦杈圭殑闆嗗悎.璁綧鏄疓鐨勪竴涓畬緹庡尮閰，

本文編號：1433043