Colorarea grafurilor

În teoria grafurilor, colorarea grafurilor este un caz special de etichetare a grafurilor; este o atribuire de etichete numite în mod tradițional „culori” elementelor unui graf, supusă anumitor constrângeri. În forma sa cea mai simplă, este o modalitate de colorat vârfurile unui graf astfel încât să nu existe două noduri adiacente cu aceeași culoare; aceasta se numește colorarea nodurilor. În mod similar, o colorare a muchiilor atribuie o culoare fiecărei muchii, astfel încât nu există două muchii adiacente de aceeași culoare, și o colorare a fețelor unui graf planar care atribuie o culoare pentru fiecare față sau regiune, astfel încât nu există două fețe care împart o graniță cu aceeași culoare.

O bună colorare a nodurilor grafului Petersen cu 3 culori, numărul minim posibil.

Colorarea nodurilor este punctul de plecare al subiectului, alte probleme de colorat putând fi transformate într-o versiune de colorare a nodurilor. De exemplu, o colorare a muchiilor unui graf este doar o colorare a nodurilor grafului muchiilor sale^⁠(d), și o colorare a fețelor unui graf planar este doar o colorare a nodurilor dualului^⁠(d) său. Cu toate acestea, adesea se enunță și se studiază ca atare și probleme de colorare a altceva decât noduri. Aceasta, parțial, pentru perspectivă, și parțial pentru că unele probleme sunt cel mai bine studiate în forma lor netransformată în colorare de noduri, ca, de exemplu, colorarea muchiilor.

Convenția de a folosi culori provine de colorarea țărilor pe o hartă politică, unde fiecare față este literalmente colorată. Aceasta a fost generalizată la colorarea fețelor unui grafic încorporat^⁠(d) în plan. Prin dualitate planară, el ajunge colorare a nodurilor, iar în această formă se generalizează la toate grafurile. În matematică și în reprezentările pe calculator, în mod tipic se utilizează primele numere întregi pozitive sau nenegative drept „culori”. În general, se poate folosi orice mulțime finită ca „mulțime de culori”. Natura problemei colorării depinde de numărul de culori, și nu de aspectul lor vizual.

Colorarea grafurilor se bucură de multe aplicații practice, precum și de provocări teoretice. Pe lângă tipurile clasice de probleme, se pot stabili și diferite limitatări asupra grafului, sau asupra felului cum se atribuie o culoare, sau chiar asupra culorii însăși. A devenit populară și pentru publicul general, sub forma popularului puzzle cu numere Sudoku. Colorarea grafurilor este încă un domeniu activ de cercetare.

Istorie

Primele rezultate despre colorarea grafurilor tratează aproape exclusiv cu grafurile planare sub forma problemei colorării hărților. În timp ce încerca să coloreze o hartă a comitatelor Angliei, Francis Guthrie^⁠(d) a postulat conjectura celor patru culori, în care remarca faptul că patru culori sunt suficiente pentru a colora o hartă, astfel încât regiunile care au frontieră comună să primească culori diferite. Fratele lui Guthrie a transmis întrebarea profesorului său de matematică, Augustus de Morgan de la University College, care a menționat-o într-o scrisoare adresată lui William Hamilton în 1852. Arthur Cayley a ridicat problema la o reuniune a London Mathematical Society^⁠(d) din 1879. În același an, Alfred Kempe^⁠(d) a publicat o lucrare care a susținut că a găsit rezultatul, și timp de un deceniu problema celor patru culori a fost considerată rezolvată. Pentru realizarea lui, Kempe a fost ales membru al Royal Society și mai târziu președinte al London Mathematical Society.

În 1890, Percy John Heawood^⁠(d) a arătat că argumentul lui Kempe era greșit. Cu toate acestea, în această lucrare, el a demonstrat teorema celor cinci culori, care spune că orice hartă în plan poate fi colorată cu nu mai mult de cinci culori, folosind ideile lui Kempe. În secolul următor, s-a depus multă muncă și s-au dezvoltat multe ipoteze pentru a reduce numărul de culori la patru, până când teorema celor patru culori a fost în cele din urmă demonstrată în 1976 de către Kenneth Appel^⁠(d) și Wolfgang Haken^⁠(d). Demonstrația s-a întors la ideile lui Heawood și Kempe și a ignorat în mare măsură evoluțiile din răstimp. Demonstrația teoremei celor patru culori este remarcabilă și pentru că este prima demonstrație matematică în mare parte asistată de calculator.

În 1912, George David Birkhoff a introdus polinoamele cromatice^⁠(d) pentru a studia problemele de colorare, care au fost generalizate la polinomul Tutte^⁠(d) de către William Tutte^⁠(d), structuri importante din teoria algebrică a grafurilor. Kempe a atras deja atenția asupra cazului general, neplanar în 1879, și au urmat în secolul al XX-lea mai multe rezultate pe generalizări ale grafurilor planare care colorează suprafețe de ordin superior.

În 1960, Claude Berge^⁠(d) a formulat o altă conjectură despre colorarea grafurilor, conjectura tare a grafurilor perfecte, motivat inițial de un concept informatic numit capacitate de eroare zero a unui graf, introdusă de Shannon. Conjectura a rămas nerezolvată timp de 40 de ani, până când a fost încetățenită ca teorema tare a grafului perfect^⁠(d) de către Chudnovsky^⁠(d), Robertson^⁠(d), Seymour^⁠(d), și Thomas^⁠(d) în 2002.

Colorarea grafurilor a fost studiată și ca problemă algoritmică încă de la începutul anilor 1970: problema numărului cromatic este una din cele 21 de probleme 21 NP-complete ale lui Karp din 1972, și în aproximativ în același timp au fost dezvoltați diverși algoritmi în timp exponențial pe baza backtrackingului și pe recurența ștergere-contracție a lui Zykov (1949). Una dintre cele mai importante aplicații ale colorării grafurilor, alocarea de registre^⁠(d) în compilatoare, a fost introdusă în 1981.

Definiție și terminologie

Acest graf poate fi 3-colorat în 12 moduri diferite.

Colorarea nodurilor

Atunci când este utilizată fără nici o calificare, colorarea unui graf este aproape întotdeauna o bună colorare a nodurilor, și anume o etichetare a nodurilor grafului cu culori, astfel încât să nu existe două noduri care împart aceeași muchie și au aceeași culoare. Întrucât un nod cu o buclă^⁠(d) (adică o muchie care duce direct înapoi la el însuși) nu poate fi colorat corespunzător, se înțelege că grafurile în acest context sunt fără bucle.

Terminologia de a folosi culori pentru etichetele nodurilor datează de la problema colorării hărților. Etichete cum ar fi roșu și albastru sunt utilizate numai atunci când numărul de culori este mic, și în mod normal, se înțelege că etichetele sunt extrase din numerele întregi {1, 2, 3, ...}.

O colorare folosind cel mult k culori se numeste o k-colorare (bună). Cel mai mic număr de culori necesare pentru a colora un graf G se numește număr cromatic, și este adesea notat χ(G). Uneori se folosește și notația γ(G), deoarece χ(G)  mai poate însemnași caracteristica Euler a unui graf. Un grafic căruia i se poate atribui o k-colorare (bună) este k-colorabil, și este k-cromatic dacă numărul său cromatic este exact k. O submulțime de noduri care au atribuite aceeași culoare se numește clasă de culoare, fiecare astfel de clasă formând o mulțime independentă. Astfel, o k-colorare este același lucru cu o partiție a mulțimii de noduri în k mulțimi independente, și deci termenii k-partit și k-colorabil sunt echivalenți.

Polinom cromatic

Toate grafurile neizomorfe de 3 noduri și polinoamele lor cromatice. Graful vid E₃ (red) admite o 1-colorare, celelalte nu. Graful verde admite 12 colorări cu 3 culori.

Polinomul cromatic numară modurile în care un graf poate fi colorat folosind nu mai mult de un anumit număr de culori. De exemplu, folosind trei culori, graful din imaginea alăturată poate fi colorat în 12 moduri. Cu doar două culori, el nu ar putea fi colorat deloc. Cu patru culori, acesta poate fi colorat în 24 + 4⋅12 = 72 moduri: folosind toate cele patru culori, sunt 4! = 24 colorări valide (fiecare atribuire de patru culori pentru orice graf cu 4 noduri este o bună colorare); și, pentru fiecare alegere de trei din cele patru culori, sunt valide 12 3-colorări. Astfel, pentru graful din exemplu, un tabel cu numărul colorări valide ar începe așa:

Culori disponibile	1	2	3	4	...
Numărul de colorări	0	0	12	72	...

Polinomul cromatic este o funcție P(G, t) care contorizează numărul de t-colorări ale lui G. După cum indică și numele, pentru un G dat, funcția este într-adevăr un polinom în t. Pentru graful luat ca exemplu, P(G, t) = t(t − 1)²(t − 2), și într-adevăr, P(G, 4) = 72.

Polinomul cromatic include cel puțin la fel de multe informații despre colorabilitatea lui G ca și numărul cromatic. Într-adevăr, χ este cel mai mic număr întreg pozitiv care nu este rădăcină a polinomului cromatic

$\chi (G)=\min\{k\,\colon \,P(G,k)>0\}.$

Polinoame cromatice pentru anumite grafuri

Triunghiul K3	$t(t-1)(t-2)$
Graful complet Kn	$t(t-1)(t-2)\cdots (t-(n-1))$
Arbore cu n noduri	$t(t-1)^{n-1}$
Ciclul⁠(d) Cn	$(t-1)^{n}+(-1)^{n}(t-1)$
Graful Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

Colorarea muchiilor

O colorare a muchiilor unui graf este o bună colorare a muchiilor, adica o atribuire de culori muchiilor astfel încât să niciun nod nu este incident la două muchii de aceeași culoare. O colorare de muchii cu k culori se numește k-colorare de muchii și este echivalentă cu problema de partiționării mulțimii muchiilor în k cuplaje^⁠(d). Cel mai mic număr de culori necesare pentru o colorare a muchiilor unui graf G este indicele cromatic, sau numărul cromatic al muchiilor, χ'(G). O colorare Tait este o 3-colorare a muchiilor unui graf cubic^⁠(d). Teorema celor patru culori este echivalentă cu afirmația că fiecare graf planar cubic fără punți admite o colorare Tait.

Colorare totală

Colorarea totală este un tip de colorare a nodurilor și muchiilor unui graf. Atunci când este utilizată fără nicio calificare, o colorare totală se presupune a fi mereu corectă, în sensul că nu există noduri adiacente, muchii adiacente, și nici perechi de muchii și extremități ale ei care au aceeași culoare. Numărul cromatic total χ"(G) al unui graf G este cel mai mic număr de culori necesare în orice colorare totală a lui G.

Colorare neetichetată

O colorare neetichetată a unui grafic este o orbită^⁠(d) a unei colorări sub acțiunea grupului de automorfisme al grafului. Dacă am interpreta o colorare a unui graf pe $d$ noduri ca un vector în $\mathbb {Z} ^{d}$, acțiunea unui automorfism este o permutare a coeficienților de colorat. Există analogii ale polinoamelor cromatice care numără colorările neetichetate ale unui graf dintr-o mulțime finită dată de culori.

Proprietăți

Limite privind numărul cromatic

Atribuirea de culori distincte pentru noduri distincte dă mereu o buna colorare, deci

$1\leq \chi (G)\leq n.\,$

Singurele grafuri care pot fi 1-colorate sunt grafurile fără muchii^⁠(d). Un graf complet $K_{n}$ cu n noduri are nevoie de $\chi (K_{n})=n$ culori. Într-o colorare optimă trebuie să fie cel puțin una din cele m muchii ale grafului între fiecare pereche de clase de culori, deci

$\chi (G)(\chi (G)-1)\leq 2m.\,$

Dacă G conține o clică de dimensiune k, atunci cel puțin k culori sunt necesare pentru colorarea acelei clici; cu alte cuvinte, numărul cromatic este cel puțin numărul de clică:

$\chi (G)\geq \omega (G).\,$

Pentru grafurile perfecte^⁠(d) această limită este strictă.

Grafurile 2-colorabile sunt exact grafurile bipartite, inclusiv arborii și pădurile. Conform teoremei celor patru culori, orice graf planar poate fi 4-colorat.

O colorare greedy^⁠(d) arată că fiecare graf poate fi colorat cu o culoare mai mult decât gradul maxim al unui nod,

$\chi (G)\leq \Delta (G)+1.\,$

Grafurile complete au $\chi (G)=n$ și $\Delta (G)=n-1$, și ciclurile impare^⁠(d) au $\chi (G)=3$ și $\Delta (G)=2$, astfel încât pentru aceste grafuri limita este cea mai bună posibilă. În toate celelalte cazuri, limita poate fi ușor îmbunătățită; teorema lui Brooks^⁠(d) prevede că

Teorema lui Brooks: $\chi (G)\leq \Delta (G)$ pentru un graf conex simplu G, dacă G nu este un graf complet sau ciclu impar.

Limitele inferioare ale numărului cromatic

De-a lungul anilor s-au descoperit mai multe limite inferioare pentru numărul cromatic:

Limita Hoffman: Fie $W$ o matrice simetrică reală, astfel încât $W_{i,j}=0$ ori de câte ori $(i,j)$ nu este o muchie în $G$. Se definește $\chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}$, unde $\lambda _{\max }(W),\lambda _{\min }(W)$ sunt cea mai mare și, respectiv, cea mai mică valoare proprie a lui $W$. Se definește $\chi _{H}(G)=\max _{W}\chi _{W}(G)$, cu $W$ ca mai sus. Atunci:

$\chi _{H}(G)\leq \chi (G)$.

Număr cromatic de vector: Fie $W$ o matrice pozitivă semidefinită astfel încât $W_{i,j}\leq -{\tfrac {1}{k-1}}$ ori de câte ori $(i,j)$ este o muchie în $G$. Se definește $\chi _{V}(G)$ ca cel mai  mic k pentru care o astfel de matrice $W$ există. Atunci

$\chi _{V}(G)\leq \chi (G)$.

Numărul Lovász^⁠(d): Numărul Lovász al unui graf complementar este tot o limită inferioară pentru numărul cromatic:

$\vartheta ({\bar {G}})\leq \chi (G)$.

Număr cromatic fracționar^⁠(d): Numărul cromatic fracționar al unui graf este o limită inferioară a numărului cromatic:

$\chi _{f}(G)\leq \chi (G)$.

Aceste limite sunt ordonate după cum urmează:

$\chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G)$.

Grafuri cu număr cromatic mare

Grafurile cu clici mari au un număr cromatic mare, dar reciproca nu este adevărată. Graful Grötzsch^⁠(d) este un exemplu de graf 4-cromatic fără triunghiuri, și exemplul poate fi generalizat la mycielskieni^⁠(d).

Teorema lui Mycielski (Alexander Zykov 1949, Jan Mycielski 1955): Există grafice fără triunghiuri cu un număr cromatic arbitrar de mare.

Din teorema lui Brooks, grafurile cu număr cromatic mare trebuie să aibă gradul maxim mare. O altă proprietate locală care duce la un număr cromatic mare este prezența unei clici mari. Dar colorabilitatea nu este în întregime un fenomen local: Un graf cu calibru mare arată local ca un arbore, pentru că toate ciclurile lui sunt lungi, dar numărul cromatic nu este obligatoriu 2:

Teoremă (Erdős): Există grafuri de calibru și număr cromatic arbitrar de mari.

Limitele indicelui cromatic

O colorare a muchiilor lui G este o colorare a nodurilor grafului muchiilor sale $L(G)$ și vice-versa. Astfel,

$\chi '(G)=\chi (L(G)).\,$

Există o relație puternică între colorabilitatea muchiilor și gradul maxim al grafului $\Delta (G)$. Deoarece toate muchiile incidente la același nod au nevoie de propria lor colorare, avem

$\chi '(G)\geq \Delta (G).\,$

Mai mult decât atât,

Teorema lui König: $\chi '(G)=\Delta (G)$ dacă G este bipartit.

În general, relația este mai puternică decât ceea ce dă teorema lui Brooks pentru colorarea nodurilor:

Teorema lui Vizing: Un graf de grad maxim $\Delta$ are numărul cromatic al muchiilor $\Delta$ sau $\Delta +1$.

Alte proprietăți

Un graf are o k-colorare dacă și numai dacă are o orientare aciclică^⁠(d) pentru care cel mai lung drum^⁠(d) are lungime cel mult k; aceasta este teorema Gallai–Hasse–Roy–Vitaver^⁠(d) (Nešetřil & Ossona de Mendez 2012).

Pentru grafuri planare, colorările nodurilor sunt, în esență, duale cu fluxurile nicăieri-zero^⁠(d).

Despre grafurile infinite, se știu mult mai puține. Următoarele sunt două dintre puținele rezultate despre colorarea grafurilor infinite:

• Dacă toate subgrafurile finite ale unui graf infinit G sunt k-colorabile, atunci și G este la fel, în ipoteza axiomei alegerii. Aceasta este teorema de Bruijn–Erdős^⁠(d) din de Bruijn & Erdős (1951).
• Dacă un graf admite o n-colorare deplină, pentru orice n ≥ n₀, admite o colorare deplină infinită (Fawcett 1978).

Probleme deschise

Numărul cromatic al planului^⁠(d), unde două puncte sunt adiacente dacă au distanță unitară, este necunoscut, deși este 4, 5, 6, sau 7. Alte probleme deschise privind numărul cromatic al grafurilor sunt conjectura Hadwiger^⁠(d) care afirmă că orice graf cu număr cromatic k are un graf complet de k noduri ca minor^⁠(d), conjectura Erdős–Faber–Lovász^⁠(d) care limitează numărul cromatic al reuniunilor de grafuri complete care au exact un nod în comun pentru fiecare pereche, și conjectura Albertson^⁠(d) că în rândul grafurilor k-cromatice, grafurile complete sunt cele cu cel mai mic număr de traversare^⁠(d).

Când Birkhoff și Lewis au introdus polinomul cromatic în abordarea teoremei celor patru culori, ei au presupus că pentru grafurile planare G, polinomul $P(G,t)$ nu are zerouri în intervalul $[4,\infty )$. Deși se știe că un astfel de polinom cromatic nu are zerouri în intervalul $[5,\infty )$ și că $P(G,4)\neq 0$, conjectura lor este încă nerezolvată. De asemenea, rămâne o problemă nerezolvată caracterizarea grafurilor care au același polinom cromatic și determinarea polinoamelor cromatice.

Algoritmi

În timp polinomial

Determinarea dacă un graf poate fi colorat cu 2 culori este echivalent cu a determina dacă graful este bipartit sau nu și, astfel, este calculabilă în timp liniar folosind căutarea în lățimea sau căutarea în adâncime. Mai general, numărul cromatic și colorarea corespunzătoare a grafurilor perfecte^⁠(d) pot fi calculate în timp polinomial folosind programarea semidefinită^⁠(d). Se cunosc formule închise pentru polinoamele cromatice pentru multe clase de grafice, cum ar fi pădurile, grafurile cordale, ciclurile, roțile și scările, astfel încât acestea pot fi evaluate în timp polinomial.

Dacă graful este planar și are o lățime de ramificare mică (sau este neplanar dar cu o descompunere cunoscută în ramuri), atunci acesta poate fi rezolvat în timp polinomial folosind programarea dinamică. În general, timpul necesar este polinomial în raport cu dimensiunea grafului, dar exponențial în raport cu lățimea de ramificare.

Algoritmi exacți

Căutara cu forța brută^⁠(d) a unei k-colorări consideră fiecare dintre cele $k^{n}$ atribuiri de k culori pentru n noduri și o verifică pe fiecare dacă este corectă. Pentru calculul numărului cromatic și al polinomului cromatic, această procedură este folosită pentru fiecare $k=1,\ldots ,n-1$, fiind nepractică pentru orice graf, mai puțin cele mai mici.

Folosind programarea dinamică^⁠(d) și o limită cu privire la numărul de mulțimi independente maximale^⁠(d), k-colorabilitatea poate fi decisă în timp și spațiu $O(2.445^{n})$. Folosind principiul includere–excludere^⁠(d) și algoritmul lui Yates^⁠(d) pentru transformata zeta rapidă, k-colorabilitatea poate fi decisă în timp $O(2^{n}n)$ pentru orice k. Se cunosc algoritmi mai rapizi pentru 3- și 4-colorabilitate, care pot fi deciși în timp $O(1.3289^{n})$ și, respectiv, $O(1.7272^{n})$

Contracția

Contracția $G/uv$ a unui graf G este graful obținut prin identificarea nodurilor u și v, și eliminarea oricăror muchii între ele. Muchiile rămase și care erau inițial incidente la u sau la v sunt acum incidente la identificarea lor. Această operațiune joacă un rol major în analiza colorării grafurilor.

Numărul cromatic care satisface relația de recurență:

$\chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}$

conform Zykov (1949), unde u și v sunt noduri neadiacente, și $G+uv$ este graful la care se adaugă muchia $uv$. Mai mulți algoritmi se bazează pe evaluarea acestei recurențe și arborele de calcul rezultat se numește uneori arbore Zykov. Timpul de funcționare se bazează pe o euristică pentru alegerea nodurilor u și v.

Polinomul cromatic satisface următoarea relație de recurență

$P(G-uv,k)=P(G/uv,k)+P(G,k)$

unde u și v sunt noduri adiacente, și $G-uv$ este graful cu muchia $uv$ eliminată. $P(G-uv,k)$ reprezintă numărul de bune colorări posibile ale grafului, unde nodurile pot avea culori la fel sau identice. Atunci bunele colorări apar din două grafuri diferite. Aceasta deoarece, dacă nodurile u și v au culori diferite, atunci s-ar putea la fel de bine să se ia în considerare un graf unde u și v sunt adiacente. Dacă u și v au aceleași culori, s-ar putea considera un graf unde u și v sunt contractate. Curiozitatea lui William Tutte^⁠(d) despre ce alte proprietăți ale grafului satisfac această recurență l-a condus la descoperirea unei generalizări bivariate a polinomului cromatic, polinomul Tutte^⁠(d).

Aceste expresii dau naștere unei proceduri recursive numită algoritmul ștergere–contracție, care stă la baza multor algoritmi pentru colorarea grafurilor. Timpul de funcționare satisface aceeași relație de recurență ca și numerele lui Fibonacci, astfel încât, în cel mai rău caz algoritmul se execută într-un timp cu un factor polinomial în funcție de $((1+{\sqrt {5}})/2)^{n+m}=O(1.6180^{n+m})$ pentru n noduri și m muchii. Analiza poate fi îmbunătățită până la un factor polinomial de numărul $t(G)$ al arborilor de acoperire^⁠(d) al grafului de intrare. În practică, strategiile branch and bound și respingerea izomorfismelor de graf se folosesc pentru a evita unele apeluri recursive. Timpul de execuție depinde de euristica folosită pentru a alege perechea de noduri.

Colorarea greedy

Două colorări greedy ale aceluiași graf utilizând ordini diferite ale nodurilor. Exemplul din dreapta se generalizează la grafurile 2-colorabile cu n noduri, unde algoritmul greedy folosește $n/2$ culori.

Algoritmul greedy consideră nodurile într-o anumită ordine $v_{1}$,…,$v_{n}$ și atribuie nodului $v_{i}$ cea mai mică culoare disponibilă care nu este utilizată de vecinii lui $v_{i}$ dintre $v_{1}$,…,$v_{i-1}$, adăugând o culoare nouă dacă este necesar. Calitatea colorării rezultate depinde de ordonarea aleasă. Exista o ordonare care duce la o colorare greedy cu numărul optim de $\chi (G)$ culori. Pe de altă parte, colorările greedy pot fi arbitrar de rele; de exemplu, graful coroană^⁠(d) cu n noduri poate fi 2-colorat, dar are o ordonare care ar duce la o colorare greedy cu $n/2$ culori.

Pentru grafurile cordale^⁠(d), și pentru cazuri speciale de grafuri cordale, cum ar fi grafurile de interval^⁠(d) și grafurile de indiferență^⁠(d), algoritmul greedy de colorare poate fi folosit pentru a găsi o colorare optimă în timp polinomial, alegând ordonarea nodurilor pentru a fi inversă pentru o ordonare de eliminare perfectă^⁠(d) pentru graf. Grafurile perfect ordonabile^⁠(d) generalizează această proprietate, dar este NP-hard găsirea unei ordonări perfecte a acestor grafuri.

Dacă nodurile sunt ordonate după gradul lor, colorarea greedy rezultată folosește cele mult ${\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}$ culori, cel mult cu una mai mult decât gradul maxim al grafului. Această euristică este uneori numită algoritmul Welsh–Powell. O altă euristică datorată lui Brélaz stabilește ordonarea dinamică pe măsură ce avansează algoritmul, alegând următorul nod ca fiind cel adiacent cu cel mai mare număr de culori diferite. Multe alte euristici de colorare a grafului se bazează similar pe colorarea greedy pentru o anumită strategie statică sau dinamică de a ordona nodurile, acești algoritmi sunt uneori numiți algoritmi de colorare secvențială.

Numărul maxim (cel mai rău) de culori care pot fi obținute prin algoritmul greedy, folosind o ordonare a nodurilor aleasă pentru a maximiza acest număr, se numește numărul Grundy al unui graf.

Algoritmi paraleli și distribuiți

În domeniul algoritmilor distribuiți^⁠(d), colorarea grafurilor este strâns legată de problema simetriei^⁠(d). Algoritmii state-of-the-art actuali sunt mai rapizi decât algoritmii determiniști pentru un grad maxim Δ suficient de mare. Cei mai rapizi algoritmi randomizați folosesc tehnica mai multor încercări^⁠(d) elaborată de Schneider et al.

Într-un graf simetric, un algoritm distribuit determinist nu poate găsi o bună colorare a nodurilor. Este nevoie de unele informații auxiliare pentru a sparge simetria. O ipoteză standard este că, inițial, fiecare nod are un identificator unic, de exemplu, din mulțimea {1, 2, ..., n}. Altfel spus, vom presupune că se dă o n-colorare. Provocarea este de a reduce numărul de culori de la n la, de exemplu, Δ + 1. Cu cât se folosesc mai multe culori, de exemplu, O(Δ) în loc de Δ + 1, cu atât este nevoie de mai puține runde de comunicație.

O versiune distribuită simplă a algoritmului greedy pentru (Δ + 1)-colorare necesită Θ(n) runde de comunicare, în cel mai rău caz − se poate să fie nevoie ca informația să fie propagată dintr-o parte a rețelei în alta.

Cel mai simplu caz de interes este un n-ciclu^⁠(d). Richard Cole și Uzi Vishkin^⁠(d) arată că există un algoritm distribuit care reduce numărul de culori de la n la O(log n) într-un singur pas de comunicare sincronă. Prin iterarea aceleiași proceduri, se poate obține o 3-colorare a unui n-ciclu în O(log* n) pași de comunicare (presupunând că avem identificatori unici pentru noduri).

Funcția log*, un logaritm iterat, este o funcție extrem de lent crescătoare, „aproape constantă”. Prin urmare, rezultatul lui Cole și Vishkin a ridicat întrebarea dacă există un algoritm distribuit în timp constant pentru 3-colorarea unui n-ciclu. Linial (1992) a arătat că acest lucru nu este posibil: orice algoritm distribuit determinist necesită Ω(log* n) pași de comunicare pentru a reduce o n-colorare la o 3-colorare într-un n-ciclu.

Tehnica lui Cole și Vishkin poate fi aplicată și în grafuri cu grad arbitrar mărginit; timpul de funcționare este de poly(Δ) + O(log* n). Tehnica a fost extinsă la grafuri disc unitate^⁠(d) de Schneider et al. Cel mai rapid algoritm determinist pentru (Δ + 1)-colorare pentru un Δ mic se datorează lui Leonid Barenboim, Michael Elkin și Fabian Kuhn. Algoritmul lui Barenboim et al. rulează în timp O(Δ) + log*(n)/2, care este optim în termeni de n deoarece factorul constant 1/2 nu poate fi îmbunătățit din cauza limitei inferioare a lui Linial. Panconesi et al. utilizează descompuneri ale rețelei pentru a calcula o Δ+1 colorare în timp $2^{O\left({\sqrt {\log n}}\right)}$.

Problema colorării muchiilor a fost studiată și în modelul distribuit. Panconesi & Rizzi (2001) ajung la o (2Δ − 1)-colorare în timp O(Δ + log* n) în acest model. Limita inferioară pentru colorarea distribuită a nodurilor dată de Linial (1992) se aplică și la problema distribuită a colorării muchiilor.

Algoritmi descentralizați

Algoritmii descentralizați sunt cei în care nu se permite schimbul de mesaje (spre deosebire de algoritmii distribuiți unde au loc schimburi locale de mesaje), și există algoritmi eficienți și descentralizați care vor colora un graf dacă există deja o bună colorare. Acestea presupun că un nod poate simți dacă vreunul dintre vecinii săi utilizează aceeași culoare ca nodul, adică dacă există un conflict local. Aceasta este o ipoteză rezonabilă în multe aplicații, de exemplu alocarea canalelor de comunicație fără fir, este rezonabil să se presupună că o stație va fi capabilă să detecteze dacă alți transmițători interferează pe același canal (de exemplu, prin măsurarea SINR). Această culegere de informații suficiente pentru a permite algoritmi bazați pe automate care învață pentru a găsi o colorare adecvată a grafului cu o probabilitate de unu, vezi de exemplu Leith (2006) și Duffy (2008).

Complexitatea calculului

Calculul colorării grafului este unul dificil. Problema de a decide dacă un anumit graf admite o k-colorare pentru un anumit k este NP-completă, cu excepția cazurilor k ∈ {0,1,2}. În special, calculul numărului cromatic este NP-hard. 3-colorarea rămâne NP-completă, chiar și pe grafuri planare 4-regulate. k-colorarea a unui graf planar este însă în P, pentru orice k>3, deoarece orice graf planar are o 4-colorare (și, prin urmare, și o k-colorare, pentru orice k≥4); a se vedea teorema celor patru culori.

Cel mai cunoscut algoritm de aproximare^⁠(d) calculează o colorare de dimensiune cel mult un factor de O(n(log n)⁻³(log log n)²) a numărului cromatic. Pentru ε > 0, aproximarea numărului cromatic în n^1−ε este NP-hard.

NP-hard este și colorarea unui graf 3-colorabil cu 4 culori și a unui graf k-colorabil cu k^{(log k ) / 25} de culori pentru o constantă k suficient de mare.

Calculul coeficienților polinomului cromatic este #P-hard^⁠(d). De fapt, chiar și calculul valorii $\chi (G,k)$ este #P-hard în orice punct rațional^⁠(d) k , cu excepția k = 1 și k = 2. Nu există nicio schemă de aproximare în timp polinomial^⁠(d) pentru evaluarea polinomului cromatic în orice punct rațional k ≥ 1.5 cu excepția k = 2, dacă  NP ≠ RP^⁠(d).

Pentru colorarea muchiilor, demonstrarea rezultatului lui Vizing oferă un algoritm care folosește cel mult Δ+1 culori. Cu toate acestea, decizia între cele două valori candidate pentru numărul cromatic al muchiilor este NP-completă. În termeni de algoritmi de aproximare, algoritmul lui Vizing arată că numărul cromatic al muchiilor poate fi aproximat într-o marjă de 4/3, și rezultatul dificultății arată că nu există niciun (4/3 − ε )-algoritm pentru orice ε > 0 decât dacă P = NP. Acestea sunt printre cele mai vechi rezultate din literatura algoritmilor de aproximare, chiar dacă nicio lucrare nu utilizează explicit această noțiune.

Aplicații

Planificarea

Colorarea nodurilor modelează o serie de probleme de planificare^⁠(d). În cea mai curată formă, unei mulțimi date de joburi trebuie să i se atribuie sloturi de timp, fiecare job necesitând un astfel de slot. Joburile pot fi programate în orice ordine, dar perechile de joburi ar putea intra în conflict în sensul că lor nu li se poate atribui același slot de timp, de exemplu pentru că ambele se bazează pe o resursă comună. Graful corespunzător conține un nod pentru fiecare job și o muchie pentru fiecare pereche contradictorie de joburi. Numărul cromatic al grafului este exact la makespanul minim, adică timpul optim pentru a termina toate joburile fără conflicte.

Detalii ale problemei planificării definesc structura grafului. De exemplu, atunci când se atribuie aeronave unor zboruri, graful de conflicte rezultat este un graf de intervale^⁠(d), astfel încât problema colorării poate fi rezolvată eficient. În alocarea lățimii de bandă^⁠(d) pentru posturile de radio, graful de conflicte rezultat este un grad disc unitate^⁠(d), astfel încât problema colorării este 3-aproximabilă.

Alocarea registrelor

Un compilator este un program de calculator care traduce un limbaj de calculator^⁠(d) în altul. Pentru a îmbunătăți timpul de execuție al codului rezultat, una dintre tehnicile de optimizare a compilatoarelor este alocarea registrelor, unde cele mai frecvent utilizate valori ale programului compilat sunt stocate în registrele procesorului, cel mai rapid spațiu de memorare. În mod ideal, valorilor li se atribuie registre așa încât ele să poată sta în registrele atunci când sunt utilizate.

Abordarea de manual a acestei probleme este de a modela problema ca pe o colorare a grafului. Compilatorul construiește astfel un graf de interferențe, unde nodurile sunt variabile și o muchie conectează două noduri dacă acestea sunt necesare în același timp. Dacă graful poate fi colorat cu k culori, atunci orice set de variabile necesare în același timp pot fi stocate în cel mult k registre.

Alte aplicații

Problema colorării grafurilor apare în mai multe domenii practice, cum ar fi potrivirea șabloanelor, planificarea evenimentelor sportive, proiectarea locurilor unor persoane la evenimente, orarele de examen, programarea taxiurilor, și rezolvarea puzzle-urilor Sudoku.

Alte colorări

Teoria lui Ramsey

O clasă importantă de probleme de colorare improprii este studiată în teoria lui Ramsey, unde muchiilor grafului i se atribuie culori, și nu există nicio restricție cu privire la culorile de muchiilor incidente. Un exemplu simplu este teorema prieteniei, care prevede că în orice colorare a muchiilor lui $K_{6}$, graful complet cu șase noduri, va exista un triunghi monocromatic; de multe ori ilustrată prin a spune că orice grup de șase oameni, fie are trei persoane care nu se cunosc, fie are trei cunoștințe comune. Teoria lui Ramsey se ocupă cu generalizări ale acestei idei pentru a căuta regularitate în dezordine, găsind condiții generale pentru existența subgrafurilor monocromatice cu o structură dată.

Bibliografie

• Barenboim, L.; Elkin, M. (2009), „Distributed (Δ + 1)-coloring in linear (in Δ) time”, Proceedings of the 41st Symposium on Theory of Computing^⁠(d), pp. 111–120, doi:10.1145/1536414.1536432, ISBN 978-1-60558-506-2 
• Panconesi, A.; Srinivasan, A. (1996), „On the complexity of distributed network decomposition”, Journal of Algorithms, 20 
• Schneider, J. (2010), „A new technique for distributed symmetry breaking” (PDF), Proceedings of the Principles of Distributed Computing^⁠(d), arhivat din original (PDF) la 30 iulie 2013, accesat în 20 iunie 2017 
• Schneider, J. (2008), „A log-star distributed maximal independent set algorithm for growth-bounded graphs” (PDF), Proceedings of the Principles of Distributed Computing^⁠(d), arhivat din original (PDF) la 30 iulie 2013, accesat în 20 iunie 2017 
• Beigel, R.; Eppstein, D. (2005), „3-coloring in time O(1.3289ⁿ)”, Elsevier, 54 (2)): 168–204, doi:10.1016/j.jalgor.2004.06.008 
• Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), „Set partitioning via inclusion–exclusion”, SIAM Journal on Computing^⁠(d), 39 (2): 546–563, doi:10.1137/070683933 
• Brélaz, D. (1979), „New methods to color the vertices of a graph”, Communications of the ACM^⁠(d), 22 (4): 251–256, doi:10.1145/359094.359101 
• Brooks, R. L.; Tutte, W. T. (1941), „On colouring the nodes of a network”, Mathematical Proceedings of the Cambridge Philosophical Society^⁠(d), 37 (2): 194–197, doi:10.1017/S030500410002168X 
• de Bruijn, N. G.; Erdős, P. (1951), „A colour problem for infinite graphs and a problem in the theory of relations” (PDF), Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373  (= Indag. Math. 13)
• Byskov, J.M. (2004), „Enumerating maximal independent sets with applications to graph colouring”, Operations Research Letters, 32 (6): 547–556, doi:10.1016/j.orl.2004.03.002 

• Chaitin, G. J. (1982), „Register allocation & spilling via graph colouring”, Proc. 1982 Programming Language Design and Implementation^⁠(d), pp. 98–105, doi:10.1145/800230.806984, ISBN 0-89791-074-5 
• Cole, R.; Vishkin, U. (1986), „Deterministic coin tossing with applications to optimal parallel list ranking”, Information and Computation^⁠(d), 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7 
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990), Introduction to Algorithms^⁠(d) (ed. 1st), The MIT Press 
• Dailey, D. P. (1980), „Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete”, Discrete Mathematics^⁠(d), 30 (3): 289–293, doi:10.1016/0012-365X(80)90236-8 
• Duffy, K.; O'Connell, N.; Sapozhnikov, A. (2008), „Complexity analysis of a decentralised graph colouring algorithm” (PDF), Information Processing Letters, 107 (2): 60–63, doi:10.1016/j.ipl.2008.01.002 
• Fawcett, B. W. (1978), „On infinite full colourings of graphs”, Can. J. Math.^⁠(d), 30: 455–457, doi:10.4153/cjm-1978-039-8 

• Fomin, F.V.; Gaspers, S.; Saurabh, S. (2007), „Improved Exact Algorithms for Counting 3- and 4-Colorings”, Proc. 13th Annual International Conference, COCOON 2007, Lecture Notes in Computer Science^⁠(d), 4598, Springer, pp. 65–74, doi:10.1007/978-3-540-73545-8_9, ISBN 978-3-540-73544-1 
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability^⁠(d), W.H. Freeman, ISBN 0-7167-1045-5 
• Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), „Some simplified NP-complete problems”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47–63, doi:10.1145/800119.803884 
• Goldberg, L. A.; Jerrum, M. (iulie 2008), „Inapproximability of the Tutte polynomial”, Information and Computation^⁠(d), 206 (7): 908–929, doi:10.1016/j.ic.2008.04.003 
• Goldberg, A. V.; Plotkin, S. A.; Shannon, G. E. (1988), „Parallel symmetry-breaking in sparse graphs”, SIAM Journal on Discrete Mathematics^⁠(d), 1 (4): 434–446, doi:10.1137/0401044 
• Guruswami, V.; Khanna, S. (2000), „On the hardness of 4-coloring a 3-colorable graph”, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pp. 188–197, doi:10.1109/CCC.2000.856749, ISBN 0-7695-0674-7 
• Halldórsson, M. M. (1993), „A still better performance guarantee for approximate graph coloring”, Information Processing Letters, 45: 19–23, doi:10.1016/0020-0190(93)90246-6 
• Holyer, I. (1981), „The NP-completeness of edge-coloring”, SIAM Journal on Computing^⁠(d), 10 (4): 718–720, doi:10.1137/0210055 
• Crescenzi, P.; Kann, V. (decembrie 1998), „How to find the best approximation results — a follow-up to Garey and Johnson”, SIGACT^⁠(d), 29 (4): 90, doi:10.1145/306198.306210 
• Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), „On the computational complexity of the Jones and Tutte polynomials”, Mathematical Proceedings of the Cambridge Philosophical Society^⁠(d), 108: 35–53, doi:10.1017/S0305004100068936 
• Jensen, T. R.; Toft, B. (1995), Graph Coloring Problems, Wiley-Interscience, New York, ISBN 0-471-02865-7 
• Khot, S. (2001), „Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring”, Proc. 42nd Annual Symposium on Foundations of Computer Science^⁠(d), pp. 600–609, doi:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3 
• Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4 
• Kuhn, F. (2009), „Weak graph colorings: distributed algorithms and applications”, Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures^⁠(d), pp. 138–144, doi:10.1145/1583991.1584032, ISBN 978-1-60558-606-9 
• Lawler, E.L. (1976), „A note on the complexity of the chromatic number problem”, Information Processing Letters^⁠(d), 5 (3): 66–67, doi:10.1016/0020-0190(76)90065-X 
• Leith, D.J.; Clifford, P. (2006), „A Self-Managed Distributed Channel Selection Algorithm for WLAN”, Proc. RAWNET 2006, Boston, MA (PDF), accesat în 3 martie 2016 
• Linial, N. (1992), „Locality in distributed graph algorithms”, SIAM Journal on Computing^⁠(d), 21 (1): 193–201, doi:10.1137/0221015 
• van Lint, J. H.; Wilson, R. M. (2001), A Course in Combinatorics (ed. 2nd), Cambridge University Press, ISBN 0-521-80340-3 
• Marx, Dániel (2004), „Graph colouring problems and their applications in scheduling”, Periodica Polytechnica, Electrical Engineering, 48 (1–2), pp. 11–16, CiteSeerX 10.1.1.95.4268  
• Mycielski, J. (1955), „Sur le coloriage des graphes” (PDF), Colloq. Math., 3: 161–162 .
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), „Theorem 3.13”, Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058 .
• Panconesi, Alessandro; Rizzi, Romeo (2001), „Some simple distributed algorithms for sparse networks”, Distributed Computing, Berlin, New York: Springer Science+Business Media, 14 (2): 97–100, doi:10.1007/PL00008932, ISSN 0178-2770 
• Sekine, K.; Imai, H.; Tani, S. (1995), „Computing the Tutte polynomial of a graph of moderate size”, Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995), Lecture Notes in Computer Science^⁠(d), 1004, Springer, pp. 224–233, doi:10.1007/BFb0015427, ISBN 3-540-60573-8 
• Welsh, D. J. A.; Powell, M. B. (1967), „An upper bound for the chromatic number of a graph and its application to timetabling problems”, The Computer Journal, 10 (1): 85–86, doi:10.1093/comjnl/10.1.85 
• West, D. B. (1996), Introduction to Graph Theory, Prentice-Hall, ISBN 0-13-227828-6 
• Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall 
• Zuckerman, D. (2007), „Linear degree extractors and the inapproximability of Max Clique and Chromatic Number”, Theory of Computing^⁠(d), 3: 103–128, doi:10.4086/toc.2007.v003a006 
• Zykov, A. A. (1949), „О некоторых свойствах линейных комплексов (On some properties of linear complexes)”, Math. Sbornik. (în Russian), 24(66) (2): 163–188 Mentenanță CS1: Limbă nerecunoscută (link)
• Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, John Wiley & Sons, ISBN 9780471028659 

Legături externe

• Pagină de colorare a grafurilor Arhivat în 22 septembrie 2016, la Wayback Machine. de Joseph Culberson (programe de colorare a grafurilor)
• High-Performance Graph Colouring Algorithms Suită de 8 algoritmi diferiți (implementați în C++) de Rhyd Lewis
• CoLoRaTiOn de Jim Andrews și Mike Fellows este un puzzle de colorare a grafurilor
• Legături către coduri sursă de colorarea grafurilor Arhivat în 4 iulie 2008, la Wayback Machine.
• Cod pentru calculul eficient al polinoamelor Tutte, cromatic și de flux Arhivat în 16 aprilie 2008, la Wayback Machine. de Gary Haggard, David J. Pearce și Gordon Royle
• O aplicație web de colorare a grafurilor Arhivat în 22 iunie 2012, la Wayback Machine. de Jose Antonio Martin H.