圖譜著色

圖譜著色?是圖譜標記的一個特例；它是對圖譜中的元素進行傳統(tǒng)上稱為顏色的標簽分配，并受到某些約束。在其最簡單的形式中，它是一種為圖的頂點著色的方法，使相鄰的兩個頂點不具有相同的顏色；這被稱為頂點著色。同樣，邊著色為每條邊分配顏色，使相鄰的兩條邊不具有相同的顏色，而平面圖的面著色為每個面或區(qū)域分配顏色，使共享邊界的兩個面不具有相同的顏色。頂點著色經(jīng)常被用來介紹圖形著色問題，因為其他著色問題可以轉(zhuǎn)化為頂點著色實例。

圖形著色的第一個結(jié)果幾乎只涉及平面圖形的地圖著色。在試圖為英格蘭各郡的地圖著色時，弗朗西斯-格思里提出了四色猜想，指出四種顏色足以為地圖著色，從而使具有共同邊界的區(qū)域都不會得到相同的顏色。格思里的弟弟將這個問題傳給了他在大學學院的數(shù)學老師奧古斯都-德-摩根，后者在1852年給威廉-漢密爾頓的信中提到了這個問題。阿瑟-凱利在1879年倫敦數(shù)學會的一次會議上提出了這個問題。同年，阿爾弗雷德-肯普（AlfredKempe）發(fā)表了一篇論文，聲稱確立了這一結(jié)果，十年來，四色問題被認為已經(jīng)解決。由于他的成就，肯普被選為皇家學會會員，后來又被選為倫敦數(shù)學學會主席。1890年，海伍德指出肯普的論點是錯誤的。然而，在那篇論文中，他證明了五色定理，說每個平面圖都可以用不超過五種顏色來著色，使用的是肯普的想法。在接下來的一個世紀里，大量的工作和理論被開發(fā)出來，以將顏色的數(shù)量減少到四種，直到四色定理最終在1976年被KennethAppel和WolfgangHaken證明。該證明回到了Heawood和Kempe的想法，并在很大程度上無視了中間的發(fā)展。四色定理的證明還值得一提的是，它是第一個重要的計算機輔助證明。1912年，喬治-大衛(wèi)-伯克霍夫引入色度多項式來研究著色問題，被圖特概括為圖特多項式，是代數(shù)圖論的重要結(jié)構(gòu)。

Kempe在1879年已經(jīng)引起了對一般的、非平面的情況的注意，在20世紀初，許多關于平面圖著色對高階表面的泛化的結(jié)果也隨之而來。1960年，ClaudeBerge提出了另一個關于圖形著色的猜想，即強完美圖形猜想，最初的動機是香農(nóng)提出的一個稱為圖形零誤差容量的信息論概念。這個猜想40年來一直沒有得到解決，直到2002年被Chudnovsky、Robertson、Seymour和Thomas確立為著名的強完美圖定理。自20世紀70年代初以來，圖形著色一直被作為一個算法問題來研究：色度數(shù)問題（見下文）是Karp在1972年提出的21個NP-complete問題之一，大約在同一時期，基于回溯和Zykov（1949）的刪除-收縮遞歸的各種指數(shù)時間算法被開發(fā)出來。圖著色的主要應用之一，即編譯器中的寄存器分配，于1981年被引入。

一個圖的邊著色只是其線圖的一個頂點著色，而一個平面圖的面著色只是其對偶的一個頂點著色。然而，非頂點著色問題往往是按原樣陳述和研究的。這一方面是教學上的原因，另一方面是因為有些問題最好以非頂點形式來研究，如邊緣著色的情況。使用顏色的慣例起源于為地圖的國家著色，其中每個面都是字面上的顏色。這被概括為對嵌入平面的圖形的面進行著色。通過平面二重性，它變成了給頂點著色，而在這種形式下，它可以推廣到所有的圖形。在數(shù)學和計算機表示中，典型的做法是使用前幾個正整數(shù)或非負整數(shù)作為顏色。一般來說，人們可以使用任何有限集作為顏色集。著色問題的性質(zhì)取決于顏色的數(shù)量，但不取決于它們是什么。圖譜著色享有許多實際應用和理論上的挑戰(zhàn)。除了經(jīng)典的問題類型外，還可以對圖形、分配顏色的方式、甚至是顏色本身設置不同的限制。它甚至以流行的數(shù)字謎題"數(shù)獨"的形式在公眾中流行起來。圖形著色仍然是一個非?；钴S的研究領域。