侴萬禧，黃云峰 (安徽理工大學(xué)土木建筑學(xué)院，安徽 淮南 232001)

李曉毅 (沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，遼寧 沈陽 110034)

22面體平圖的頂點4著色研究

侴萬禧，黃云峰 (安徽理工大學(xué)土木建筑學(xué)院，安徽 淮南 232001)

李曉毅 (沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，遼寧 沈陽 110034)

闡明了對偶圖G(p,q,f)的4著色的基本思路，給出了對偶樹的定義，提出了依據(jù)對偶圖G(p,q,f)的2棵對偶樹TA及TB的分解，實現(xiàn)對偶圖G(p,q,f)的4著色的方法，最后介紹了22面體平圖的頂點4著色的全過程，并分析了對偶樹TA、TB的性質(zhì)。

對偶圖；對偶樹；4著色；連通分支

1 基本思路

定義1[1,2]設(shè)任意平圖的對偶圖為含p個頂，q個邊和f個面的平圖，記為G(p,q,f)，則對偶圖G(p,q,f)的p-2個邊所導(dǎo)出的2個不含圈的可2著色的連通分支TA和TB稱為對偶樹。

對偶樹TA的(p-3)/2或(p-5)/2個邊與G(p,q,f)中f個面相關(guān)聯(lián)，對偶樹TB的(p-1)/2或(p+1)/2個邊與G(p,q,f)中f個面相關(guān)聯(lián)。

借助對偶圖G(p,q,f)的2棵對偶樹TA及TB的分解，可以實現(xiàn)對偶圖G(p,q,f)的4著色，這是因為對偶樹TA的2著色和對偶樹TB的2著色等價于對偶圖G(p,q,f)的4著色。

命題1[3,4]設(shè)平圖的對偶圖為G(p,q,f)，而對偶圖G(p,q,f)的對偶圖為G′(f,q,p)，則對偶圖G(p,q,f)的2棵對偶樹TA和TB與對偶圖為G′(f,q,p)的H路徑p是相互依存的(如圖1)。

圖1 對偶樹TA、TB與對偶圖G′(f,q,p)的H路徑p

由圖1可得，基于命題1的對偶樹的一個算法：依據(jù)H路徑求對偶樹TA及TB。反之，倘若對偶樹TA及TB依據(jù)它們自身的性質(zhì)被確定，則對偶樹TA及TB就自然的將G(p,q,f)的f個面分隔出一條通過f個相鄰面中心的暢通路——H路徑p，H路徑p成為對偶樹TA及TB正確與否的標(biāo)志。

2 對偶圖G(p,q,f)的4著色方法

設(shè)對偶圖G(p,q,f)為p=35,q=55,f=22的平圖，對偶圖G(p,q,f)的對偶圖G′(f,q,p)為f=21,q=55,p=35的平圖，則對偶圖G(p,q,f)的4著色的步驟如下：

1)將含f個頂，q個邊和p個面的對偶圖G′(f,q,p)分解出1條通過f個面中心的H路徑p(如圖2)。

圖2 對偶圖G′(f,q,p)的H路徑p的分解

2)讓G(p,q,f)中的與H路徑未交的p-2=33個邊構(gòu)成2棵對偶樹TA及TB，使得TA由(p-5)/2=15或(p-3)/2=16個邊構(gòu)成，而TB由(p-1)/2=17或(p+1)/2=18個邊構(gòu)成(如圖3)。

圖3 對偶圖G(p,q,f)的4著色

3)用y,g為對偶樹TA著色，用r,b為對偶樹TB著色，使得TA的2著色和TB的2著色等價于G(p,q,f)的4著色，即有：

?(TA)+?(TB)=?(G)

3 對偶樹TA及TB的性質(zhì)

22面體平圖G(p,q,f)所分解出的2棵對偶樹TA及TB具有下列性質(zhì)：

1)對偶樹TA的(p-3)/2=16或(p-5)/2=15個邊與G(p,q,f)的f=22個面相關(guān)聯(lián)，對偶樹TB的(p-1)/2=17或(p+1)/2=18個邊也與G(p,q,f)的f=21個面相關(guān)聯(lián)。

2)對偶圖G(p,q,f)的每個面為對偶樹TA及TB的構(gòu)造貢獻(xiàn)出3個邊。

3)對偶樹TA的邊總是試圖包圍對偶樹TB的邊，而對偶樹TB的邊也總是試圖包圍對偶樹TA的邊。

4)對偶樹TA和對偶樹TB將對偶圖G(p,q,f)的f-1=21個面分隔成一條暢通道，亦即形成一條通過f-1=21個面中心的H路徑p。

5)對偶樹TA和對偶樹TB是G(p,q,f)中的與H路徑p未交的p-2=33個邊構(gòu)成的。

[1]Beineke L W, Wilson R J.Selected Topics in Graph Theory[M]. London: Academic Press，1978.

[2]Bollobas B.Extramal Graph Theory[M]. London:Academic Press，1978.

[3]Douglas B.West Introduction to Graph Theory[M].Beijing: China Machine Press， 2004.

[4]徐俊明.圖論及其應(yīng)用[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2004.

[編輯] 洪云飛

O157.5

A

1673-1409(2009)02-N014-02

2009-03-10

國家自然科學(xué)基金資助項目(10471096)。

侴萬禧(1930-)，男，1956年大學(xué)畢業(yè)，教授，現(xiàn)主要從事巖石力學(xué)及圖論方面研究工作。