圖譜著色

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

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

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

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