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

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

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

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