圖G的完美匹配M的強迫數(shù)由Klein和Randic與Harary等分別在化學(xué)與數(shù)學(xué)中先后引入,具體定義為M中邊的最少條數(shù),使得這些邊的集合不包含在G的其它完美匹配里.而M的反強迫數(shù)是指不在M中邊的最少條數(shù),使得從G中刪除這些邊之后得到的子圖有唯一的完美匹配M.一般地,二部圖的完美匹配的強迫數(shù)與反強迫數(shù)的計算問題都是NP-完全的.研究表明,一個六角系統(tǒng)的最大強迫數(shù)等于它的Clar數(shù),而最大反強迫數(shù)等于它的Fries數(shù),且Clar數(shù)與Fries數(shù)都可以用來衡量芳香烴的分子穩(wěn)定性.在一般圖中,每個完美匹配的強迫數(shù)不小于最多不交交錯圈的個數(shù),Guenin和Thomas表明對不含K3,3或希伍德圖的偶剖分作為好子圖的二部圖前面兩者有相等關(guān)系;每個完美匹配的反強迫數(shù)不小于最大相容交錯集的大小,并且對不含K3,3的剖分的二部圖前面兩者有相等關(guān)系.近幾年,關(guān)于圖的最大最小強迫數(shù)與反強迫數(shù),以及強迫譜與反強迫譜的研究有了一些較深入的討論.然而,計算一個圖中有多少個完美匹配具有相同的強迫數(shù)與反強迫數(shù)是匹配強迫問題的一個新領(lǐng)域.在此基礎(chǔ)上,本文提出了圖的強迫多項式,即將具有相同強迫數(shù)的完美匹配個數(shù)作為系數(shù)的... 

【文章頁數(shù)】：125 頁

【學(xué)位級別】：博士

【文章目錄】：
中文摘要
Abstract
第一章 引言
    1.1 圖的基本概念,記號與基本引理
    1.2 六角系統(tǒng)與方格子圖的性質(zhì)
    1.3 匹配強迫問題的研究背景及進(jìn)展
    1.4 匹配反強迫問題的研究背景及進(jìn)展
    1.5 本文的主要結(jié)果
第二章 cata-型六角系統(tǒng)的強迫多項式
    2.1 圖的強迫多項式的定義及重要引理
    2.2 六角鏈
    2.3 zigzag六角鏈
    2.4 cata-型六角系統(tǒng)
第三章 平行四邊形六角系統(tǒng)的強迫多項式
    3.1 平行四邊形六角系統(tǒng)
    3.2 與平行四邊形六角系統(tǒng)相關(guān)的六角系統(tǒng)
第四章 具有強迫邊的六角系統(tǒng)的反強迫多項式
    4.1 圖的反強迫多項式的定義及重要引理
    4.2 具有反強迫邊的六角系統(tǒng)
    4.3 平行四邊形六角系統(tǒng)
    4.4 具有強迫邊的六角系統(tǒng)
第五章 一些格子圖的強迫及反強迫多項式
    5.1 2×n格子圖的強迫多項式
    5.2 2×n格子圖的反強迫多項式
    5.3 3×2n格子圖的強迫多項式
    5.4 3×2n格子圖的反強迫多項式
第六章 一類廣義彼得森圖的強迫譜
    6.1 兩類完美匹配
    6.2 第一類完美匹配的強迫數(shù)
        6.2.1 強迫數(shù)的最大值
        6.2.2 強迫數(shù)的最小值
        6.2.3 連續(xù)性
    6.3 第二類完美匹配的強迫數(shù)
        6.3.1 強迫數(shù)的最大值
        6.3.2 強迫數(shù)的最小值
        6.3.3 連續(xù)性
參考文獻(xiàn)
在學(xué)期間的研究成果
致謝


【參考文獻(xiàn)】：
期刊論文
[1]石墨烯的生物安全性研究進(jìn)展[J]. 田甜,呂敏,田旸,孫艷紅,李曉霞,樊春海,黃慶.  科學(xué)通報. 2014(20)
[2]FORCING BONDS OF A BENZENOID SYSTEM[J]. 張�；顚W(xué)良.  Acta Mathematicae Applicatae Sinica（English Series）. 1996(02)
[3]A THEOREM CONCERNING PERFECT MATCHINGS IN HEXAGONAL SYSTEMS[J]. 張�；�,陳榮斯.  Acta Mathematicae Applicatae Sinica（English Series）. 1989(01)
[4]THE CONNECTIVITY OF Z-TRANSFORMATION GRAPHS OF PERFECT MATCHINGS OF HEXAGONAL SYSTEMS[J]. 張�；�,郭曉峰,陳容思.  Acta Mathematicae Applicatae Sinica（English Series）. 1988(02)



本文編號：3733481