由圖的3-著色問題論四色問題及NP=P?

作者簡介： @胡qy 湖南大學04年本科畢業、高中數學老師、業餘時間研讀並發表paper

歡迎原鏈接轉發，付費轉載請前往 @留德華叫獸 的主頁獲取信息，盜版必究。 敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態： 『運籌OR帷幄』大數據人工智慧時代的運籌學--知乎專欄

前言

作者@胡qy本科湖南大學數學專業，2003年底開始研究四色問題的手工證明。由於不注意查文獻，走了很多彎路，也加深了對著色問題的理解。自2011年了解了NP完全問題及其實用意義，得知一般的圖著色問題是NP完全的，在考慮一般的圖著色問題中發現仍然繞不過圖的3-著色問題，查閱文獻發現原來圖的3-著色問題也是NP完全問題。某一天突然得到幾個重要的概念，經過對這些概念的深刻理解，自認為對四色問題以及NP=P?的研究有突破性的進展，幾經斟酌，修補漏洞，最終得到了圖的3-著色問題的多項式時間演算法。然而，其中一個關鍵命題的嚴格且完整的證明卻始終得不到，雖然本人越驗證越覺得其正確。因此，拋磚引玉，望高人能解我疑惑。

摘要：本文給出了證明四色定理的一個新思路；給出了對平面圖的頂點進行4-著色的多項式時間演算法；給出了圖的3-著色問題（著名的NP完全問題）存在多項式時間演算法——即NP=P——的充要條件。在假設所給的NP=P的充要條件成立的基礎上（本人所能給的是部分證明，嚴格但是不完整），本文給出了圖的3-著色問題的多項式時間演算法。

關鍵詞：平面圖 3-著色問題 多項式時間 演算法 NP完全問題

正文

概述：著名的「四色定理」說明，平面圖的頂點可以4-著色。但證明是由計算機得到的，至今沒有手工的證明。

對於任意簡單無向圖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的一對對等點」4-（或「G存在對等點va、vb」，「va（vb）存在對等點vb（va）」）。

例1.如圖1所示，G=（V，E），V={v1，v2，v3，v4}，E={（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）},v1、v4是G的一對對等點。

例2.如圖2所示，G=（V，E），V={vi|1≤i≤9}，E={（v1，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v5），（v3，v6），（v3，v7），（v4，v8），（v4，v9），（v5，v6），（v5，v8），（v6，v7），（v7，v9），（v8，v9）},v3、v5是G的一對對等點。

例3.如圖5所示，G=（V，E），V={vi|1≤i≤18}，E={（v1，v2），（v1，v3），（v2，v3），（v1，v4），（v1，v5），（v4，v5），（v2，v6），（v2，v7），（v6，v7），（v7，v8），（v7，v18），（v8，v18），（v3，v8），（v3，v9），（v8，v9），（v4，v9），（v4，v10），（v9，v10），（v10，v11），（v10，v18），（v11，v18），（v5，v11），（v5，v12），（v11，v12），（v12，v16），（v12，v17），（v16，v17），（v14，v15），（v14，v16），（v15，v16），（v6，v13），（v6，v14），（v13，v14）},v6、v12、v15中的任意兩個是G的一對對等點；

v13、v16是G的一對對等點；v14、v17是G的一對對等點。

定義（比鄰點）：設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，va、vb是G中不相鄰的兩個頂點，若對G的任意一種可行的3-著色方案，va、vb都著不同顏色，則稱「va、vb為G的一對比鄰點」（或「G存在比鄰點va、vb」，「va（vb）存在比鄰點vb（va）」）。

例4.如圖3所示，G=（V，E），V={vi|1≤i≤12}，E={（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v2，v5），（v4，v5），（v4，v8），（v4，v9），（v8，v9），（v9，v10），（v9，v11），（v10，v11），（v7，v11），（v7，v12），（v11，v12），

（v3，v6），（v3，v7），（v6，v7），（v5，v6），（5v，v10），（v6，v10）},v1、v8、v12中的任意兩個是G的一對比鄰點。

即G有3個頂點構成3對比鄰點。

定義（理想圖）：設G=（V，E）是簡單無向圖，G的頂點色數為3，若對G的任意兩個不相鄰頂點va、vb，存在對G的兩種正確的3-著色方案，使得在這兩種方案中，va、vb的著色分別相同和不同，則稱G為理想圖。

由定義可知，理想圖中不存在對等點、比鄰點。並且容易知道理想圖的任意4階子圖的邊數不大於4（否則G有對等點）。

定義（胡圖）：設G=（V，E）是簡單無向圖，G的頂點色數為3，若G存在對等點或比鄰點，則稱G為胡圖。

定義（極小胡圖）：設G=（V，E）是胡圖，若G去掉任意一條邊所得圖都是理想圖，則稱G為極小胡圖。

定義（簡單胡圖）：設G=（V，E）是胡圖，若G去掉任意一個頂點及其所有關聯邊所得圖都是理想圖，則稱G為簡單胡圖。

定理0.簡單胡圖必有子圖是極小胡圖。

證明：顯然。

注意：理想圖可以有真子圖是極小胡圖。例如，在圖3中添加3條邊（v1，v8），（v1，v12），（v8，v12）所得圖即為理想圖。

例5.例1和例2中的G都是極小胡圖。例4中的G去掉v12及其所有關聯邊所得圖也是極小胡圖。

定理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。

例6.如圖4所示，G=（V，E），V={vi|1≤i≤7}，E={（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4），（v4，v5），（v4，v6），（v5，v6），（v5，v7），（v6，v7），（v1，v7）}，G去掉邊（v1，v7）得到G1，顯然S（G1）=3，v1、v7是G1的一對對等點，但v1、v7在G中相鄰，則G的頂點色數S（G）≥4。

定理2.設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，va、vb是G的一對對等點，vb、vc也是G中的一對對等點，則va、vc是G的一對對等點。

證明：顯然。

例7.在例3中，v6、v15是G的一對對等點，v15、v12也是G中的一對對等點，則v6、v12是G的一對對等點。

定理3.設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，va、vb是G的一對對等點，vb、vc是G中的一對比鄰點，且va、vc在G中不相鄰，則va、vc是G的一對比鄰點。

證明：顯然。

例8.在例3中，v6、v15是G的一對對等點，v15、v5是G中的一對比鄰點，且v6、v5在G中不相鄰，則v6、v5是G的一對比鄰點。

定理4.設G=（V，E）是簡單無向圖，G的子圖G1的頂點色數S（G1）=3,va、vb是G1的一對對等點，則G的頂點色數S（G）=3的必要條件是：va、vb是G中的一對對等點。

證明：顯然。

定義（素圖）：設G=（V，E）是極大平面圖，G的階數大於4。若G的階數大於3的任意真子圖都不是極大平面圖，則稱G為素圖,；

否則稱G為合圖。

要證明四色定理，只需證明任意極大平面圖的頂點色數都小於5。

顯然，只需要證明任意素圖的頂點色數小於5。

公開的文獻有以下結果：四色定理成立當且僅當任意極大平面圖對應的4-正則圖的頂點色數為3。

由以上結果，很容易得到四色定理的一個等價命題。

命題1.四色定理成立當且僅當任意素圖所對應的4-正則圖的頂點色數為3。

事實上，我們可以證明：任意素圖所對應的4-正則圖G是理想圖；G去掉一個K3子圖的3條邊，得圖G1，G1再去掉任意一個度為2的頂點得圖G2，則G2是不含對等點、有且只有一對比鄰點的極小胡圖。

參考文獻

[1]M.R.Garey,D.S.Johnson and L.Stockmeyer, Some simplified

NP-complete graph problems,Theoretical Computer Science(1976)

237-267.

第一篇完。

在下篇中，本人將給出關於四色問題的更多細節，包括對任意素圖所對

應的4-正則圖的多項式時間3-著色演算法。

如果你是運籌學/人工智慧碩博或在讀，請添加微信號：zf13772441490（備註請務必按照：姓名/昵稱-加群類型-單位/學校-最高/在讀學位-研究方向，否則不會通過），她會拉你進全球運籌或AI學者群（群內學界、業界大佬雲集）。

如果你是運籌學/控制論/隨機優化愛好者，歡迎加qq群：686387574

如果你是人工智慧愛好者，歡迎加qq群： 685839321

敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態。

專欄文章匯總和有獎投稿須知：

『運籌OR帷幄』專欄文章分類匯總+面向學術界/工業界徵稿(含招聘廣告)+專欄編輯/審稿招募

推薦閱讀：