P-,3--控制圖和（K-,1,4-;2）-圖的圈和路.pdf

1、圈和路是圖的兩種基本結(jié)構(gòu)．是分析和刻畫圖的有力工具．大量的實際問題都可以歸結(jié)為圖的圈和路問題．對圖的圈路性質(zhì)的研究是在圖論中的著名問題-Hamilton問題的基礎(chǔ)上發(fā)展來的．而關(guān)于圖的哈密頓性的研究．已經(jīng)取得了長足的發(fā)展．這方面的研究成果和進(jìn)展可參見文獻(xiàn)[26]-[29]．圖的圈路性質(zhì)一直是圖論中的熱門研究領(lǐng)域．經(jīng)過幾十年的發(fā)展．圈路性質(zhì)所涉及的內(nèi)容日益豐富和具體．圈的方面包括圖的Hamilton圈．最長圈．(點)泛圈．完全圈可擴(kuò)．點不

2、交的圈．圈覆蓋等等：路的方面包括圖的Hamilton路(可跡性)．最長路．Hamilton連通．泛連通．路可擴(kuò)等等．另外．在圖連通性方面．一些學(xué)者不斷提出新的概念．比如N2-局部連通．三角連通．四角連通等．為圖的圈路性質(zhì)的研究提供了新的思路． 由于直接研究一般圖的圈路性質(zhì)往往比較困難．所以若干年來相關(guān)的研究主要集中在一些特殊匿類上．即不含有某些禁用子圖的圖類．其中比較有代表性的是無爪圖．它是以K1.3為禁用子圖的圖類．繼Bcin

3、ckcl968.1970年發(fā)表的關(guān)于線圖性質(zhì)的兩篇文章[30]-[31]之后．人們就開始關(guān)注包這種含著線圖的無爪圖．70年代末80年代初．是研究無爪圖的一個非?；钴S的時期．至今在這方面已取得了相當(dāng)多的研究成果．另外．無爪圖的概念也被從不同角度推廣到了更大的圖類．如爪心獨立圖．半無爪圖．幾乎無爪圖．(K1.p:q)-圖．?dāng)M無爪圖等．近年來．一些新型圖類不斷被提出．P3-控制圖就是其中一種．這種圖類包含半無爪圖是半無爪圖的推廣．2006年．