Colorare uniformă

Colorarea uniformă  este alocarea de culori la vârfurile unui grafic nedirecționat astfel încât:

Adică, împărțirea vârfurilor în culori diferite este cât se poate de uniformă. De exemplu, acordarea fiecărui vârf de o culoare diferită ar fi o colorare uniformă, dar ar folosi de obicei mult mai multe culori decât este necesar pentru o colorare uniformă optimă. O modalitate echivalentă de a defini o colorare uniformă este încorporarea unui grafic dat ca subgraf într-un grafic Turan cu același set de vârfuri. Există două tipuri de numere cromatice asociate cu colorarea uniformă [1] . Numărul cromatic uniform al unui grafic G  este cel mai mic număr k astfel încât graficul G are o colorare uniformă cuk flori. Cu toate acestea, graficul G poate să nu aibă colorații uniforme pentru unele seturi mai mari de culori. Pragul cromatic uniform al unui grafic G  este cel mai mic număr k astfel încât graficul G are colorări uniforme pentru orice număr de culori mai mare sau egal cu k [2] .

Teorema Hajnal-Szemeredy , care a fost formulată ca o presupunere de Pal Erdős [3] și demonstrată de András Hajnal și Endre Szemeredy [4] , afirmă că orice graf cu un grad maxim are o colorare uniformă cu culorile. Mai multe ipoteze înrudite rămân deschise. Există, de asemenea, algoritmi de timp polinomial pentru găsirea unei colorări corespunzătoare acestei limite [5] , precum și algoritmi pentru găsirea colorațiilor optime pentru clase speciale de grafice, dar o problemă mai generală de a determina dacă un graf arbitrar are o colorare uniformă cu o anumită dată. numărul de culori este NP-complet .

Exemple

Steaua K 1.5 prezentată în figură este un grafic bipartit complet și, prin urmare, poate fi colorată cu două culori. Cu toate acestea, colorarea rezultată are un vârf de o culoare și cinci vârfuri de altă culoare și, prin urmare, colorarea nu este uniformă. Cel mai mic număr de culori într-o colorare uniformă a acestui grafic este de patru, așa cum se arată în figură - vârful central trebuie să aparțină unei clase cu un singur vârf, astfel încât celelalte cinci vârfuri trebuie împărțite în cel puțin trei culori, astfel încât fiecare clasa conține cel mult două vârfuri. Mai general, Meyer [6] a observat că orice stea K 1, n necesită culori pentru o colorare uniformă și, prin urmare, numărul cromatic al unui grafic poate diferi de numărul său uniform cromatic de cel mult n /4 ori. Deoarece K 1,5 are un grad maxim de cinci, numărul de culori garantat de teorema Hajnal-Szemeredi este de șase, care se obține prin atribuirea unei culori diferite fiecărui vârf.

Un alt fenomen interesant arată un alt grafic bipartit complet, . Acest grafic are o 2-colorare uniformă definită de bipartitul său. Cu toate acestea, nu are o colorare uniformă (2 n  + 1) - orice împărțire uniformă a vârfurilor în acest număr de culori ar trebui să aibă exact două vârfuri pe culoare, dar cele două părți ale unui grafic bipartit nu pot fi împerecheate deoarece conţin un număr impar de vârfuri. Prin urmare, pragul cromatic uniform al acestui grafic este , care este mult mai mare decât numărul său cromatic uniform, care este doi.

Teorema Hainal-Semeredi

Teorema lui Brooks afirmă că orice graf conectat cu grad maxim este -colorabil, cu două excepții ( grafice complete și cicluri impare). Cu toate acestea, această colorare poate fi, în general, departe de a fi uniformă. Pal Erdős [3] a presupus că o colorare uniformă este posibilă doar cu o singură culoare complementară - orice grafic cu grad maxim are o colorare uniformă cu culori. Cazul este simplu (orice combinație de căi și bucle poate fi colorată uniform cu modele repetate în trei culori, cu ușoare ajustări pentru bucle închise). Cazul a fost decis de Corradi și Hainal [7] . Conjectura completă a fost dovedită de Hajnal și Semeredi [4] și este acum cunoscută ca teorema Hajnal-Szemeredi. Dovada lor inițială a fost lungă și complicată. O dovadă mai simplă a fost dată de Kirsted și Kostochka [8] . Kiersted și Kostochka au descris un algoritm de timp polinomial pentru găsirea de colorații uniforme cu acest număr de culori. Ei atribuie lui Marcelo Midlarz și Endre Szemeredi un algoritm de timp polinomial diferit, dezvoltat anterior, nepublicat. Kiersted și Kostochka au anunțat, de asemenea, o versiune mai puternică a teoremei că există o colorare k uniformă dacă gradele oricăror două vârfuri adiacente se însumează cel mult , dar dovada nu a fost niciodată publicată.

Meyer [6] a presupus sub forma teoremei de colorare uniformă a lui Brooks că orice graf conectat cu grad maxim are o colorare uniformă cu sau mai puține culori, cu excepția graficelor complete și a ciclurilor impare. O versiune mai puternică a conjecturii afirmă că fiecare astfel de graf are o colorare uniformă cu exact culori, cu excepția suplimentară a unui graf bipartit complet în care ambele părți au același număr impar de vârfuri [1] .

Seymour [9] a propus o consolidare a teoremei Hajnal-Szemeredi, care include și teorema lui Dirac conform căreia grafurile dense sunt hamiltoniene  - el a presupus că, dacă orice vârf dintr-un graf cu n vârfuri are cel puțin vecini, atunci graficul conține ca subgraf pe grafic format prin conectarea vârfurilor care se află la cel mult k pași într-un n -ciclu. Cazul k  = 1 este teorema proprie a lui Dirac. Teorema Hajnal-Szemeredi poate fi depășită de această ipoteză prin aplicarea ipotezei pentru valori mari ale lui k la complementul graficului și folosind secvențe continue de vârfuri din ciclul n ca clase de culoare . Conjectura lui Seymour a fost dovedită pentru grafice în care n este suficient de mare în comparație cu k [10] . Dovada folosește câteva mijloace profunde, inclusiv teorema Hajnal-Szemeredi în sine.

O altă generalizare a teoremei Haynal-Szemeredi este ipoteza Bollobash-Eldridge-Katlin (sau, pe scurt, ipoteza BEC) [11] . Se afirmă că dacă G 1 și G 2 sunt grafice n -vertex cu gradul maxim și respectiv, și dacă , atunci G 1 și G 2 pot fi împachetate. Adică, G1 și G2 pot fi reprezentați pe aceeași mulțime de n vârfuri fără muchii comune . Teorema Hajnal-Szemeredi este un caz special al conjecturei în care G 2 este uniunea de clicuri disjunse . Catlin [12] oferă o condiție similară, dar mai puternică asupra și sub care este garantată existența unui astfel de ambalaj.

Cazuri speciale de grafice

Pentru orice arbore cu grad maxim, numărul cromatic uniform nu depășește

[6]

cu cel mai rău caz pe o stea. Cu toate acestea, majoritatea arborilor au un număr cromatic uniform mult mai mic - dacă un arbore cu n vârfuri are , atunci are o colorare uniformă cu doar trei culori [13] . Furmanchik [1] a studiat numărul cromatic uniform al produselor graficelor .

Complexitate computațională

S-a studiat și problema găsirii coloranților uniforme cu cât mai puține culori (sub limita Hainal-Semeredi). O reducere directă de la o colorare a graficului la o colorare uniformă poate fi dovedită prin adăugarea unor vârfuri izolate la grafic, ceea ce arată că testarea dacă un grafic are o colorare uniformă cu un număr dat de culori (mai mare de două) este NP-complet . Cu toate acestea, problema devine mai interesantă atunci când este restrânsă la o clasă specială de grafice sau în termeni de complexitate parametrizată . Bodlander și Fomin [14] au arătat că, având în vedere un grafic G și un număr de culori c , se poate verifica dacă G poate fi uniform c -colorat în timp O( n O( t ) ), unde t  este lățimea arborelui G . În special, colorarea uniformă poate fi rezolvată optim în timp polinomial pentru copaci (așa cum este cunoscut datorită lui Chen și Lee [15] ) și grafurilor exterioare planare . Există, de asemenea, un algoritm de timp polinomial pentru colorarea uniformă a graficelor divizate [16] . Totuși, Fellowes, Fomin, Lokshtanov și alții [17] au demonstrat că atunci când lățimea arborelui este un parametru al algoritmului, problema este W[1]-hard. Astfel, este puțin probabil să existe un algoritm de timp polinomial care să fie independent de acest parametru sau chiar ca dependența de parametru să poată fi încadrată de exponent în formula timpului de rulare.

Aplicații

Unul dintre motivele pentru a lua în considerare colorarea uniformă a fost sugerat de Meyer [6] în legătură cu problemele de programare . În această aplicație, vârfurile graficului reprezintă un set de sarcini de efectuat, iar muchiile conectează două sarcini care nu pot fi efectuate în același timp. Colorarea acestui grafic reprezintă împărțirea sarcinilor în subseturi care pot fi executate simultan. Apoi, numărul de culori din colorare corespunde numărului de pași necesari pentru a finaliza sarcina complet. Conform convențiilor de echilibrare a sarcinii , este de dorit să se efectueze același sau aproape același număr de sarcini în fiecare pas, iar această echilibrare este exact ceea ce oferă o colorare uniformă. Furmanchik [1] a menționat o aplicație specifică a acestui tip de problemă de programare, și anume repartizarea cursurilor universitare pe ore academice astfel încât cursurile să fie distribuite în mod egal pe intervalele orare disponibile, pentru a evita alocarea de perechi de cursuri incompatibile în același timp.

Teorema Hajnal-Szemeredi a fost de asemenea folosită pentru a limita varianța sumelor variabilelor aleatoare cu dependență mărginită [18] [19] . Dacă (ca și în condiția lemei locale Lovas ) fiecare variabilă depinde de cel mult altele, colorarea uniformă a graficului de dependență poate fi utilizată pentru a împărți variabilele în submulțimi independente în care pot fi calculate limitele Chernoff , ceea ce va oferi limite mai bune pe varianța decât dacă este împărțită într-un mod neuniform.

Note

  1. ↑ 1 2 3 4 Furmańczyk, 2006 .
  2. ↑ Rețineți că atunci când k este mai mare decât numărul de vârfuri din grafic, există întotdeauna o colorare uniformă cu k culori în care toate clasele de culori au zero sau un vârf pe clasă, astfel încât orice grafic are un prag cromatic uniform.
  3. ↑ 12 Erdős , 1964 .
  4. ↑ 1 2 Hajnal, Szemerédi, 1970 .
  5. ↑ Kierstead, Kostochka, Mydlarz, Szemerédi, 2010 , p. 217–224.
  6. ↑ 1 2 3 4 Meyer, 1973 .
  7. ↑ Corrádi, Hajnal, 1963 .
  8. ↑ Kierstead, Kostochka, 2008 .
  9. ↑ Seymour, 1974 .
  10. ↑ Komlós, Sárközy, Szemerédi, 1998 .
  11. ↑ Bollobás, Eldridge, 1978 .
  12. ↑ Catlin, 1974 .
  13. ↑ Bollobás, Guy, 1983 .
  14. ↑ Bodlaender, Fomin, 2005 .
  15. ↑ Chen, Lih, 1994 .
  16. ↑ Chen, Ko, Lih, 1996 .
  17. ↑ Fellows, Fomin, Lokshtanov, 2007 .
  18. ↑ Pemmaraju, 2001 .
  19. ↑ Janson, Ruciński, 2002 .

Literatură

Link -uri