關於NP=P：圖的3-著色問題的O（n^9）演算法及不完整證明
06-25
關於NP=P：圖的3-著色問題的O（n^9）演算法及不完整證明
推薦閱讀：
關於NP=P：圖的3-著色問題的O（n^9）演算法及不完整證明
江西省余江二中 胡錢元（湖南大學數學本科2000級）摘要：本文給出了圖的3-著色問題（一個NP完全問題）的O（n^9）遞歸演算法。除了命題0我只能給出部分證明外，本文的其它部分都有數學上嚴格的證明。
關鍵詞：3-著色問題，多項式時間，演算法，NP完全問題，NP=P概述 對於任意簡單無向圖G，判斷G的頂點可否3-著色是一個NP完全問題，哪怕G是平面圖且每個頂點的度都不大於4[1]。圖的3-著色問題之所以困難，在於兩點：一、即使圖可3-著色，但若其中存在不相鄰卻必須著色相同或不同的頂點，要確定這樣的頂點非常困難（如果圖不可3-著色，則困難在於找到一個極小的色數為4的子圖——該子圖去掉任意一個頂點及其所有關聯邊都可以3-著色）；二、即使圖可3-著色，且其中任意兩個不相鄰的頂點可以著色相同或者不同，找到一個多項式時間的3-著色方案也不容易。本文對這兩點一一做了分析，
給出了圖3-著色問題的一個多項式時間演算法，該演算法的時間複雜度不超過O（n^9）。由概述，先給出一些重要的定義，這些定義對於圖的3-著色問題的多項式時間演算法起到了關鍵作用。定義（3-可著色）：設G=（V，E）是簡單無向圖，G存在奇迴路，若存在函數f：V→{1,2,3}，使得只要（u，v）∈E，就有f（u）≠f（v），則稱G是可3-著色的，G的頂點色數為3，f是G的一個正確的3-著色方案。定義（對等點）：設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，va、vb是G中不相鄰的兩個頂點，若對G的任意一個正確的3-著色方案，va、vb都著相同顏色，則稱「va、vb是G的一對對等點」
（或「G存在對等點va、vb」，「va（vb）存在對等點vb（va）」）。定義（比鄰點）：設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，va、vb是G中不相鄰的兩個頂點，若對G的任意一個可行的3-著色方案，va、vb都著不同顏色，則稱「va、vb為G的一對比鄰點」（或「G存在比鄰點va、vb」，「va（vb）存在比鄰點vb（va）」）。定義（理想圖）：設G=（V，E）是簡單無向圖，G的頂點色數為3，若對G的任意兩個不相鄰頂點va、vb，存在對G的兩個正確的3-著色方案，使得在這兩種方案中，va、vb的著色分別相同和不同，則稱G為理想圖。顯然，在頂點色數為3的簡單無向圖中，理想圖的3-著色是「最容易」的。由定義可知，理想圖中不存在對等點、比鄰點。並且容易知道理想
圖的任意4階子圖的邊數不大於4（否則G有對等點）。定義（胡圖）：設G=（V，E）是簡單無向圖，G的頂點色數為3，若G存在對等點或比鄰點，則稱G為胡圖。定義（極小胡圖）：設G=（V，E）是胡圖，若G去掉任意一條邊所得圖都是理想圖，則稱G為極小胡圖。命題0.設G是階數大於10的極小胡圖，則有：（1）G最多只有一對對等點。當G存在對等點va、vb時，G的任意一對比鄰點中必有一個頂點是va或vb。（註：這部分可以證明。）（2）若G不存在對等點，則G只有一對比鄰點。（註：這部分缺乏嚴格的證明。）
事實上，命題0的條件太強了，有以下弱化版本。命題0.1設G是階數大於10的極小胡圖，則存在常數c，使得G最多只有c對對等點；若G沒有對等點，則G最多只有c對比鄰點。只要上述命題0.1為真，則圖的3-著色問題存在多項式時間演算法，即有NP=P。定義（簡單胡圖）：設G=（V，E）是胡圖，若G去掉任意一個頂點及其所有關聯邊所得圖都是理想圖，則稱G為簡單胡圖。定理0.簡單胡圖必有子圖是極小胡圖。證明：顯然。注意：理想圖可以有真子圖是極小胡圖（存在至少一對比鄰點）。
定理1.設G=（V，E）是簡單無向圖，G的子圖G1的頂點色數S（G1）=3，va、vb是G1的一對對等點，但va、vb在G中相鄰，則G的頂點色數S（G）≥4。證明：顯然。推論1.設G=（V，E）是簡單無向圖，S（G）=3，va、vb是G的一對對等點，E=E∪{（va，vb）}，G=（V，E）,則S（G』）=4。推論2.設G=（V，E）是簡單無向圖，S（G）=3，va、vb是G的一對比鄰點，E=E∪{（va，vb）}，G=（V，E）,則S（G』）=3。定理2.設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，va、vb是G的一對對等點，vb、vc也是G中的一對對等點，則va、vc是G的一對對等點。
證明：顯然。定理3.設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，va、vb是G的一對對等點，vb、vc是G中的一對比鄰點，且va、vc在G中不相鄰，則va、vc是G的一對比鄰點。證明：顯然。定理4.設G=（V，E）是簡單無向圖，G的子圖G1的頂點色數S（G1）=3,va、vb是G1的一對對等點，則G的頂點色數S（G）=3的必要條件是：va、vb是G中的一對對等點。證明：顯然。定義（收縮）：設G=（V，E）是n階簡單無向圖，V={vi｜1≤i≤n，i∈N}，
va、vb是G中兩個不相鄰的頂點，a＜b，令V={vi｜1≤i≤n，i≠b，i∈N}E={（vi，vj）｜（vi，vj）∈E，i≠b,j≠b}∪{（va，vi）｜（vb，vi）∈E，且va與vi在G中不相鄰}，G=（V，E），稱G是G的以va、vb為對象的收縮圖。由定義可知，G的以va、vb為對象的收縮圖G就是在G中去掉頂點vb，再把所有原來與vb相鄰但不與va相鄰的頂點都跟va連接起來得到的。定義（導出子圖）：設G=（V，E）是n階簡單無向圖，設G1=（V1，E1）是G的子圖，若對任意va、vb∈V1，（va，vb）∈E，都有（va，vb）∈E1，則稱G1為G的導出子圖。定義（支撐子圖）：設G=（V，E）是n階簡單無向圖，設G1=（V，E1）
是G的子圖，則稱G1為G的支撐子圖。定理5.設G=（V，E）是n階簡單無向圖，V={vi｜1≤i≤n，i∈N}，va、vb是G中兩個不相鄰的頂點，a＜b，G是G的以va、vb為對象的收縮圖。G的頂點色數為S（G）,G的頂點色數為S（G）,則有S（G）≤S（G）。證明：只需證S（G）≥S（G），這是顯然的。定理6.設G=（V，E）是n階簡單無向圖，V={vi｜1≤i≤n，i∈N}，G的頂點色數S（G）=3，va、vb是G的一對對等點，a＜b，G是G的以va、vb為對象的收縮圖，則S（G）=3。證明：顯然。由定理6可知，一個n階的頂點色數為3且存在對等點的簡單無向圖G，經過作最多O（n^2）次的關於對等點的收縮圖後，可以得到G，使得G的頂點色數為3，且G中不再有對等點。再由定理1的推論2可知，對任意一個n階的、頂點色數為3、不存在對等點但是存在比鄰點的簡單無向圖G，將它的比鄰點全部連接起來（這最多只需要O（n^2）次），所得圖就不再有對等點或比鄰點了，即最後得到了一個理想圖。演算法大綱
演算法意圖：在簡單無向圖G中找到一個極大獨立集（所有「去點」
構成的集合），若G去掉該極大獨立集的所有頂點及其所有關聯邊所得圖不含奇迴路，則G可以3-著色。演算法中一些名詞的含義如下定義（1級待定點）：若vi是待定點，vi的所有鄰點都是留點，則稱vi為1級待定點。定義（2級待定點）：若vi是待定點，存在頂點全部是留點的道路L，L的邊數為奇數，且L的兩個端點都與vi相鄰，則稱vi為2級待定點，稱道路L為2級待定點vi的判定道路。定義（3級待定點）：若vi、vj是相鄰的兩個待定點，存在頂點全部是留點的道路L，L的邊數為偶數，且L的兩個端點分別與vi、vj相鄰，則稱vi、vj為3級待定點，道路L為3級待定點vi、vj的判定道路。註：在演算法中任何一次取2級待定點為去點時，若有多個2級待定點，則優先取判定道路邊數最少的一個2級待定點為2級去點。在演算法中任何一次取3級待定點為去點時，若有多個3級待定點，則優先取判定道路邊數最少的一個3級待定點為3級去點。定理7.運用演算法模塊一，可以判斷簡單無向圖H中距離為2的兩個頂點vx、vy是否為H的平凡對等點。
演算法第一部分
用模塊一判斷H是否有平凡對等點。若有，則得到H（G）的等效收縮圖H，H頂點色數為3當且僅當H頂點色數為3。作賦值運算H=H，若H含K4子圖，則H的頂點色數至少為4。否則繼續執行模塊一直到H不含平凡對等點為止。演算法第二部分
用模塊二得到G的一個正確的3-著色方案，或者得到G0，G0至少滿足以下條
件之一：（1）G0的頂點色數為4；（2）G0存在對等點；（3）G0存在比鄰點。演算法第三部分
用模塊三得到G0，G0必為以下情形之一：
（1）G0的頂點色數為4。此時G0的任意收縮圖的頂點色數都大於3。（2）G0是簡單胡圖，有且只有一對對等點，任意一對比鄰點都有一個端點是G0的對等點。設va、vb是G0的對等點，a＜b，則G0的va、vb為對象的收縮圖在運用模塊一之後可得理想圖（從而該圖運用模塊二一定可以3-著色）。在G0中連接va、vb所得圖的頂點色數為4；而將G0中其它任意兩個不相鄰頂點連接起來所得圖的頂點色數為3。（3）G0是簡單胡圖，不存在對等點，有且只有一對比鄰點。設va、vb是G0的比鄰點，a＜b，在G0中連接va、vb所得圖運用模塊一之後可得理想圖（從而該圖運用模塊二一定可以3-著色）。G0的以va、vb為對象的收縮圖的頂點色數為4；而G0的以其它任意兩個不相鄰頂點為對象的收縮圖的頂點色數為3。演算法第四部分這部分判斷G0的頂點色數是否為3。方法如下：取G0的不相鄰的兩個頂點vp、vq，作G0的的以vp、vq為對象的收縮圖Gpq，作賦值運算H=Gpq。若H在執行本演算法第一部分和第二部分後就可以得到一個正確的3-著色方案（有時執行演算法第一部分就可得到H的一個正確的3-著色方案），則G0的頂點色數為3。否則，若遍取所有的Gpq，作賦值運算H=Gpq,H在實行演算法第一部分和第二部分後所得判定圖仍然有奇迴路——即沒得到一個正確的3-著色方案，則G0的的頂點色數為4，G的頂點色數至少為4。演算法第五部分在這裡，G0的頂點色數為3。這部分判斷G0是否存在對等點，如有對等點va、vb，a＜b，則能找出來。則G0色數為3當且僅當G0的以va、vb為對象的收縮圖色數為3。則G色數為3當且僅當G0的以va、vb為對象的收縮圖色數為3。方法如下：取G0的不相鄰的兩個頂點vs、vt，在G0上添加邊（vs，vt）得圖Gst，作賦值運算H=Gst，對H先執行演算法第一部分使得H不含平凡對等點，再執行第四部分，若H的頂點色數為4，則vs、vt是G0的一對對等點；否則vs、vt不是G0的一對對等點。若G0的任意兩個不相鄰的頂點vs、vt都不是對等點，則G0不存在對等點，那麼G0有且只有一對比鄰點。演算法第六部分在這裡，G0頂點色數為3、不存在對等點、有且只有一對比鄰點。這部分找到G0的比鄰點va、vb，a＜b。則G0色數為3當且僅當在G0上添加邊（va、vb）所得圖色數為3。則G色數為3當且僅當在G0上添加邊（va、vb）所得圖色數為3。方法如下：取G0的不相鄰的兩個頂點vs、vt，作G0的的以vs、vt為對象的收縮圖Gpst，作賦值運算H=Gst，對H先執行演算法第一部分使得H不含平凡對等點，再執行第四部分，若H的頂點色數為4，則vs、vt是G0的一對比鄰點；否則vs、vt不是G0的一對比鄰點。由以上六部分，對於G，我們總能在O（n^8）的時間內得到G0，使得G0的階數比G的小，G的頂點色數為3當且僅當G0的頂點色數為3。則運用O（n）次後必然可以確定G是否可以3-著色；若可，則同時得到了G的一個正確的3-著色方案；否則G的頂點色數至少為4，G不可3-著色。算例
推薦閱讀：