摘要：完美圖，指的是用盡可能有限的一組顔色着色的網絡圖。在給圖表着色時，每一個處于互相之間密集聯系的“團”内的節點都必須被指定一個獨一無二的顔色。而至今為止，關于如何處理方形結構的着色，仍然沒有得到解決。
四年前，數學家maria chudnovsky 遭遇到一個常見困境：如何給120名參加婚禮的客人安排好座位,在所有客人中有可能存在沖突，問題的關鍵在于如何避免将有沖突的客人安排在同一張桌子前就座。很幸運，這個問題恰巧在她的研究領域内。maria把客人視作網絡中的節點，用線将“不相容”的節點間連接配接在一起。問題于是轉化為：用一系列不同顔色來代表不同餐桌，再将節點分别着色。隻要毗鄰節點保證不同色，婚宴中便不會出現尴尬事件。
無論是節點還是參加同一場婚禮的客人，他們在數學家眼中都可以看做是位于同一網絡中的、相聯系的事物。圖表的着色是一個被廣泛研究的課題，目的就是把這些事物分割成沒有沖突的集合。由于節點内部的複雜聯系，大部分網絡很難用有限的顔色組合完成着色。網絡規模越大，需要的顔色越多。從一個節點到另一節點，不停的變化顔色組合，最終你會陷入一種“交通堵塞”，迫使你選擇更多新的顔色。同理，在現實世界中，座位表、時間表和運輸路線安排鮮有最優解決方案。自從1960年起，數學家們就已經通過所謂“完美圖”(perfect graph)避免了着色難題。普林斯頓大學一位38歲的數學教授chudnovsky稱：“完美圖非常适用于着色難題。”
根據其定義，完美圖指的是用盡可能有限的一組顔色着色的網絡圖。在給圖表着色時，每一個處于互相之間密集聯系的“團”（cliques）内的節點都必須被指定一個獨一無二的顔色，是以任何一個網絡都至少需要與其規模最大的“團”裡的節點同等數量的顔色。在大部分網絡中，你需要的顔色甚至比這個更多。但是在完美圖表中情況則不同。正如法國圖論領域理論家claude berge 在1961年所定義的：完美圖表所需顔色的數量與其最大“團”的規模大小一緻。顔色數量（chromatic number）必須與“團數量”（clique number）完全相等，因為完美圖表的每個子集都是通過删除它的一些節點完成的。諸如此類的完美在現實世界鮮有出現，但是它的特殊屬性使得完美圖比其他非完美圖更易于分析和證明定理。
然而在半個世紀之後，關于完美圖一個顯而易見的問題仍舊無人作答：究竟該如何為完美圖着色？普林斯頓大學另外一位圖論理論家paul seymour認為：“完美圖是為着色而生的結構圖，不知道如何為其着色是非常惱人的一件事。對于一個數學家，類似問題令人着魔，每一個數學家都渴望解決完美圖的着色問題。”
現在， chudnovsky 和她的合作者在為完美圖着色的理論方面取得了顯著的進步。alan tucker，石溪大學（stony brook university）的數學家表示：在過去的幾年裡，他們已經“啃掉了餡餅的不同部分”，證明了完美圖裡大型子集的着色理論。今年10月份，chudnovsky和她的合作者（irene lo,frédéric maffray, nicolas trotignon and kristina vušković）一起釋出一個完美圖的着色理論，該理論中的完美圖表不包括由四個節點組合的方形結構（square）。gérard cornuéjols，卡内基梅隆大學（carnegiemellon university）的數學家表示：“這個理論解決了一些常見的問題。”
希望曆史能夠重演。15年前，研究人員争相證明完美圖的着色定理。在cornuéjols, vušković和michele conforti于2001年證明了“square-free”完美圖的着色定理後，chudnovsky表示：“下一步便可以推而廣之到更普遍的網絡結構中”。
在2002年，chudnovsky同她的博士導師（seymour）以及另外兩個合作者共同證明了“強完美圖定理”（strongperfect graph theorem），證明如何完成一個完美圖。他們的論證發表在2006年的《the annals of mathematics》上，占了150頁的篇幅。但強完美圖定理提供了一個簡單的令人驚奇的完善方案： 就像berge在54年前猜想的一樣，隻有一圖不包含由5個或更多節點組成的“奇洞”（odd holes）或 “反奇洞” (odd antiholes)時才能被稱為完美圖。
奇洞是一個閉合的回路，它穿過圖表的一部分，經過奇數個節點。（如果把圖畫在紙上，沿此路徑用剪刀剪開，會從紙上剪下一個洞。）在一個“反奇洞”中，形成它的節點與該圖其它所有節點都連接配接在一起，距離它最近的節點除外，最終形成一個星型。讓我們看看這些奇點為什麼會導緻圖形不完美：例如“五個節點組成的奇洞”，就像一個五角大廈，它的團數（cliques） 是2，然而隻有成對兒的連續節點才能連接配接在一起。但如果僅用兩種顔色給五個節點的奇洞着色，例如藍色和綠色，很快就會陷入麻煩：第5個節點一邊緊鄰綠色節點，一邊緊鄰藍色節點。我們需要第三種顔色給這個節點着色。（三個節點的奇洞，不像更多節點的奇洞，屬于完美圖表，因為它們的團數（cliques）是3）
現實世界的圖表，如會議時間表，曼哈頓地鐵系統或人類神經網絡，通常含有奇洞，使得完美圖的研究成為重要的智能運用研究。美國利茲大學教授vušković說：“這種完美圖可以幫助你開發尖端科技，進而應用于其他類型的網絡結構中。”
然而完美圖仍然十分複雜，得到完美圖需要考慮其内在網絡結構，但是這一過程仍缺乏簡潔而有力的論證。alan tuck表示：“現有零碎的發現并不能幫助我們得到完整的理論。” 在為缺少square（也稱4節點奇洞）的網絡設計最佳着色方案的理論中，chudnovsky等人采用了一種“分布化解”的方案，将網絡分為不同部分，分别着色後合并為完整網絡。
在為網絡着色前，chudnovsky等人首先将網絡結構簡化為一種“棱狀”（prism）結構，每一組“棱狀”結構中包含一對三邊相連的三點網絡（three-holes）。
其次，通過分析 “棱狀”結構如何與剩餘網絡聯系起來，研究者将圖分割為左右兩部分，并通過部分橋梁（hinge）節點将兩部分連接配接起來。負責連接配接兩部分圖的橋梁節點也可能包含方格形（square）結構，但是方格形結構（square）和橋梁（hinge）有太多的着色方案，在現有證明中暫時不考慮這類特殊案例。
假如左右兩部分其中一方仍包含“棱狀”結構，研究者則會将其繼續向下劃分，直到不再包含“棱狀”結構為止。（此時，方形（square）結構再次會制造障礙，過多的方形結構需要過多分割，導緻着色效率下降。）
當左右部分均不再包含“棱狀”結構，便可以開始着色過程。研究者證明存在一種高效方案可以同時為左右兩部分及其橋梁節點着色。通常，為橋梁節點着色的方案并不能完全契合（譯者注：即不一定可以保證相鄰橋梁節點顔色不同），于是，着色過程的最後一步即為調整橋梁節點的顔色直到保證其顔色不會與各自毗鄰的節點（neighboring nodes）顔色相同為止。
至此為止，關于如何處理方形結構的着色仍然沒有得到解決。該領域的研究者就目前研究是否已經實作了完美圖着色方案（perfect graph coloring theorem）仍然無法達成共識。在vušković 看來：“現有不包含方形結構的完美圖已經涵蓋了最優圖的複雜結構，是以也已經很大程度接近了更普遍的網絡結構。” cornuéjols則認為：“離解決所有網絡結構的最優着色方案還有相當遠的距離。”
五位研究者将在今年12月于法國格勒諾布爾（grenoble）見面，讨論如何将他們的論證推廣到更普遍的網絡結構中。
trotignon 是巴黎高等師範的一名數學及計算機科學家，他表示：“在完美圖的着色方案設計上，我們已經推進了一大步，然而還需要投入更多努力。我個人的感覺是這一領域最終一定會得到解決。在解決不包含方形結構的方案出現之前（譯者注：即chudnovsky等人的方案），我并不抱希望。”
有人認為，假設研究者能夠成功提出完美圖的着色定理，将會标志着一個時代的終結。cornuéjols認為：“對我而言，這是關于完美圖最後一個尚待解答的大疑問。”
原文釋出時間為：2015-11-11
本文來自雲栖社群合作夥伴“大資料文摘”，了解相關資訊可以關注“bigdatadigest”微信公衆号