邊染色圖中的匹配、圈及圖的圓染色.pdf

1、圖論的研究始于200多年前．關(guān)于圖論的第一篇論文是1736年Euler發(fā)表的，他用圖的方法解決了哥尼斯堡(Konigsberg)七橋問(wèn)題．二十世紀(jì)六十年代以來(lái)，圖論在科學(xué)界異軍突起，活躍非凡．圖論中有很多著名的問(wèn)題，如哈密爾頓問(wèn)題，四色問(wèn)題，中國(guó)郵遞員問(wèn)題等．并且，應(yīng)用圖論來(lái)解決化學(xué)，生物學(xué)，信息和計(jì)算機(jī)科學(xué)等學(xué)科問(wèn)題已顯示出極大的優(yōu)越性．同時(shí)，圖論在工程技術(shù)領(lǐng)域及社會(huì)科學(xué)中也有著廣泛的應(yīng)用．它作為離散數(shù)學(xué)的一個(gè)重要分支，受到了各方面的

2、普遍重視． 我們用G表示一個(gè)圖，若G的每條邊都染上顏色，則稱G為邊染色圖．給定一個(gè)邊染色圖G，關(guān)聯(lián)于頂點(diǎn)u的不同顏色的邊的數(shù)目，稱為頂點(diǎn)u的色度，記為d<'c>(u)．如果把一般的未染色圖看作是每條邊都染不同顏色的邊染色圖，則頂點(diǎn)的色度就等于它的度．除了在圖論和算法上的重要應(yīng)用外，邊染色中的許多問(wèn)題還出現(xiàn)在分子生物科學(xué)，心理學(xué)和網(wǎng)絡(luò)通信等其它的領(lǐng)域中．因此，近年來(lái)，這方面的研究變得活躍起來(lái)，主要集中在邊染色圖中某些特殊子圖的存在

3、性上．邊染色圖中的子圖，如果任意相鄰的兩條邊的顏色都不相同，我們稱之為交錯(cuò)子圖，或者稱為邊正常染色子圖．進(jìn)一步，如果該子圖中所有邊的顏色都不相同，我們稱之為彩色子圖．這兩類子圖的研究尤其受到關(guān)注．圖的匹配，路和圈是圖論中的基礎(chǔ)研究領(lǐng)域，因此邊染色圖中的彩色的(交錯(cuò)的)匹配，路和圈就成了一個(gè)重要的研究方向． 圖中過(guò)每個(gè)頂點(diǎn)的圈，稱為圖的哈密爾頓圈．圖的哈密爾頓圈問(wèn)題，是圖論中的一個(gè)經(jīng)典問(wèn)題．其中一個(gè)著名的猜想是Chvátal[20

4、]提出的如下猜想：韌度充分大的圖有一個(gè)哈密爾頓圈．對(duì)于許多特殊的圖類，例如弦圖和平面圖，上述猜想被證明是成立的[11，12，23]．圖G的一條K-途徑是指G的一條經(jīng)過(guò)每個(gè)頂點(diǎn)至多七次的閉支撐途徑．圖的一個(gè)哈密爾頓圈就是圖的1-途徑．作為哈密爾頓圈的一個(gè)非常有趣的變形，圖的K-途徑引起了很多人的興趣．Jackson和Wlormald[54]研究了K-途徑，并猜想任意l-堅(jiān)韌圖都有一條2-途徑．這個(gè)猜想仍然沒有得到證明，最好的結(jié)果是任意4-

5、堅(jiān)韌圖都有一條2-途徑[37]．自然地，我們會(huì)考慮如下問(wèn)題：確定最小的整數(shù)k：k(△)使得對(duì)最大度為△的任意圖都有一條k-途徑．對(duì)于一般圖，這個(gè)問(wèn)題是平凡的，因?yàn)樽畲蠖葹椤鞯娜我鈽涠加小?途徑[54]，但對(duì)于k<△，不含任何七一途徑．但如果我們考慮無(wú)橋圖(2-邊連通圖)，情況就不一樣了．我們?cè)诘谖逭轮?，討論了這個(gè)問(wèn)題．另一方面，圖的染色理論在圖論中占有很重要的地位．近年來(lái)，圖的圓染色的研究變的異?；钴S，得到了一系列漂亮的結(jié)果，也產(chǎn)生了許

6、多新穎的研究方法，逐漸成為圖的染色理論中的一個(gè)重要分支．圖的選擇數(shù)(列表色數(shù))是圖的一個(gè)很重要的參數(shù)，其中一個(gè)著名的定理是Thomassen[81]的關(guān)于平面圖的5-可選擇性的證明．最近，Zhu[89]和Mohar[69]給出了圓選擇數(shù)的概念，因此，對(duì)平面圖的圓選擇數(shù)的研究也就成了一個(gè)非常有意義的研究方向．另外， Bokal等[69]考慮了有向圖的圓染色，把色數(shù)和圓色數(shù)的概念推廣到有向圖．因此，許多關(guān)于無(wú)向圖中的染色和圓染色方面的問(wèn)題，

7、我們都可以在有向圖中考慮． 本文研究了圖論中的幾個(gè)問(wèn)題，具體地，我們研究了邊染色圖中的匹配和圈，圖的K-途徑和圖的圓染色．全文共分為七章．第一章，我們給出了一個(gè)簡(jiǎn)短但相對(duì)完整的綜述．首先，我們給出了一些基本的定義和術(shù)語(yǔ)，并且對(duì)上述三個(gè)方向的研究進(jìn)展分別做了介紹．最后，我們列出了本文的主要結(jié)果． 在第二章，我們考慮了邊染色圖中的彩色匹配問(wèn)題．邊染色圖中的一個(gè)彩色匹配是指任意兩條邊的顏色都不相同的一個(gè)匹配．在一般的未染色圖中

8、，最大匹配問(wèn)題(找一個(gè)邊數(shù)最多的匹配)是多項(xiàng)式可解的([61])．而在邊染色圖中，即使是在邊染色二部圖中，最大彩色匹配問(wèn)題(找一個(gè)邊數(shù)最多的彩色匹配)是NP-完全的([45])．因此，彩色匹配的研究主要集中在邊染色完全圖和邊染色完全二部圖中．Erds和Pósa．[30]研究了極值圖論中的一個(gè)很基本的問(wèn)題，他們證明了任意一個(gè)頂點(diǎn)個(gè)數(shù)至少為2K，最小度至少為k的圖，都有一個(gè)k條邊的匹配．我們?cè)谶吶旧珗D中研究了類似的問(wèn)題．我們證明了若

9、G是一個(gè)邊染色圖，并且對(duì)任意點(diǎn)u都有d〈’C〉(U)≥K≥4，則G含有一個(gè)有條邊的彩色匹配．我們還證明了若G是一個(gè)邊染色二部圖，并且對(duì)任意頂點(diǎn)U，都有d〈’C〉(U)≥K≥3，則G有一個(gè)條邊的彩色匹配．并且，我們給出了色鄰域的概念，研究了邊染色二部圖中，滿足某種色鄰域條件的彩色匹配問(wèn)題． 在第三章，我們研究了邊染色圖中的彩色圈．首先，我們給出了邊染色圖存在彩色圈的色度條件．并且，我們運(yùn)用關(guān)于Caccetta-Hggkvi

10、st猜想(有向圖中有向三角形存在性)的一個(gè)結(jié)果，得到了邊染色圖存在彩色三角形或者彩色四邊形的色度條件．同時(shí)，我們還研究了邊染色圖中的長(zhǎng)彩色圈. 在第四章，我們討論了邊染色圖中色度和交錯(cuò)圈的關(guān)系，得到了邊染色圖中幾類特殊交錯(cuò)圈存在的色度條件．同時(shí)，我們還對(duì)Bollobás-Erdos猜想(邊染色完全圖中的交錯(cuò)哈密爾頓圈的存在性)做了研究，給出了滿足Bollobás-Erdos條件的邊染色完全圖中，最長(zhǎng)交錯(cuò)圈的圈長(zhǎng)的一個(gè)下界． 在第

11、五章，我們研究了圖的κ-途徑，證明了最大度為△的任意無(wú)橋圖(2-邊連通圖)都有一條「(△+1)/2]．途徑，并且證明了這個(gè)界是最好可能的. 在第六章，我們考慮Mohar[69]提出的關(guān)于平面圖的圓選擇數(shù)的一個(gè)問(wèn)題，研究了具有大圍長(zhǎng)的平面圖的圓選擇數(shù)．我們證明了圍長(zhǎng)至少為(10n+8)/3的平面圖的圓選擇數(shù)至多為2+2/n，從而改進(jìn)了[53]中的結(jié)果．另外，我們還討論了幾類特殊平面圖(系列平行圖，外平面圖，奇輪)的圓選擇數(shù).