設(shè)圖G是一個有限的簡單連通圖,E（G）和V（G）分別是G的邊集和頂點集.獨立邊集M是G的一個完美匹配當(dāng)且僅當(dāng)V（G）中的點都是M-飽和的.M的反強(qiáng)迫數(shù)是指在圖G中刪去不在M中的邊而使得剩余圖有唯一完美匹配的邊的最少數(shù)目.G的反強(qiáng)迫譜是指其所有完美匹配的反強(qiáng)迫數(shù)的集合.對應(yīng)的,反強(qiáng)迫譜中最大和最小的整數(shù)被稱為最大反強(qiáng)迫數(shù)和最小反強(qiáng)迫數(shù)（簡稱反強(qiáng)迫數(shù)）,分別記為F（G）和f（G）.梯子圖Ln是路Pn和P2的笛卡爾積.第一章中我們簡單介紹了有關(guān)格子圖的相關(guān)研究背景和成果,給出了本文的一些基礎(chǔ)概念和重要引理.第二章中我們給出了一個分解定理,將Ln分成兩個片段,Ln的一個完美匹配的反強(qiáng)迫數(shù)是各個片段對應(yīng)完美匹配的反強(qiáng)迫數(shù)之和.應(yīng)用分解定理,我們得出了Ln的反強(qiáng)迫譜及其譜的連續(xù)性.通過反強(qiáng)迫數(shù)或水平匹配邊數(shù)對Ln的所有完美匹配分類計數(shù),得到了關(guān)于斐波那契數(shù)列的兩個組合解釋.第三章中首先通過將梯子圖Ln變形得到了刪邊梯子圖ILn-i和“L”型梯子圖LLn-i,分類計算得到了刪邊梯子圖的反強(qiáng)迫譜,進(jìn)而得到了“L”型梯子圖的反強(qiáng)迫數(shù).過程中得到了斐波那契數(shù)列的一個組合解釋.第四章中利用之前得到的結(jié)論,分... 

【文章來源】：西北師范大學(xué)甘肅省

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

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

【部分圖文】：

圖２．１梯子圖??

圖２．３?Ｌ９的一個堯美匹配及其對應(yīng)分解??

圖３．１刪邊梯于ｆｔｆＬｆ??

【參考文獻(xiàn)】：
期刊論文
[1]梯子圖完美匹配的反強(qiáng)迫譜與斐波那契數(shù)列[J]. 韓振云,王杰彬.  蘭州工業(yè)學(xué)院學(xué)報. 2020(01)
[2]循環(huán)梯狀圖的完美匹配的反強(qiáng)迫譜與盧卡斯數(shù)列[J]. 姚海元,王杰彬,王旭.  西北師范大學(xué)學(xué)報(自然科學(xué)版). 2018(02)

博士論文
[1]關(guān)于一些圖類的強(qiáng)迫與反強(qiáng)迫多項式的研究[D]. 趙爽.蘭州大學(xué) 2018
[2]圖的匹配強(qiáng)迫譜與匹配反強(qiáng)迫譜研究[D]. 鄧凱.蘭州大學(xué) 2016

碩士論文
[1]幾類特殊圖的反強(qiáng)迫譜的研究[D]. 王杰彬.西北師范大學(xué) 2018
[2]廣義Sierpi（?）ski圖的第一類Zagreb指標(biāo)與四角鏈的反強(qiáng)迫數(shù)[D]. 梁志鵬.新疆大學(xué) 2016



本文編號：3513847