Grafice de colorat

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 iunie 2019; verificările necesită 15 modificări .

Colorarea graficelor este o construcție teoretică a graficului , un caz special de marcare a graficelor . La colorare, elementelor grafice li se atribuie etichete cu anumite restricții; aceste etichete sunt denumite în mod tradițional „culori”. În cel mai simplu caz, un astfel de mod de colorare a vârfurilor unui graf , în care oricare două vârfuri adiacente corespund unor culori diferite, se numește colorare a vârfurilor . În mod similar , colorarea marginilor atribuie o culoare fiecărei margini, astfel încât oricare două margini adiacente să aibă culori diferite [1] . În cele din urmă, colorarea regiunii a unui grafic plan atribuie o culoare fiecărei regiuni, astfel încât fiecare două regiuni care împărtășesc o limită nu pot avea aceeași culoare.

Colorarea vârfurilor este principala problemă a colorării graficelor, toate celelalte probleme din această zonă pot fi reduse la ea. De exemplu, colorarea muchiilor unui graf este colorarea vârfurilor graficului său de linii , iar colorarea regiunilor unui graf plan este colorarea vârfurilor graficului său dual [1] . Cu toate acestea, alte probleme de colorare a graficelor sunt adesea puse și rezolvate în setarea originală. Motivul pentru aceasta este parțial pentru că oferă o idee mai bună despre ceea ce se întâmplă și este mai revelator și, parțial, pentru că unele probleme sunt mai convenabile de rezolvat în acest fel (de exemplu, colorarea marginilor).

Colorarea graficelor își găsește aplicație în multe domenii practice și nu numai în probleme teoretice. În afară de tipurile clasice de probleme, mai multe restricții pot fi puse și asupra graficului, asupra modului în care sunt atribuite culorile sau asupra culorilor în sine. Această metodă este folosită în popularul puzzle Sudoku , de exemplu . Există încă cercetări active în acest domeniu.

Istorie

Primele rezultate au fost obținute pentru graficele plane în problema colorării hărții. În încercarea de a colora o hartă a comitatelor Angliei, Francis Guthrie a formulat problema celor patru culori , observând că patru culori sunt suficiente pentru a colora harta, astfel încât oricare două regiuni adiacente să aibă culori diferite. Fratele său a adresat întrebarea profesorului său de matematică, Augustus de Morgan , care a menționat-o în scrisoarea sa către William Hamilton din 1852. Arthur Cayley a ridicat această problemă la o reuniune a Societății de Matematică din Londra în 1878. În același an, Tate a propus prima soluție la această problemă. El a redus colorarea vârfurilor grafului original la colorarea muchiilor grafului dual și a sugerat că această problemă are întotdeauna o soluție [2] . În 1880, Alfred Kempe a publicat un articol în care susținea că a reușit să stabilească rezultatul, iar timp de un deceniu problema celor patru culori a fost considerată rezolvată. Pentru această realizare, Kempe a fost ales Fellow al Societății Regale din Londra și mai târziu Președinte al Societății de Matematică din Londra [3] .

În 1890 , Heawood a găsit o eroare în dovada lui Kempe. În același articol, el a demonstrat teorema celor cinci culori , arătând că orice hartă plată poate fi colorată cu cel mult cinci culori. În acest sens, s-a bazat pe ideile lui Kempe. În secolul următor, un număr mare de teorii au fost dezvoltate în încercarea de a reduce numărul minim de culori. Teorema celor patru culori a fost în cele din urmă demonstrată în 1977 de oamenii de știință Kenneth Appel și Wolfgang Haken folosind enumerarea computerizată. Ideea dovezii s-a bazat în mare măsură pe ideile lui Heawood și Kempe și a ignorat majoritatea studiilor intermediare [4] . Dovada teoremei celor patru culori este una dintre primele dovezi în care a fost folosit un calculator.

În 1912, George David Birkhoff a propus utilizarea polinomului cromatic , o parte importantă a teoriei grafurilor algebrice, pentru a studia problemele de colorare . Polinomul cromatic a fost ulterior generalizat de William Tutt ( polinomul lui Tutt ). Kempe în 1879 a atras deja atenția asupra cazului general când graficul nu era plan [5] . Multe rezultate ale generalizărilor graficelor plane de colorare pe suprafețe de ordin superior au apărut la începutul secolului al XX-lea.

În 1960, Claude Burge a formulat conjectura grafului perfect , motivată de o noțiune din teoria informației , și anume eroarea zero a capacității grafului [6] introdusă de Shannon . Afirmația a rămas neconfirmată timp de 40 de ani, până când a fost dovedită drept celebra teoremă strictă a grafului perfect de către matematicienii Chudnovskaya , Robertson , Seymour și Thomas în 2002.

Colorarea graficelor ca problemă algoritmică a fost studiată încă din anii 1970: determinarea numărului cromatic este una dintre cele 21 de probleme NP-complete ale lui Karp (1972). Și cam în același timp, au fost dezvoltați diverși algoritmi bazați pe backtracking și ștergerea și contracția recursivă a lui Zykov [7] . Din 1981, colorarea graficelor a fost folosită pentru alocarea de registre în compilatoare [8] .

Definiție și terminologie

Colorarea vârfurilor

Când oamenii vorbesc despre colorarea graficelor, aproape întotdeauna se referă la colorarea vârfurilor lor, adică atribuirea etichetelor de culoare nodurilor graficului, astfel încât oricare două vârfuri care au o margine comună să aibă culori diferite. Deoarece graficele în buclă nu pot fi colorate în acest fel, acestea sunt excluse.

Terminologia în care etichetele sunt numite culori provine din colorarea hărților politice. Etichetele precum roșu sau albastru sunt folosite numai atunci când numărul de culori este mic, dar se presupune că etichetele sunt de obicei numere întregi . $\{1,2,3,...\}$

Colorarea cu culori se numește -colorare . Cel mai mic număr de culori necesare pentru a colora un grafic se numește numărul său cromatic și este adesea scris ca . Folosit uneori , deoarece denotă caracteristica lui Euler . Un subset de vârfuri evidențiat într-o singură culoare se numește clasă de culoare , fiecare astfel de clasă formând un set independent . Astfel, -colorarea este aceeași cu împărțirea vârfurilor în mulțimi independente [1] . $k$ $k$ $G$ $\chi (G)$ $\gamma (G)$ $\chi (G)$ $k$ $k$

Număr cromatic în ceea ce privește distanța Gromov-Hausdorff

Fie un graf arbitrar cu set de vârfuri . Fixăm două numere reale pozitive și îl vom considera ca un spațiu metric în care distanțele dintre vârfurile adiacente sunt egale cu , iar toate celelalte distanțe diferite de zero sunt egale cu . Se notează prin spațiul metric format din puncte separate între ele printr-o distanță . În cele din urmă, pentru oricare două spații metrice și , notăm distanța Gromov-Hausdorff dintre și . Apoi următorul rezultat este valabil. $G$ $V$ $a<b\leq 2a$ $V$ $b$ $A$ $a\Delta _{m)$ $m$ $A$ $X$ $Y$ $d_{GH}(X,Y)$ $X$ $Y$

Teorema (A.O. Ivanov, A.A. Tuzhilin) [9] : Fie cel mai mare număr natural pentru care (dacă astfel de numere naturale nu există, atunci setăm ). Apoi .

m

d_{GH}(V,a\Delta _{m})=b

m=0

\chi (G)=m+1

Cometariu.

Numărul cromatic este , dacă și numai dacă graficul nu conține muchii. În acest caz, egalitatea nu este valabilă pentru niciun , prin urmare, prin convenție, , ceea ce duce la egalitatea corectă . $\chi (G)$ $unu$ $G$ $d_{GH}(V,a\Delta _{m})=b$ $m$ $m=0$ $\chi (G)=0+1=1$

Prin definiție, nu depășește numărul de elemente ale mulțimii . Pe de altă parte, este ușor să arătăm că pentru fiecare , prin urmare, și, prin urmare, . $\chi (G)$ $n$ $V$ $d_{GH}(V,a\Delta _{p})\leq \max\{a,\,ba\}<b$ $p\geq n$ $m<n$ $\chi (G)=m+1\leq n$

Polinom cromatic

Un polinom cromatic este o funcție care numără numărul de t - colorări ale unui grafic . Din nume rezultă că pentru dată această funcție este un polinom în funcție de t . $P(G,t)$ $G$ $G$

Acest fapt a fost descoperit de Birkhoff și Lewis în timp ce încercau să demonstreze conjectura în patru culori [10] .

De exemplu, graficul din imaginea din dreapta poate fi colorat în 12 moduri folosind 3 culori. În principiu, nu poate fi vopsit cu două culori. Folosind 4 culori, obținem 24+4*12 = 72 de opțiuni de colorare: când folosiți toate cele 4 culori, sunt 4! = 24 de moduri corecte ( fiecare atribuire de 4 culori pentru orice grafic de 4 vârfuri este corectă); și pentru fiecare 3 culori din cele 4 există 12 moduri de a colora. Apoi, pentru graficul din exemplu, tabelul numerelor de colorații corecte va începe astfel:

Numar disponibil de culori	unu	2	3	patru	…
Numărul de moduri de a colora	0	0	12	72	…

Pentru graficul din exemplu și, desigur, . $P(G,t)=t(t-1)^{2}(t-2)$ $P(G,4)=72$

Un polinom cromatic conține cel puțin la fel de multe informații de colorizare ca un număr cromatic. Într-adevăr, este cel mai mic număr întreg pozitiv care nu este o rădăcină a unui polinom cromatic. $G$ $\chi$

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

Polinoame cromatice pentru unele grafice

Triunghiular $K_{3}$	$t(t-1)(t-2)$
Graficul complet $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
copac cu coaste $n$	$t(t-1)^{{n}}$
Ciclu $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Contele de Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Colorarea marginilor

O colorare a muchiei unui grafic înseamnă alocarea de culori muchiilor în așa fel încât să nu aparțină două muchii de aceeași culoare aceluiași vârf. Această problemă este echivalentă cu împărțirea setului de fețe în seturi de fețe independente . Cel mai mic număr de culori necesare pentru colorarea muchiei unui grafic este indicele cromatic al acestuia , sau numărul cromatic al muchiei . $G$ $\chi '(G)$

Colorare totală

Colorarea totală este un tip de colorare a vârfurilor și a muchiilor unui grafic. Prin aceasta se înțelege o astfel de atribuire a culorilor încât nici vârfurile învecinate, nici muchiile adiacente, nici vârfurile și muchiile care le leagă nu au aceeași culoare. Numărul cromatic total al unui grafic este cel mai mic număr de culori necesare pentru orice colorare completă. $\chi ''(G)$ $G$

Proprietăți

Proprietățile polinomului cromatic

Dacă este un grafic gol [11] , $G$

P(G,t)=1

Dacă graficul este uniunea subgrafelor disjunse și [11] , $G$ $H$ $K$

P(G,t)=P(H,t)P(K,t)

Dacă există o buclă în [11] , $G$

P(G,t)=0

Restricții privind numărul cromatic

Atribuirea de culori diferite tuturor vârfurilor oferă întotdeauna colorarea corectă, deci

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

Singurul tip de grafice care poate fi colorat într-o singură culoare sunt graficele zero .
Un grafic complet format din vârfuri necesită culori. $K_n$ $n$ $\chi (K_{n})=n$
Într-o colorare optimă, trebuie să existe cel puțin o margine a graficului între fiecare două clase de culoare, deci [12] $m$

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

Dacă este uniunea subgrafelor disjunse și , atunci $G$ $H$ $K$

\chi (G)=max\{\chi (H),\chi (K)\}

Dacă conține clicuri de dimensiunea k , atunci sunt necesare cel puțin k culori pentru a colora această clică, cu alte cuvinte, numărul cromatic este mai mare sau egal cu numărul clicei : $G$

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

Pentru graficele cu intervale, această restricție este exactă.

Prin teorema celor patru culori, orice grafic plan poate fi colorat cu patru culori.
Graficele cu două culori sunt grafice bipartite , inclusiv arbori .

Un grafic este bipartit dacă și numai dacă nu conține cicluri de lungime impară [11] .

G

Colorarea greedy arată că orice grafic poate fi colorat folosind o culoare în plus decât gradul maxim de vârf [12] .

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

Graficele complete au și , graficele ciclului au și , deci pentru ei această constrângere este cea mai bună, în toate celelalte cazuri, constrângerea poate fi îmbunătățită: teorema lui Brooks [13] afirmă că $\chi (G)=n$ $\Delta(G)=n-1$ $\chi (G)=3$ $\Delta(G)=2$

\chi (G)\leq \Delta (G)

pentru un grafic simplu, conectat, dacă nu este nici un grafic complet, nici un grafic de ciclu.

G

G

Grafice cu număr cromatic mare

Graficele cu clicuri mari au numere cromatice mari, dar inversul nu este întotdeauna adevărat. Graficul Grötzsch este un exemplu de grafic cu 4 culori fără triunghi, iar acest exemplu poate fi generalizat la graficul Mycielski .

Teorema lui Mychelski (Alexander Zykov 1949, Jan Mychelski 1955): Există grafice fără triunghiuri cu numere cromatice arbitrar mari.

Din teorema lui Brooks, graficele cu număr cromatic mare trebuie să aibă un grad maxim de vârf ridicat. O altă condiție locală datorită căreia numărul cromatic poate fi mare este prezența unei cliche mari. Dar colorabilitatea graficului depinde nu numai de condițiile locale: un grafic cu circumferință mare local arată ca un copac, deci toate ciclurile sunt lungi, dar numărul său cromatic nu este egal cu 2:

Teorema Erdős : Există grafice cu circumferință și număr cromatic arbitrar mare [12] .

Restricții privind indexul cromatic

O colorare a muchiei este o colorare a vârfurilor graficului său de linii . Acesta este $G$ $L(G)$

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

Mai mult [14] ,

Teorema lui König : , if este bipartită.

\chi '(G)=\Delta (G)

G

În general, conexiunea este mult mai puternică decât dă teorema lui Brooks pentru colorarea vârfurilor [14] :

Teorema lui Vizing: Un grafic cu un grad maxim de vârf are un număr cromatic de muchie sau .

\Delta

\Delta

\Delta +1

Alte proprietăți

Un grafic este k - cromatic dacă și numai dacă are o orientare aciclică , pentru care lungimea drumului cel mai lung este k . Acest lucru a fost demonstrat în teorema Gallai-Hasse-Roy-Vitaver [15] .
Pentru graficele plane, colorarea vârfurilor este echivalentă cu curgerea nulă nicăieri .
Se știe mult mai puțin despre graficele infinite. Mai jos sunt două rezultate pentru colorarea graficelor infinite.

Dacă toate subgrafele finite ale unui graf infinit sunt k -cromatice, atunci la fel este k - cromatic (demonstrat în ipoteza axiomei alegerii ). Aceasta este formularea teoremei lui de Bruijn-Erdős [16] . $G$ $G$
Dacă un grafic admite o n -colorare completă pentru orice , atunci admite o colorare completă infinită [17] . $n\geqslant n_{0}$

Întrebări deschise

Numărul cromatic al unui plan în care două puncte sunt adiacente dacă există o unitate de distanță între ele este necunoscut. Poate fi 5, 6 sau 7. Alte întrebări deschise despre numărul cromatic de grafice includ conjectura Hadwiger , care afirmă că orice graf cu număr cromatic k are un grafic complet de k vârfuri ca minor , Erdős-Faber-Lovas conjectura , care limitează numărul cromatic de grafuri complete care au exact un vârf comun pentru fiecare pereche de grafuri, și conjectura lui Albertson că printre grafurile k - cromatice, cele cu cel mai mic număr de intersecții sunt complete .

Când Birkov și Lewis au introdus polinomul cromatic în încercarea lor de a rezolva teorema celor patru culori, ei au susținut că pentru graficele plane, polinomul nu are zerouri în domeniul . Deși se știe că un astfel de polinom cromatic nu are zerouri în domeniul , și că , afirmația lor rămâne nedovedită. De asemenea, rămâne o întrebare deschisă cum să distingem graficele cu același polinom cromatic și cum să determinați că un polinom este cromatic. $G$ $P(G,t)$ $[4,\infty )$ $[5,\infty )$ $P(G,4)\neq 0$

Algoritmi de colorare

Algoritmi polinomiali

Pentru un grafic bipartit , problema de colorare este calculată în timp liniar folosind căutarea pe lățimea întâi . În cazul graficelor perfecte, numărul cromatic și colorarea corespunzătoare pot fi găsite în timp polinomial folosind programarea semidefinită . Formulele exacte pentru găsirea numărului cromatic sunt cunoscute pentru multe clase de grafice (păduri, cicluri , roți , grafice cordale ) și pot fi calculate și în timp polinomial.

Algoritmi exacti

Algoritmul de căutare exhaustiv pentru cazul k-colorării ia în considerare toate combinațiile de aranjamente de culori într-un grafic cu n vârfuri și le verifică pentru corectitudine. Pentru a calcula numărul cromatic și polinomul cromatic, acest algoritm ia în considerare fiecare k de la 1 la n. În practică, un astfel de algoritm poate fi aplicat numai graficelor mici. $k^{n}$

Folosind programarea dinamică și estimând dimensiunea celei mai mari mulțimi independente , posibilitatea de k-colorare într-un grafic poate fi rezolvată în timp [18] . Sunt cunoscuți algoritmi mai rapizi pentru 3 și 4 colorări care rulează în timp [19] și , respectiv, [20] . $O(2.445^{n})$ $O(1,3289^{n})$ $O(1,7272^{n})$

Contracție

Contracția vârfurilor este o operație prin care se realizează un grafic dintr-un grafic prin identificarea vârfurilor și , eliminând muchiile care le leagă și înlocuindu-le cu un singur vârf , unde muchiile incidente la vârfuri și sunt redirecționate . Această operație joacă un rol important în analiza colorării graficelor. $G$ $g/uv$ $u$ $v$ $w$ $u$ $v$

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

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

unde și sunt vârfuri neadiacente, este un grafic cu o muchie adăugată . Unii algoritmi se bazează pe acest raport, producând ca rezultat un arbore, numit uneori arbore Zykov. Timpul de execuție depinde de metoda de selecție a vârfurilor și . $u$ $v$ $G+uv$ $UV$ $u$ $v$

Polinomul cromatic satisface relatia de recurenta

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

unde și sunt vârfuri adiacente, este un grafic cu muchia eliminată . reprezintă numărul de colorări corecte posibile ale graficului, când vârfurile și pot avea culori identice sau diferite. Dacă și au culori diferite, atunci putem considera un grafic unde și sunt adiacente. Dacă și au aceleași culori, putem considera un grafic în care și sunt îmbinate. $u$ $v$ $G-uv$ $UV$ $P(G-uv,t)$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$

Expresiile prezentate mai sus conduc la o procedură recursivă numită algoritmul de eliminare și contractare , care a stat la baza multor algoritmi de colorare a graficelor. Timpul de rulare satisface aceeași relație de recurență ca și numerele Fibonacci , așa că în cel mai rău caz, algoritmul va rula în timp pentru n vârfuri și m muchii [21] . În practică , metoda ramurilor și legate și respingerea graficelor izomorfe evită unele apeluri recursive, timpul de rulare depinde de metoda de selectare a unei perechi de vârfuri. $((1+{\sqrt 5})/2)^{{n+m}}=O(1,6180^{{n+m}})$

Colorat lacom

Algoritmul greedy sortează vârfurile ,…, și atribuie secvenţial vârfului cea mai mică culoare disponibilă care nu a fost folosită pentru a colora vecinii dintre ,…, , sau adaugă una nouă. Calitatea colorării rezultate depinde de ordinea aleasă. Există întotdeauna o ordine care aduce algoritmul lacom la numărul optim de culori. Pe de altă parte, un algoritm lacom poate fi arbitrar rău; de exemplu, o coroană cu n vârfuri poate fi colorată cu 2 culori, dar există o ordine a vârfurilor care are ca rezultat o colorare lacomă a culorilor. $v_{1}$ $v_{n}$ $v_{i}$ $v_{i}$ $v_{1}$ $v_{{i-1}}$ $\chi (G)$ $n/2$

Pentru un grafic de acorduri și pentru cazurile sale speciale (cum ar fi un grafic de intervale ), algoritmul de colorare greedy poate fi utilizat pentru a găsi colorarea optimă în timp polinomial, alegând ordinea vârfurilor să fie inversă ordinii de eliminare perfectă . Acest algoritm poate fi aplicat la o clasă mai largă de grafice (grafice complet ordonabile ), dar găsirea unei astfel de ordine pentru astfel de grafice este o problemă dificilă.

Dacă vârfurile sunt ordonate în funcție de gradele lor, algoritmul de colorare greedy folosește cel mult culori, care este cu cel mult 1 mai mult decât (aici , gradul vârfului ). Acest algoritm euristic este uneori numit algoritmul Welsh-Powell [22] . Un alt algoritm stabilește ordinea în mod dinamic, alegând următorul vârf din cel cu cele mai multe vârfuri adiacente de diferite culori. Mulți alți algoritmi de colorare a graficelor se bazează pe colorarea lacomă și folosesc strategii statice sau dinamice de ordonare a vârfurilor. $max_{i}min\{d(v_{i})+1,i\}$ $\Delta$ $d(v_{i})$ $v_{i}$

Algoritmi paraleli și distribuiți

O problemă similară apare în domeniul algoritmilor distribuiți. Să presupunem că vârfurile graficului sunt computere care pot comunica între ele dacă sunt conectate printr-o muchie. Scopul este ca fiecare computer să aleagă o „culoare” pentru sine, astfel încât computerele vecine să aleagă culori diferite. Această problemă este strâns legată de problema ruperii simetriei . Cei mai dezvoltați algoritmi probabilistici sunt mai rapidi decât algoritmii determiniști pentru grafice cu un grad maxim suficient de mare de vârfuri . Cei mai rapizi algoritmi probabilistici folosesc tehnica încercărilor multiple [23] . $\Delta$

În graficele simetrice, algoritmii distribuiți determiniști nu pot găsi colorarea optimă a vârfurilor. Sunt necesare mai multe informații pentru a evita simetria. Se face o presupunere standard că inițial fiecare vârf are un identificator unic, de exemplu, din mulțimea . Cu alte cuvinte, se presupune că ni se dă o n -colorare. Sarcina este de a reduce numărul de culori de la n la, de exemplu, . Cu cât sunt folosite mai multe culori (de exemplu, în loc de ), cu atât vor fi necesare mai puține schimburi de mesaje [23] . $\{1,2,...,N\}$ $(\Delta+1)$ $O(\Delta )$ $(\Delta+1)$

O versiune simplă a algoritmului lacom distribuit pentru -colorare necesită runde de comunicare în cel mai rău caz - este posibil ca informațiile să treacă de la un capăt la altul al rețelei. $(\Delta+1)$ $\Theta(n)$

Cel mai simplu caz interesant este ciclul n . Richard Cole și Uzi Vishkin [24] au arătat că există un algoritm distribuit care reduce numărul de culori de la n la , folosind doar un mesaj de vecinătate. Repetând aceeași procedură, se poate obține o colorare n -ciclu 3 în runde de conexiune (cu condiția să fie furnizați identificatori unici de nod). $O(log(n))$ $O(log^{*}(n))$

Funcția , logaritm iterat , este o funcție cu creștere extrem de lentă, „aproape o constantă”. Prin urmare, rezultatele lui Cole și Vishkin ridică întrebarea dacă există un algoritm de colorare n-ciclu distribuit, care rulează în timp constant. Nathan Linial a arătat că acest lucru este imposibil: orice algoritm distribuit determinist necesită runde de comunicare pentru a reduce un N -colorare la 3-colorări într-un n-ciclu [25] . $jurnal^{*}$ $\Omega (log^{*}(n))$

Tehnica lui Cole și Vishkin poate fi aplicată și unui graf arbitrar cu un grad mărginit de vârfuri, caz în care timpul de rulare este [26] . Această metodă a fost generalizată la graficul cerc unitar de către Schneider și colab .. [27] . $P(\Delta)+O(log^{*}(n))$

Problema colorării marginilor a fost studiată și într-un model distribuit. Pansonezzi și Rizzi au realizat -colorarea pentru în acest model [28] . Limita inferioară pentru colorarea vârfurilor distribuite realizată de Linial este de asemenea aplicabilă problemei colorării marginilor distribuite [25] . $(2\Delta -1)$ $O(\Delta +log^{*}(n))$

Algoritmi descentralizati

Algoritmii descentralizați sunt numiți algoritmi în care transmiterea internă a mesajelor nu este permisă (spre deosebire de algoritmii distribuiți , în care procesele fac schimb de date între ele). Există algoritmi descentralizați eficienți care fac față cu succes sarcinii de colorare a graficelor. Acești algoritmi funcționează pe ipoteza că un vârf este capabil să „simți” că oricare dintre vârfurile învecinate are aceeași culoare ca el. Cu alte cuvinte, este posibil să se definească un conflict local. O astfel de condiție este destul de des îndeplinită în aplicațiile din lumea reală - de exemplu, atunci când transmite date pe un canal fără fir, o stație de transmisie, de regulă, are capacitatea de a detecta că o altă stație încearcă să transmită simultan pe același canal. Capacitatea de a obține astfel de informații este suficientă pentru ca algoritmii bazați pe automate de învățare să rezolve corect problema de colorare a graficelor [29] [30] cu probabilitatea unu .

Complexitate computațională

Colorarea graficelor este o sarcină dificilă din punct de vedere informatic. A afla dacă un grafic poate fi k - colorat pentru un k dat este o problemă NP-completă, cu excepția cazurilor k = 1 și k = 2. În special, problema calculării numărului cromatic este NP-hard [31] . Problema cu 3 culori este NP-complet chiar și în cazul unui graf plan de grad 4 [32] .

Este, de asemenea, o problemă dificilă de a colora un grafic cu 3 culori cu 4 culori [33] și un grafic k -colorabil pentru valori suficient de mari ale lui k [34] . $k^{{log(k)/25}}$

Calcularea coeficienților unui polinom cromatic este o problemă #P-hard . S-a dovedit că nu există un algoritm FPRAS pentru calcularea polinomului cromatic pentru orice număr rațional k ≥ 1,5 altul decât k = 2, cu excepția cazului în care NP = RP [35] .

Aplicație

Planificare

Colorarea vârfurilor modelează multe probleme de planificare [36] . În cea mai simplă setare, un anumit set de locuri de muncă ar trebui distribuit pe intervale de timp, fiecare astfel de job ocupând un segment. Ele pot fi executate în orice ordine, dar cele două joburi pot intra în conflict în sensul că nu pot fi realizate în același timp pentru că, de exemplu, folosesc resurse partajate. Graficul corespunzător conține un vârf pentru fiecare job și o muchie pentru fiecare pereche conflictuală. Numărul cromatic al graficului construit este timpul minim pentru a finaliza toate lucrările fără conflicte.

Detaliile problemei de planificare determină structura graficului. De exemplu, atunci când există o împărțire a aeronavelor în zboruri, graficul de conflict rezultat este un grafic de intervale , astfel încât problema de colorare poate fi rezolvată eficient. La distribuirea frecvențelor radio, se obține un grafic al cercurilor de conflict unitar, iar pentru o astfel de problemă există un algoritm cu 3 aproximări .

Înregistrează alocare

Un compilator este un program de calculator care traduce un limbaj de calculator în altul. Pentru a îmbunătăți timpul de execuție a codului rezultat, una dintre tehnicile de optimizare a compilatorului este alocarea registrelor , în care variabilele cele mai frecvent utilizate ale programului compilat sunt stocate în registrele procesorului de mare viteză . În mod ideal, variabilele sunt stocate în registre, astfel încât să fie toate în registre în momentul în care sunt utilizate.

Abordarea standard a acestei probleme este de a o reduce la o problemă de colorare a graficului [8] . Compilatorul construiește un grafic de interferență , unde vârfurile corespund variabilelor, iar o muchie conectează două dintre ele dacă sunt necesare în același timp. Dacă acest grafic este k -cromatic, atunci variabilele pot fi stocate în k registre.

Filigrane digitale

Tehnologia filigranelor digitale ( eng. digital watermarking ) vă permite să transferați un mesaj ascuns împreună cu date (fie fișiere media , fișiere executabile și altele) (" filigran ", filigran ). Un astfel de mesaj ascuns poate fi folosit în protecția drepturilor de autor pentru a identifica proprietarul datelor.

Acest lucru este important, de exemplu, pentru a stabili sursa distribuirii lor ilegale. Sau pentru a confirma drepturile asupra datelor, de exemplu - sisteme software pe un cip ( system-on-cip ).

Mesajul poate fi, de asemenea, codificat în modul în care sunt alocate registrele. O astfel de tehnică a fost propusă de Qu și Potkonjak [37] (de aceea este uneori numită algoritmul QP).

Se compune din următoarele: să fie graficul de incompatibilitate (graful de interferență) al distribuției registrelor procesorului, care a fost menționat mai sus. Colorarea sa este utilizată în program - în plus, este utilizată astfel încât să fie permisă modificarea conținutului graficului cu o ușoară creștere a numărului său cromatic . Se pare că este posibilă codificarea unui mesaj într -un produs software folosind colorarea graficului , adică distribuția registrelor. $G$ $G$

Puteți extrage acest mesaj comparând distribuția registrelor cu colorarea originală; [38] există și modalități de a verifica dacă un mesaj a fost codificat în program fără a-l folosi pe cel original.

Ulterior, diverși autori au dezvoltat și rafinat ideile lui Qu și Potkonjak [39] . [38] [40]

Alte utilizări

Problema colorării graficelor a fost pusă în multe alte aplicații, inclusiv potrivirea modelelor .

Rezolvarea unui puzzle Sudoku poate fi considerată ca completarea unei colorări în 9 culori a unui grafic dat de 81 de vârfuri.

Note

↑ 1 2 3 ( Molloy & Reed 2002 , Definițiile de bază )
↑ ( Donets & Shor 1982 , Referință istorică )
↑ ( Kubale 2004 , Istoria colorării graficelor )
↑ ( van Lint & Wilson 2001 , Cap. 33)
↑ ( Jensen & Toft 1995 , p. 2)
↑ CE Shannon, „The zero-error capacity of a noisy channel”, IEEE Trans. Teoria informației , pp. 8-19, 1956.
↑ ( Zykov 1949 )
↑ 1 2 ( Chaitin 1982 )
↑ AOIvanov, AATuzhilin (2019), The Gromov-Hausdorff Distance between Simplexes and Two-Distance Spaces , < https://arxiv.org/pdf/1907.09942.pdf > Arhivat 29 iulie 2019 la Wayback Machine
↑ ( Birkhoff & Lewis 1946 )
↑ 1 2 3 4 ( Tutte 1984 , Polinom cromatic )
↑ 1 2 3 ( Diestel 2005 , Colorarea vârfurilor )
↑ ( Brooks & Tutte 1941 )
↑ 1 2 ( Diestel 2005 , Colorarea marginilor )
↑ ( Nesetřil & Ossona de Mendez 2012 )
↑ ( de Bruijn, Erdős 1951 )
↑ ( Fawcett 1978 )
↑ ( Lawler 1976 )
↑ ( Beigel & Eppstein 2005 )
↑ ( Fomin, Gaspers & Saurabh 2007 )
↑ ( Sekine, Imai & Tani 1995 )
↑ ( Welsh & Powell 1967 )
↑ 1 2 ( Schneider 2010 )
↑ ( Cole & Vishkin 1986 ), vezi și ( Cormen, Leiserson & Rivest 1990 , Secțiunea 30.5)
↑ 1 2 ( Linial 1992 )
↑ ( Goldberg, Plotkin & Shannon 1988 )
↑ ( Schneider 2008 )
↑ ( Panconesi & Rizzi 2001 )
↑ ( Leith & Clifford 2006 )
↑ ( Duffy, O'Connell și Sapozhnikov 2008 )
↑ ( Garey, Johnson & Stockmeyer 1974 ); ( Garey & Johnson 1979 ).
↑ ( Dailey 1980 )
↑ ( Guruswami & Khanna 2000 )
↑ ( Khot 2001 )
↑ ( Goldberg & Jerrum 2008 )
↑ ( Marx 2004 )
↑ ( Qu & Potkonjak 1998 )
↑ 1 2 ( Zhu & Thomborson 2006 )
↑ ( Collberg, Thomborson & Townsend 2004 )
↑ ( Myles & Collberg 2003 )

Literatură

Donets, G. A. & Shor, N. Z. (1982), An Algebraic Approach to the Plane Graph Coloring Problem , Naukova Dumka, p. 5-7
Zykov, A. A. (1949), Despre unele proprietăți ale complexelor liniare , Mat. sat. T. 24(66) (2): 163–188 , < http://mi.mathnet.ru/eng/msb5974 >
Beigel, R. & Eppstein, D. (2005), 3-coloring in time O(1.3289 n ) , Journal of Algorithms vol . 54 (2)): 168–204 , DOI 10.1016/j.jalgor.2004.06.008
Birkhoff, G.D. & Lewis, D.C. (1946), Polinoame cromatice , Trans. amer. Matematică. soc. T. 60 : 355-451 , >
Brélaz, D. (1979), New methods to color vertices of a graph , Communications of the ACM vol. 22 (4): 251–256 , DOI 10.1145/359094.359101
Brooks, R.L. & Tutte, WT (1941), On coloring the nodes of a network , Proceedings of the Cambridge Philosophical Society vol . 37 (2): 194–197 , DOI 10.1017/S030500410002168X
N. G. de Bruijn, P. Erdős . O problemă de culoare pentru grafice infinite și o problemă în teoria relațiilor (engleză) // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . - S. 371-373 . (= Indag. Matematică 13 )
Byskov, JM (2004), Enumerating maximal independent sets with applications to graph coloring , Operations Research Letters vol. 32 (6): 547–556 , DOI 10.1016/j.orl.2004.03.002
Cormen, T.H.; Leiserson, CE & Rivest, RL (1990), Introduction to Algorithms (prima ed.), The MIT Press
Collberg, creștin; Thomborson, Clark & Townsend, Gregg M. (2004), Filigranare software dinamică bazată pe grafice , < ftp://ftp.cs.arizona.edu/reports/2004/TR04-08.pdf >
Chaitin , GJ (1982), Register allocation & spilling via graph coloring , Proc. 1982 Simpozion SIGPLAN privind construcția compilatorului , p. 98–105, ISBN 0-89791-074-5 , DOI 10.1145/800230.806984
Cole, R. & Vishkin, U. (1986), Deterministic coin tossing with applications to optimal parallel list ranking , Information and Control vol. 70 (1): 32–53 , DOI 10.1016/S0019-9958(86)80023-7
Dailey, D.P. (1980), Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete , Discrete Mathematics vol . 30 (3): 289–293 , DOI 10.1016/0012-365X(80)90236-8
Diesel, R. (2005), Teoria grafurilor , < http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf > Arhivat la 25 noiembrie 2014 la Wayback Machine
Duffy, K.; O'Connell, N. & Sapozhnikov, A. (2008), Complexity analysis of a descentralized graph coloring algorithm , Information Processing Letters vol . 107: 60–63, doi : 10.1016/j.ipl.2008.01.002 , < http: //www.hamilton.ie/ken_duffy/Downloads/cfl.pdf >
Fawcett, BW (1978), Despre infinite colorări complete ale graficelor, Can. J Math. T. XXX: 455–457
Fomin, FV; Gaspers, S. & Saurabh, S. (2007), Improved Exact Algorithms for Counting 3- and 4-Colorings , Proc. 13th Annual International Conference, COCOON 2007 , vol. 4598, Lecture Notes in Computer Science , Springer, p. 65-74, ISBN 978-3-540-73544-1
Garey, MR & Johnson, DS (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, ISBN 0-7167-1045-5
Goldberg, LA & Jerrum, M. (iulie 2008), Inapproximability of the Tutte polynomial , Information and Computation vol. 206 (7): 908–929 , DOI 10.1016/j.ic.2008.04.003
Goldberg, A.V .; Plotkin, SA & Shannon, GE (1988), Parallel symmetry-breaking in sparse graphs , SIAM Journal on Discrete Mathematics vol . 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 , p. 188–197, ISBN 0-7695-0674-7 , DOI 10.1109/CCC.2000.856749
Jaeger, F.; Vertigan, DL & Welsh, DJA (1990), Despre complexitatea computațională a polinoamelor Jones și Tutte , Mathematical Proceedings of the Cambridge Philosophical Society vol. 108: 35–53 , DOI 10.1017/S0305004100068936
Jensen, Tommy R. și Toft, Bjarne (1995), Probleme de colorare a graficelor , John Wiley & Sons, ISBN 0-471-02865-7
Khot, S. (2001), Rezultate îmbunătățite de inaproximabilitate pentru MaxClique, număr cromatic și colorare aproximativă a graficului , Proc. Al 42-lea simpozion anual despre fundamentele informaticii , p. 600–609, ISBN 0-7695-1116-3 , DOI 10.1109/SFCS.2001.959936
Kubale, M. (2004), Graph Colorings , Societatea Americană de Matematică, 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 , p. 138–144, ISBN 978-1-60558-606-9
Lawler, EL (1976), A note on the complexity of the chromatic number problem , Information Processing Letters vol . 5 (3): 66–67 , DOI 10.1016/0020-0190(76)90065-X
Leith, DJ & Clifford, P. (2006), A Self-Managed Distributed Channel Selection Algorithm for WLAN , Proc. RAWNET 2006, Boston, MA , < http://www.hamilton.ie/peterc/downloads/rawnet06.pdf >
Linial, N. (1992), Locality in distributed graph algorithms , SIAM Journal on Computing vol. 21 (1): 193–201 , DOI 10.1137/0221015
van Lint, JH & Wilson, R.M. (2001), Un curs de combinatorică (ed. a doua), Cambridge University Press, ISBN 0-521-80340-3
Molloy, Michael & Reed, Bruce (2002), Graph coloring and the probabilistic method , Springer, ISBN 3-540-42139-4 , ISSN 0937-5511
Marx, Dániel (2004), Probleme de colorare a graficelor și aplicațiile lor în planificare, Periodica Polytechnica, Inginerie electrică , voi. 48, p. 11–16, CiteSeerX:10.1.1.95.4268
Mycielski, J. (1955), Sur le coloriage des graphes , Colloq. Matematică. Vol. 3: 161–162 , < http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf > .

Myles, Ginger & Collberg, Christian S. (2003), Software Watermarking Through Register Allocation: Implementation, Analysis, and Attacks , ICISC , p. 274-293 , DOI 10.1007/b96249

Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Teorema 3.13 , Sparsity: Graphs, Structures, and Algorithms , voi. 28, Algoritmi și combinatorie, Heidelberg: Springer, p. 42, ISBN 978-3-642-27874-7 , DOI 10.1007/978-3-642-27875-4 .
Panconesi, Alessandro & Rizzi, Romeo (2001), Some simple distributed algorithms for sparse networks , Distributed Computing (Berlin, New York: Springer-Verlag ). — V. 14 (2): 97–100, ISSN 0178-2770 , DOI 10.1007/PL00008932
Panconesi, A. & Srinivasan, A. (1996), Despre complexitatea descompunerii rețelelor distribuite, Journal of Algorithms , voi. douăzeci
Qu, Gang & Potkonjak, Miodrag (1998), Analysis of watermarking techniques for graph coloring problem , ICCAD , p. 190-193 , DOI 10.1145/288548.288607
Schneider, J. (2010), O nouă tehnică pentru spargerea simetriei distribuite , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf > Arhivat la 30 iulie 2013 mașina Wayback
Schneider, J. (2008), A log-star distribuite maximal independent set algorithm for growth-bounded graphs , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podc08SW. pdf > Arhivat 30 iulie 2013 la Wayback Machine
Sekine, K.; Imai, H. & Tani, S. (1995), Calcularea polinomului Tutte al unui grafic de mărime moderată , Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995) , voi. 1004, Note de curs în informatică , Springer, p. 224–233, ISBN 3-540-60573-8 , DOI 10.1007/BFb0015427
Tutte, WT (1984), Teoria grafurilor, Enciclopedia matematicii și aplicațiilor (Cambridge University Press). - Vol. 21, ISBN 0-521-30241-2
Welsh, DJA & Powell, MB (1967), O limită superioară pentru numărul cromatic al unui grafic și aplicarea acestuia la problemele de orar , The Computer Journal vol . 10 (1): 85–86 , DOI 10.1093/comjnl/10.1.85
Wilf, H. S. (1986), Algoritmi și complexitate , Prentice–Hall
Zhu, William & Thomborson, Clark (2006), Recognition in software watermarking , MCPS '06: Proceedings of the 4th ACM international workshop on Contents protecting and security , ACM, p. 29–36, ISBN 1-59593-499-5 , DOI 10.1145/1178766.1178776