連通度,H-局部連通與[s,l]-圖的路圈性質.pdf

1、圖論作為現(xiàn)代數(shù)學的一個重要分支，在電氣網絡，信息傳輸，城市規(guī)劃等方面的應用越來越廣泛，因為自然界和人類社會中有大量事物以及事物之間的關系，可以用圖來描述．而路和圈作為圖的兩種基本結構，是分析和刻畫圖的有力工具，有許多的實際問題可以歸結為圖的路和圈問題，所以這方面一直是圖論中的熱點研究領域，其研究成果和進展可參見文獻[1]-[4]．事實上，圖論中三大著名難題之一的Hamilton問題本質上也是圖的路和圈問題．經過幾十年的發(fā)展，圖的路圈性質

2、所涉及的內容日益豐富和具體．路的方面包括圖的Hamilton-路(可跡性)，最長路，Hamilton連通，泛連通，路可擴等等；圈的方面包括圖的Hamilton圈，最長圈，(點)泛圈，完全國可擴，點不交的圈，圈覆蓋等等．
　　由于Hamilton問題是一個NPC問題，直接研究往往比較困難，于是人們轉而研究不含有某些禁用子圖的圖類．繼Beinekel968，1970年發(fā)表的關于線圖性質的兩篇文章[5]-[6]之后，人們開始關注包含著線

3、圖的無爪圖．70年代末80年代初，是研究無爪圖的一個非?；钴S的時期．關于無爪圖方面的部分優(yōu)秀成果可參考[7]-[32]．另外，無爪圖的概念也被從不同角度推廣到了更大的圖類，如半無爪圖，幾乎無爪圖，(K1，4；2)-圖，DCT圖等．這方面的研究成果可參考[33]-[46]．2005年，劉春房在[47]中定義了一種新的圖類-[s，t]-圖，即任意s個點之間至少含有t條邊，這類圖的特點是其邊的分布比較均勻，因而在交通網絡，通信系統(tǒng)，計算機的網

4、絡配置等方面有著典型應用．目前，關于[s，t]-圖路圈性質的研究也取得了不少成果，可參考文獻[47]-[50]．
　　連通和局部連通是研究圖的路圈性質的常用條件，在局部連通的概念提出之后，張存全在1989年提出了半局部連通的定義，并研究了無爪圖在半局部連通條件下的一些性質．而后人們又相繼提出了許多不同的相關定義，如：幾乎局部連通，三角連通，2-階鄰域連通等．2008年劉明穎[51]提出了H-局部連通的概念，并初步討論了K2-局部連