圖的染色ppt課件

1、圖著色，周思波，四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院，1。給定(p，Q)圖的邊著色，考慮用K色著色G的Q邊。也就是說，G的邊集E(G)被分成k個子集Ei，Ei被稱為第I顏色組，并且這些邊被認(rèn)為是用第I顏色染色的。實(shí)際上，從G的邊集E(G)到色集s=1，2，K建立了一個映射。如果G的任意兩個相鄰邊ei和ej都有(Ei) (ej)，換句話說，對于每一個I，Ei都是圖G的邊獨(dú)立集，那么它被稱為圖G的正規(guī)K邊染色。如果圖G具有正規(guī)K邊染色，那么G被稱為是可染的。例如，如果G是可染的，那么G就是可染的。使圖g具有正常邊著色的最小色數(shù)稱為g的邊色數(shù)，表示為(g)。(G) (G)，3，引理6.1如果連通圖G不是奇

2、數(shù)長度的環(huán)，那么G有一個2邊著色，并且它的兩種顏色出現(xiàn)在每個頂點(diǎn)上，且度數(shù)至少為2。首先，假設(shè)連通圖G是歐拉圖。如果G的所有頂點(diǎn)都是2度，那么G就是一個環(huán)。因此，G是一個偶數(shù)長度的環(huán)，這個定理顯然成立。如果G的頂點(diǎn)度數(shù)不全是2，那么一定有一個頂點(diǎn)的度數(shù)至少是4。設(shè)e1e2方程為g的歐拉回路，設(shè)E1=ei|i為奇數(shù)，E2=ei|i為偶數(shù)。因?yàn)镚的每個頂點(diǎn)都是旅行的內(nèi)頂點(diǎn)，所以G的雙邊著色(E1，E2)具有必要的性質(zhì)。其次，假設(shè)G不是一個歐拉圖，增加一個新點(diǎn)W，并把它與G的每個奇點(diǎn)連接起來。這樣構(gòu)造的圖G*顯然是一個歐拉圖。We1e2eqw是G*的歐拉圖，Euler，E2如上定義。然后(E1E，E

3、2E)具有所需的屬性。4，最佳K邊著色。給定圖G的一個K邊著色，我們用C(v)表示在著色下出現(xiàn)在點(diǎn)V的不同顏色的數(shù)目。顯然，存在C(v) dG(v)，并且當(dāng)且僅當(dāng)它是正常的K邊著色時，所有頂點(diǎn)的等號成立。讓圖G有兩個K邊著色和。如果有，就說K邊著色優(yōu)于，如果沒有K邊著色優(yōu)于，就說它是最好的K邊著色。5，引理6.2是圖G的最佳k-邊染色。如果G中有一個頂點(diǎn)U和兩個顏色I(xiàn)和J，我不會出現(xiàn)在U中，但J至少會出現(xiàn)在U中兩次。假設(shè)Ei和Ej是G中用I和J著色的邊的集合，那么Ei和Ej中包含U的分支B是一個奇數(shù)長度的環(huán)。6，定理6.3對于任何簡單的圖G，都有(G) (G) (G) 1，所以它是一個最優(yōu)的(G) 1)邊著色，并且必須有一個頂點(diǎn)U適合于C(u) dG(u)和dG(u) (G) 1 Let (u，v)=i1，(U，v1)=i1，因?yàn)镈G(v1)=G(1)，顏色i2不出現(xiàn)在v1中，但是i2必須出現(xiàn)。否則，我們可以改變(u，v2)為顏色i2，并得到一個新的(G) 1邊染色比。這與權(quán)利的假設(shè)相矛盾。讓(u，v2)=i2。出于與上述相同的原因，有一種顏色i3不會出現(xiàn)在v2中，但會出現(xiàn)在u中。否則，(u，v1)可以用i2染色，而(u，v2)可以用i3染色，因此另一種(G)單面染色更好，這導(dǎo)致了矛盾。繼續(xù)這個過程，頂點(diǎn)序列v1，v2和顏色序列i1，i2，vi都與U相鄰，因此vt與U