圖的匹配強迫與匹配阻礙問題研究

項目摘要

本項目主要研究圖的匹配強迫和匹配阻礙問題，包括圖的完美匹配的強迫數及其分布，全局強迫數和完全強迫數，反強迫數和匹配阻礙等。具體地討論圖的完美匹配的強迫數與獨立交錯圈、獨立交錯面的最大個數之間的關係;研究圖的匹配強迫數分布和強迫譜這個整數集的連續和間斷情況, 計算若干圖的匹配強迫多項式，特別是得到超立方圖的最小強迫數以證實Pachter 和Kim的猜想，利用圖的共振圈的變換方法發現六角系統和Fullerene等圖中具有連續強迫譜的類型；討論全局強迫數和完全強迫數、反強迫數和各種匹配阻礙數（包括反Kekulé數）的計算方法和計算複雜性. 圖的匹配強迫和匹配阻礙問題來源於理論化學和計算機網路, 是匹配理論發展的新方向，一些挑戰性問題相繼被提出，許多基本問題亟待解決. 通過本項目的研究提出有價值的研究方法，解決若干重要問題,為這個匹配理論的新型領域的研究奠定基礎, 推動匹配理論的進一步發展.

結題摘要

本項目主要研究圖匹配強迫和匹配阻礙問題, 其來源於理論化學和計算機網路, 包括平面二部圖的完美匹配的強迫與反強迫和交錯面集的極大極小關係, 匹配強迫數與反強迫數及其分布, 完全強迫數和匹配阻礙等, 是圖的匹配理論發展的新方向. 在強迫數與共軛圈的關係上, 表明了對六角系統與方格子圖達到最大強迫數的每個完美匹配都有最多的獨立交錯面的個數,（4,6）-fullerene圖的最大強迫數等於共振數(或Clar 數); 在匹配強迫數的分布上，藉助Z-變換圖（或共振圖）的連通性表明有強迫邊的六角系統的強迫譜是連續的（最多2是間隔）, 偶階路與奇長圈的卡氏積圖（柱面格子圖）的強迫譜是連續的, 廣義彼得森圖P(n,2)的強迫譜是兩個整區間的並. 對zigzag六角鏈、冠狀六角環、cata型和和平行四邊形六角系統計算出了它們的強迫多項式, 得到平均強迫數的一些漸進結果. 利用構造方法刻畫出了最小強迫數是3的所有富勒烯圖，解決了一公開問題；提出並研究了圖的完全強迫數，刻畫出了其完全強迫集，給出cata型苯系統的完全強迫數的線性算法，表明其完全強迫數等於Clar數加上六邊形的個數，給出了渺位冠狀系統的完全強迫數的精確表達式；在反強迫上，提出了圖的單個完美匹配的反強迫數，極大擴展了D. Vukicvic 與N. Trinajstic 的起初概念，建立了與強迫數的關係，揭示出了與強迫數類似的極大極小結果，證明了六角系統與(4,6)-fullerene圖的最大反強迫數都等於各自的Fries數. 給出了圖的最大反強迫數的兩個可達上界並刻畫出了極值圖. 證明了Cata型與單調可構造型六角系統的反強迫譜是連續的. 在匹配阻礙上，研究了偶階點傳遞圖與正則圖的極大匹配與超匹配性，統一得到了一系列已知結果. 將圖的匹配排除數表示成線性整數規劃，利用完美匹配多面體理論研究分數匹配排除數, 證明了一般圖分數匹配排除數有多項式時間算法. 對於二部圖，給出了其顯式表達式，並與k-因子建立了聯繫. 表明了一般正則圖與極大匹配正則圖的笛卡爾乘積圖、直積圖與強乘積圖都是超匹配的.

圖的匹配強迫與匹配阻礙問題研究

基本介紹

項目摘要

結題摘要

熱門詞條