關(guān)于圖g的色數(shù)和色色交換

關(guān)于圖g的色數(shù)和色色交換

1840年，數(shù)學家莫奧貝茨提出了一張面積為四英寸的平面地圖，假設(shè)相鄰兩個國家有不同的顏色。這個假設(shè)被稱為灰色假設(shè)。1879年A.B.Kempe曾發(fā)表論文,聲稱證明了四色猜想。11年后,P.J.Heawood指出Kempe證明為錯。許多數(shù)學家企圖證明四色猜想,但都未成功,直至1976年美國K.I.Appel和W.Hakem借助于電子計算機證明了四色猜想為真。本人于1998年從理論上證明了A(Q)類平面圖可4-著色。近數(shù)年內(nèi)作者對平面圖及其著色的研究取得了一些成果。在上述基礎(chǔ)上,本人將從理論上證明任一平面圖可4-著色。1kempe法色交換的可能性令χ(G)為圖G的色數(shù)。設(shè)圖G用a1,a2,…,aχ(G)等χ(G)種顏色著色。在G中,由分別著ai(i=1,2,…,χ(G))色的點與aj(j=1,2,…,χ(G);i≠j)色的點以及它們之間的邊所構(gòu)成的子圖稱為G的aiaj的兩色子圖,記為Gaiaj。Gaiaj可能是連通的,也可能是分離的。若兩色連通子圖Gaiaj中包含點υk,則將它記為Gaiaj(υk)。設(shè)Gaiaj′是Gaiaj的一個連通子圖。Kempe法色交換是在Gaiaj′中各點上的顏色ai、aj對調(diào)。由此可見,任一次Kempe法色交換都限定在一個連通兩色子圖中,且該子圖中必須是所有點的顏色都要對調(diào)。因此,在某些情況時,用Kempe法色交換,由G的一種著色求另一種著色有可能實現(xiàn)不了。例1設(shè)最大平面圖G已用χ(G)種顏色著色,如圖1所示。χ(G)=4,將圖G的著色分為A和B兩種,當G為無結(jié)圖時,G為A種著色。否則,G為B種著色。它們分別用圖1(a)和圖1(b)表示。在圖1(a)所示的圖G中,任一兩色子圖均是連通圖。而在圖1(b)所示的圖G中,含有c、d兩色交錯回路(υ3,υ4,υ7,υ8,υ3),Gab是分離的,它含有2個連通子圖。由此顯見,僅用Kempe法色交換是無法將圖G由A種著色改為B種著色,反之亦然。綜上分析,A.B.Kempe運用Kempe法色交換來證明四色猜想,必然導(dǎo)致在某些情況下有可能使證明陷入無結(jié)果的循環(huán)狀態(tài)。故Kempe的四色猜想證明缺乏嚴格性和周密性。2at色點交錯出現(xiàn)的路徑設(shè)圖G用a1,a2,…,aχ(G)等χ(G)種顏色著色。若G中點υi和υj在兩色子圖Gasat(s,t=1,2,…,χ(G);s≠t)的同一連通子圖中,則υi和υj之間至少存在一條as色點和at色點交錯出現(xiàn)的路徑,此路徑名為υi和υj間asat兩色交錯路徑,記為Pi,jasat。定理1設(shè)平面圖G已用χ(G)種顏色著色,(υk,υl)是G中任一兩色連通子圖Ga1a2的一條割邊,υk和υl分別著a1和a2色。令G′=G-(υk,υl),在G′的Ga1a2(υk)中各點顏色對調(diào),不影響Ga1a2(υl)中各點著色,從而υk由a1改為a2色,而υl保持a2色。在G′中添加邊(υk,υl),得圖Gu。在Gu中υk和υl相鄰且同為a2色,故Gu為非正常著色。若Gu中υk和υl之間存在χ(G)-1種兩色交錯路徑,則其中至少有一種兩色交錯路徑可被消除(變成非兩色交錯路徑)。2.1模型a3l方法(1):設(shè)圖Gu中υk和υl相鄰且同為a2色,依據(jù)定理1,可從υk和υl之間χ(G)-1種兩色交錯路徑中消除其中之一,不妨設(shè)被消除的兩色交錯路徑為Pk,la2a3。令Gu′=Gu-(υk,υl),由于Gu′中已不存在Pk,la2a3,故在Ga2a3(υl)中各點顏色對調(diào),不影響Ga2a3(υk)中各點著色。從而將υl由a2改為a3色,而υk保持a2色。在Gu′中添加邊(υk,υl),恢復(fù)G的拓撲結(jié)構(gòu),此時G中υk和υl分別著a2和a3色,G為正常著色,且為一個新著色方案。方法(2):設(shè)Gu中υk和υl相鄰且同為a2色。在Gu中包含υk或υl的另一種兩色連通子圖(不妨設(shè)它為Ga2a4)中作部分點的顏色對調(diào),使相鄰又同色的點對轉(zhuǎn)移到Ga2a4中一條割邊的兩端點,不妨設(shè)它們分別為υf和υg,得到Gui。由定理1知,在Gui中υf和υg之間至少有1種兩色交錯路徑不存在,令Gui′=Gui-(υf,υg)。此時可使Gui′中υf和υg成為異色,從而可使G獲得1個新著色方案。上述方法(1)和方法(2)統(tǒng)稱為轉(zhuǎn)移法色交換。2.2轉(zhuǎn)移法色交換與ga和b種Kempe法色交換須限定在一個連通兩色子圖中所有點的顏色對調(diào),而轉(zhuǎn)移法色交換沒有這種限定條件,它允許在一個兩色子圖中僅作部分點的顏色對調(diào),甚至僅將1個點的顏色由一種改著為另一種。它還允許相鄰且同色點對由一種兩色子圖轉(zhuǎn)移到另一種兩色子圖。顯見轉(zhuǎn)移法色交換是Kempe法色交換的延伸和發(fā)展,或者說Kempe法色交換只是在特定條件下的轉(zhuǎn)移法色交換。兩者相比,轉(zhuǎn)移法色交換的交換范圍靈活全面,作用深廣,功能齊全,應(yīng)用廣泛。前面例1已指出,僅用Kempe法色交換是無法實現(xiàn)最大平面圖G的A和B2種著色互相變換。然而,用轉(zhuǎn)移法色交換可實現(xiàn)它們互相變換。(1)當圖G由A種著色向B種著色轉(zhuǎn)移時,轉(zhuǎn)移過程如下:1)在圖1(a)所示的G中將υ3和υ5的顏色互換,得Gu1。在Gu1中υ5和υ6相鄰且同為c色,為非正常。2)在Gu1中將υ5和υ4的顏色對調(diào),得Gu2,Gu2中υ4和υ6相鄰且同為c色,為非正常。3)在Gu2中不存在P4,6cb。令Gu2′=Gu2-(υ4,υ6),在Gu2′的Gbc(υ6)中各點上的顏色b、c對調(diào),υ6由c色改為b色,υ8由b色改為c色。在Gu2′中添加邊(υ4,υ6),恢復(fù)G的原有拓撲結(jié)構(gòu),且得G的B種著色,如圖1(b)所示。(2)當圖G由B種著色向A種著色轉(zhuǎn)移時,其轉(zhuǎn)移過程是情況(1)的逆過程,不再贅述。3,3,4,5設(shè)平面圖G中點υ0的鄰點集為{υ1,υ2,υ3,υ4,υ5},令G′=G-υ0,并設(shè)G′可4-著色,在G′的一個著色方案中υ1,υ2,υ3,υ4,υ5分別著a,a,b,c,d色。為了便于敘述,將此著色方案的圖G′簡記為G0。定義1相干點對(υi·υj)。在G0中υi,υj(i,j=1,2,3,4,5;i≠j)著為異色,通過Kempe交換也不能著為同色,稱υi和υj為相干點對,記為(υi·υj),這表示在υi和υj之間至少存在1條奇段數(shù)的兩色交錯路徑。定義2不相干點對(υi;υj),在G0中υi,υj(i,j=1,2,3,4,5;i≠j)著為同色或通過kempe交換可著為同色,則υi和υj被稱為不相干點對,記為(υi;υj),這表示υi和υj著同色后兩者之間不存在奇段數(shù)的兩色交錯路徑,但允許存在偶段數(shù)兩色交錯路徑。在圖G0中υ1,υ3,υ4,υ54個點以及它們之間的兩色交錯路徑所構(gòu)成的子圖絕不是K4或K4的同胚圖,否則該子圖將與G中的υ0及其關(guān)聯(lián)的邊構(gòu)成K5或K5的同胚圖,由Kuratowski定理知,這與圖G的平面性相矛盾。因此,在υ1,υ3,υ4,υ5中至少有1個不相干點對。同理,在υ2,υ3,υ4,υ5中也至少有1個不相干點對。由此可見,{υ1,υ2,υ3,υ4,υ5}中僅有1個同色點對υ1和υ2時,它中還至少有2個不相干點對,設(shè)為(υ1;υ3)和(υ2;υ4)。定義3X圖和非X圖。能同時滿足下列5個條件的圖G0稱為X圖。(1){υ1,υ2,υ3,υ4,υ5}中(υ1;υ2),(υ1;υ3)和(υ2;υ4)為不相干點對,且其中只有1個同色點對。{υ1,υ2,υ3,υ4,υ5}中其余各點對均為相干點對;(如圖2所示,圖中實線的兩端點為相干點對,虛線的兩端點為不相干點對)。(2)在Gab(υ1)中作kempe法色交換,υ2和υ4變成相干點對;(3)在Gab(υ3)中作kempe法色交換,υ2和υ4變成相干點對;(4)在Gac(υ2)中作kempe法色交換,υ1和υ3變成相干點對;(5)在Gac(υ4)中作kempe法色交換,υ1和υ3變成相干點對;否則,圖G0被稱為非X圖。推論1當圖G0為X圖時,則G0中P3,5bd和P4,5cd間至少有1個d色公共中間點,并在該點它們互相交叉。為了強調(diào)圖的著色方案,從此處本文將X圖和非X圖改稱為G0的X和非X種著色,將G0的一著色方案為X或非X種著色簡記為:G0為x或xˉxˉ。引理1設(shè)簡單平面圖G有n個點,ne條邊,各點次數(shù)均大于或等于5,則G中至少有12個次數(shù)為5的點。證明用反證法。設(shè)G中至多有11個次數(shù)5的點,其余各點次數(shù)大于等于6。那么由平面圖必要條件知式(1)和式(2)相矛盾,故反證假設(shè)不成立。定理2設(shè)簡單平面圖G中各點次數(shù)大于等于5,υ0是G中任一次數(shù)為5的點,G的導(dǎo)出子圖G0=G-υ0。若G0為x,則使用轉(zhuǎn)移法色交換可將G0的著色方案由x變?yōu)閤ˉxˉ。證明不妨設(shè)υ0的鄰點在G0中構(gòu)成回路C0,令C0=(υ1,υ5,υ2,υ3,υ4,υ1),將圖G0嵌入一個平面,外區(qū)的周界為回路C0,并設(shè)G0用a,b,c,d等4種顏色著色,υ1,υ2,υ3,υ4,υ5分別著a,a,b,c,d色。因G0為x,故G0中必定存在(υ1;υ2),(υ1;υ3)和(υ2;υ4)等3個不相干點對,其中υ1和υ2是同為a色的點對。而且,G0中必定存在P3,5bd和P4,5cd,由推論1知它們至少有1個同為d色的公共中間點,并在該點它們相交叉。本文稱該點是G0為x的交叉點。因G0中存在P3,5bd,故Gac(υ1,υ4)∩Gac(υ2)=?,從而在Gac(υ1,υ4)中各點的顏色對調(diào),不影響Gac(υ2)中各點著色,反之亦然。因G0中存在P4,5cd,故Gab(υ1)∩Gab(υ2,υ3)=?,從而在Gab(υ1)中各點的顏色對調(diào),不影響Gab(υ2,υ3)中各點著色,反之亦然。不失一般性,設(shè)G0中存在P3,5bd和P4,5cd各一條,令P3,5bd=(υ3,…,υj,υk,υf,…,υ5),P4,5cd=(υ4,…,υs,υk,υt,…,υ5)。顯見υk為d色,且它是G0為x的交叉點,依據(jù)推論1和引理1,不妨設(shè)υk的次數(shù)為5。令G0′=G0-(υj,υk),故在G0′的Gbd(υj)中各點的顏色對調(diào),不影響Gbd(υk)中各點著色。從而υ3,υj均由b色改為d色,不影響υk和υ5著色,υk和υ5均保持d色。在G0′中添加邊(υj,υk),得Gou1。在Gou1中υj和υk相鄰且同為d色,故Gou1是非正常著色。但Gou1中(P3,jbd+(υj,υk)+Pk,5bd)是一條由b、d兩色組成的路徑,簡記為P3,5bd′。故在Gou1的Gac(υ1,υ4)中各點的顏色對調(diào),不影響Gac(υ2)中各點著色,反之亦然。從而Gou1有如下情況。為了論述簡潔,先作如下約定:令Goui′=Goui-(υj,υk),當Goui′中υj和υk變成異色點對時,在Goui′中添加邊(υj,υk),恢復(fù)G0的拓撲結(jié)構(gòu),此時G0為正常著色。(1)Gou1中Pj,kda和Pj,kdc兩者之一不存在。①設(shè)Pj,kda不存在。在Gou1中(υ3,υ2,υ5,υ1)是一條d,a兩色交錯路徑。(A)若Gou1′不存在Pk,5da,那么在Gou1′的Gda(υk)中各點的顏色對調(diào),υk由d色改為a色,υ3,υ2,υ5,υ1以及υj各點著色都不受影響,它們都保持原有的著色。此時,G0中υ1和υ2同為a色,υ3和υ5同為d色,故G0為xˉxˉ。(B)若Gou1′存在Pk,5da,那么在Gou1′的Gda(υk)中各點的顏色對調(diào),υk,υ3,υ2,υ5和υ1分別由d、d、a、d、a色改著為a、a、d、a、d色,但υj不受影響,它保持d色。此時,G0中υ1和υ2同為d色,υ3和υ5同為a色,故G0為xˉxˉ。②設(shè)Pj,kdc不存在。在Gou1中υ3和υ4相鄰,且它們分別著d和c色。(A)若在Gou1′中不存在Pk,5dc,那么Gdc(υk)中不含有υ5。(a)若Gdc(υk)中不含有υ3和υ4,那么在Gdc(υk)中各點的顏色對調(diào),υk由d色改為c色,不影響υj,υ5,υ3和υ4各點著色,它們分別保持d、d、d和c色。因此,G0中υ1和υ2同為a色,υ3和υ5同為d色,故G0為xˉxˉ。(b)若Gdc(υk)中含有υ3和υ4,那么在Gdc(υk)中各點的顏色對調(diào),υk,υ3和υ4分別由d、d和c色改為c、c和d色,但不影響υj和υ5著色,υj和υ5保持d色。此時,G0中υ1和υ2同為a色,υ4和υ5同為d色,故G0為xˉxˉ。(B)若在Gou1′中存在Pk,5dc,那么Gdc(υk)中含有υ5。(a)若Gdc(υk)中不含有υ3和υ4,那么在Gdc(υk)中各點的顏色對調(diào),υk和υ5都由d色改為c色,υ3和υ4著色不受影響,它們分別保持d和c色。此時,G0中υ1和υ2同為a色,υ4和υ5同為c色,故G0為xˉxˉ。(b)若Gdc(υk)中含有υ3和υ4,那么在Gdc(υk)中各點的顏色對調(diào),υk,υ5,υ3和υ4分別由d,d,d和c色改為c,c,c和d色,但υj著色不受影響,它保持d色。此時,G0中υ1和υ2同為a色,υ3和υ5同為c色,故G0為xˉxˉ。(2)Gou1中Pj,kda和Pj,kdc均存在。不失一般性,設(shè)υk的鄰點構(gòu)成回路Ck=(υj,υm,υs,υf,υt,υj)。顯見Gou1中υj,υm,υs,υf,υt分別著d,a,c,b,c色。依據(jù)定理1可消除Pj,kda和Pj,kdc兩者之一。①將Pj,kda消除。(A)若在Gou1中存在d、c兩色回路C1=(υj,…,υ4,…,υs,υk,υj),則在回路C1內(nèi)側(cè)a色點和b色點上作顏色對調(diào),將υm由a色改為b色,不僅消除了Pj,kda,而且不影響回路C0上各點著色,得Gou2。在Gou2中不存在Pj,kda,且υ1,υ5,υ2,υ3,υ4分別著a,d,a,d,c色?？梢奊ou2情況與Gou1的情況(1)①類同,故它的變換結(jié)果同樣是G0為xˉxˉ。(B)若Gou1中不存在回路C1。從而Gou1中不存在Pj,kdc=(υj,…,υ4,…,υs,υk)。又因Gou1中存在P3,5bd′,故在Gou1的Gac(υ1,υ4)中各點顏色對調(diào),將υ1,υ4,υs,υm分別由a,c,c,a色改為c,a,a,c色。既不產(chǎn)生Pj,kda=(υj,…,υ4,…,υs,υk),又不影響Gac(υ2)中各點著色,υ2,υt分別保持a和c色,得Gou2。在Gou2中不存在Pj,kda,且υ1,υ5,υ2,υ3,υ4分別著c,d,a,d,a色。此時Gou2情況和Gou1的情況(1)①類同。(a)若Gou2′中不存在Pk,5da,則G0中υ2和υ4同為a色,υ3和υ5同為d色,且為正常著色,故G0為xˉxˉ。(b)若Gou2′中存在Pk,5da,則G0中υ2和υ4同為d色,υ3和υ5同為a色,且為正常著色,故G0為xˉxˉ。②將Pj,kdc消除。在使C0上有2個a色點和2個d色點,或有2個c色點和2個d色點條件下,消除Pj,kdc和消除Pj,kda對G0為xˉxˉ而言是等價的,其過程與情況(2)①類同,這里不再贅述。綜上分析,所有可能的情況,轉(zhuǎn)移法色交換可使G0的著色方案由x變換成xˉxˉ。例2設(shè)平面圖G0如圖3所示。由于該圖G0同時滿足定義3中5個條件,故G0的著色方案為x。依據(jù)定理2,采用轉(zhuǎn)移法色交換必然可使G0的著色方案由x變換成xˉxˉ。其過程如下:(1)設(shè)G0′=G0-(υ10,υ14),在G0′的Gbd(υ14)中各點顏色對調(diào),使υ14,υ3,υ23,υ21,υ17,υ19分別改染為b,d,b,d,b,d色。在G0′中添加邊(υ10,υ14),恢復(fù)G0的拓撲結(jié)構(gòu),將它記為Gou1。在Gou1中υ10和υ14相鄰且同為b色是非正常著色。(2)設(shè)Gou1′=Gou1-(υ10,υ14),由于在Gou1′的υ10和υ14之間不存在P10,14ab,故在Gou1′的Gab(υ14)中作Kempe交換,使υ14,υ16,υ17分別改染為a,b,a色。而υ10著色不受影響,它保持b色,在Gou1′中添加邊(υ10,υ14),恢復(fù)圖G0的拓撲結(jié)構(gòu),且為正常著色。圖G0新的著色方案如表1所示。由此可見,當圖G0為新著色方案時,{υ1,υ2,υ3,υ4,υ5}中含有2個同色點對,故此時圖G0為xˉxˉ。定理3若圖G0為xˉxˉ,則G0中υ1,υ2,υ3,υ4,υ5等5個點可3-著色。證明(1)當G0不滿足定義3中條件(1)時。(A)設(shè){υ1,υ2,υ3,υ4,υ5}中有4個以上不相干點對,不妨設(shè)有4個。除原有3個外,另設(shè)一個不相干點對為(υi;υj)。(a)當υi和υj之一為a色點時,不妨設(shè)它為(υ1;υ5)。因υ1和υ5為不相干點對,故不存在P1,5ad,從而也不存在偶段數(shù)的P1,2ad。那么,在Gad(υ1)中各點顏色對調(diào),υ1改染為d色,υ2不受影響,保持a色。此時,若(υ3·υ1)和(υ3·υ5)兩者之一存在,則υ2和υ4必為不相干點對。故在Gac(υ2)中各點顏色對調(diào),υ2改染為c色,υ4不受影響,它保持c色。可見υ1,υ2,υ3,υ4,υ5分別著d,c,b,c,d色,故上述5個點可3-著色。反之,若存在(υ2·υ4),則(υ3·υ1)和(υ3·υ5)均不存在。故在Gbd(υ3)中各點顏色對調(diào),υ3改染為d色,υ1和υ5都不受影響,都保持d色?？梢姦?,υ2,υ3,υ4,υ5分別著d,a,d,c,d色,故上述5個點可3-著色。(b)當υi和υj均不為a色點時,不妨設(shè)它為(υ4;υ5)。那么,在Gcd(υ4)中各點顏色對調(diào),υ4改染為d色,υ5不受影響,保持d色。此時υ1,υ2,υ3,υ4,υ5分別著a,a,b,d,d色,故上述5個點可3-著色。(B)當{υ1,υ2,υ3,υ4,υ5}中有2個以上同色點對時,顯然上述5個點可3-著色。(2)當G0不滿足定義3中條件(2),(3),(4)和(5)之一時。不妨設(shè)它不滿足條件(2)時。已知υ4和υ5為相干點對,從而存在P4,5cd。那么,在Gab(υ1)中各點顏色對調(diào),υ1改染為b色,υ2和υ3都不受影響,它們分別保持a色和b色。又由于在Gab(υ1)中各點顏色對調(diào),υ2和υ4仍保持為不相干點對,從而在Gac(υ4)中各點顏色對調(diào),υ4改染為a色,υ2不受影響,保持a色。此時υ1,υ2,υ3,υ4,υ5分別著b,a,b,a,d色,故上述5個點可3-著色。4轉(zhuǎn)移法色交換定理4(四色定理)每一個平面圖是可4-著色的。證明當平面圖G不超過4個點時,定理顯然成立。應(yīng)用歸納法,假定平面圖G中有n-1個點,定理成立。當G有n個點時。因為G是平面圖,故G中至少有一個點的次數(shù)不大于5。不妨設(shè)d(υ0)≤5。導(dǎo)出子圖G′=G-υ0,G′具有n-1個點,根據(jù)