均勻染色的新途徑.pdf

1、圖論〔Graph Theory〕是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線(xiàn)所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線(xiàn)表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。
　　 二十世紀(jì)六十年代以來(lái)，圖論在科學(xué)界突軍異起，活躍非凡。圖論中有很多著名的問(wèn)題，如哈密頓問(wèn)題，四色問(wèn)題，中國(guó)郵遞員問(wèn)題等。并且，應(yīng)用圖論來(lái)解決化學(xué)，計(jì)算機(jī)科學(xué)，生物學(xué)等學(xué)科問(wèn)題已顯出極大的優(yōu)越性。

2、圖論作為離散數(shù)學(xué)的一個(gè)重要分支，受到了各方面的普遍重視。
　　 均勻染色問(wèn)題作為圖論里的一個(gè)重要問(wèn)題，對(duì)于它的研究有著深遠(yuǎn)的意義。令G表示一個(gè)簡(jiǎn)單圖。圖的均勻染色，就是指正常染色中任意兩個(gè)色類(lèi)中的元素個(gè)數(shù)最多相差一個(gè)。這里主要考慮簡(jiǎn)單的非空有限圖，這些圖不包含環(huán)以及重邊。
　　 本文研究了圖論中有關(guān)均勻染色的若干問(wèn)題，具體地，我們從樹(shù)的均勻染色入手，通過(guò)在樹(shù)上加邊的方式形成各種帶圈的圖，從而將簡(jiǎn)單圖做了系統(tǒng)的歸類(lèi)，然后研

3、究這幾類(lèi)加圈圖的相關(guān)性質(zhì)及其均勻染色數(shù)k的范圍。上述問(wèn)題可以概括如下：任意一個(gè)簡(jiǎn)單圖G，其均勻染色數(shù)為k，為了方便確定k的范圍，我們將G進(jìn)行分類(lèi)，按各類(lèi)別的性質(zhì)去確定其具體k的范圍，達(dá)到更科學(xué)、更精確的目的。
　　 全文共分為五章。
　　 第一章，我們給出了一個(gè)簡(jiǎn)短而又相對(duì)完整的引言。首先，我們介紹了均勻染色的理論知識(shí)。然后，我們給出了一些基本的術(shù)語(yǔ)和定義。最后，我們列出本文的主要結(jié)果。
　　 在第二章里，針對(duì)連

4、通的簡(jiǎn)單圖，我們先從簡(jiǎn)單一些的圖類(lèi)入手，這里是以樹(shù)入手，巧妙借助已經(jīng)存在的若干定理，來(lái)研究這類(lèi)圖的均勻染色數(shù)k。
　　 在第三章里，我們對(duì)剩下的連通含圈簡(jiǎn)單圖進(jìn)行研究，將其分類(lèi)細(xì)化，設(shè)計(jì)相關(guān)算法，尋求其均勻染色數(shù)七的范圍。具體分成以下三大類(lèi)：
　　 第一類(lèi)，圖G里不存在奇圈。在這一類(lèi)情況里，我們將圖G看成二分圖G(X，Y)，然后按照二分圖的性質(zhì)來(lái)研究其均勻染色色數(shù)的范圍。
　　 第二類(lèi)，圖G中不存在偶圈。對(duì)于此類(lèi)

5、情況，我們不難得出其任意兩個(gè)圈都不相交的結(jié)論。這樣便大大簡(jiǎn)化了我們確定均勻染色色數(shù)的難度。而另外關(guān)鍵的一步是將此大類(lèi)按照這樣一個(gè)規(guī)則劃成兩小類(lèi)，即，圖G中是否存在滿(mǎn)足||X|-|Y||≥2條件的子樹(shù)Ti(X，Y)。如果不存在該條件的子樹(shù)，則圖G是3-均勻可染色的。反之，如果圖G中存在滿(mǎn)足條件的子樹(shù)Ti(X，Y)時(shí)，我們便采用二分搜索方法來(lái)鎖定均勻染色色數(shù)的范圍。這里七是介于3和ki之間的數(shù)。在本部分，我們構(gòu)造了相關(guān)例子來(lái)演示該方法。

6、r>　　 第三類(lèi)，圖G中既存在奇圈，又存在偶圈。這里又可以分兩種情況來(lái)討論。分類(lèi)標(biāo)準(zhǔn)是，圖G里的圈是否相交。如果嚴(yán)格不存在相交的情況，便可以運(yùn)用前面提到的第二類(lèi)方法來(lái)解決此類(lèi)問(wèn)題；然而，如果存在相交的情況——這種情況相對(duì)來(lái)說(shuō)比較復(fù)雜，我們便對(duì)其進(jìn)行樹(shù)分解，找到圖G的樹(shù)寬w，即w-退化的，借助樹(shù)寬，可以確定該圖G的均勻染色色數(shù)k的范圍。
　　 在第四章里，主要研究那些非連通簡(jiǎn)單含圈圖的均勻染色數(shù)k。本文先從森林入手，將此類(lèi)圖劃分