均勻染色的新途徑.pdf

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

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

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

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

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

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