dreapta|miniatura|O bună colorare a nodurilor grafului Petersen cu 3 culori, numărul minim posibil. Î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.
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 , și o colorare a fețelor unui graf planar este doar o colorare a nodurilor 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 î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, 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 din 1879. În același an, 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.M. Kubale, History of graph coloring, in
În 1890, 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 și . 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 pentru a studia problemele de colorare, care au fost generalizate la de către , structuri importante din teoria algebrică a grafurilor. Kempe a atras deja atenția asupra cazului general, neplanar în 1879,, p. 2 ș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, 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 de către , , , și î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 . Una dintre cele mai importante aplicații ale colorării grafurilor, în compilatoare, a fost introdusă în 1981.
Definiție și terminologie dreapta|miniatura|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 (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
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)2(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
+Polinoame cromatice pentru anumite grafuri Triunghiul K3 Graful complet Kn Arbore cu n noduri Cn Graful Petersen
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 . 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 . 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.
O colorare neetichetată a unui grafic este o a unei colorări sub acțiunea grupului de automorfisme al grafului. Dacă am interpreta o colorare a unui graf pe noduri ca un vector în , 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
Singurele grafuri care pot fi 1-colorate sunt . Un graf complet cu n noduri are nevoie de 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
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ă:
Pentru 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 arată că fiecare graf poate fi colorat cu o culoare mai mult decât gradul maxim al unui nod,
Grafurile complete au și , și au și , astfel încât pentru aceste grafuri limita este cea mai bună posibilă. În toate celelalte cazuri, limita poate fi ușor îmbunătățită; prevede că Teorema lui Brooks: 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 o matrice simetrică reală, astfel încât ori de câte ori nu este o muchie în . Se definește , unde sunt cea mai mare și, respectiv, cea mai mică valoare proprie a lui . Se definește , cu ca mai sus. Atunci: . : Fie o matrice pozitivă semidefinită astfel încât ori de câte ori este o muchie în . Se definește ca cel mai mic k pentru care o astfel de matrice există. Atunci . : Numărul Lovász al unui graf complementar este tot o limită inferioară pentru numărul cromatic: . : Numărul cromatic fracționar al unui graf este o limită inferioară a numărului cromatic: . Aceste limite sunt ordonate după cum urmează: .
Grafuri cu număr cromatic mare Grafurile cu clici mari au un număr cromatic mare, dar reciproca nu este adevărată. este un exemplu de graf 4-cromatic fără triunghiuri, și exemplul poate fi generalizat la . Teorema lui Mycielski (, ): Există grafice fără triunghiuri cu un număr cromatic arbitrar de mare.