În matematică , în special în teoria graficelor , teorema lui Brooks oferă o relație între gradul maxim al unui grafic conectat nedirecționat și numărul cromatic .
Conform acestei teoreme, într-un grafic în care fiecare vârf are cel mult Δ vecini , vârfurile pot fi colorate cu cel mult Δ culori, fără ca două vârfuri adiacente să aibă aceeași culoare, cu excepția în două cazuri, graficele complete și graficele impare cicluri de lungime, care necesită Δ + 1 culori.
Teorema - În orice grafic G nedirectat de grad maxim Δ, numărul cromatic χ (G) satisface χ (G) ≤ Δ, cu excepția cazului în care G este un grafic complet sau un ciclu de lungime impar, caz în care χ (G) = Δ + 1.
Teorema este numită după R. Leonard Brooks , care a publicat o dovadă a acesteia în 1941. Colorarea cu numărul de culori descrisă de teorema lui Brooks este uneori numită colorare Brooks sau colorare Δ- . László Lovász a dat o dovadă mai simplă a teoremei în 1975.
Nu este foarte greu de arătat că, pentru orice grafic, χ (G) ≤ Δ + 1. Într-adevăr, orice vârf v are cel mult Δ vârfuri învecinate, care în cel mai rău caz sunt toate colorate diferit. Chiar și în acest caz, putem lua întotdeauna culoarea (Δ + 1) pentru a v . Meritul lui Brooks a fost acela de a reduce această creștere cu 1 unitate în majoritatea cazurilor.
Există mai multe dovezi ale teoremei lui Brooks. De exemplu, putem argumenta prin inducție asupra numărului de vârfuri ale graficului. Următoarea demonstrație se desfășoară diferit, se bazează pe algoritmul lacom pentru colorarea graficelor și, prin urmare, are meritul de a furniza algoritmi pentru colorarea graficului (este o demonstrație constructivă ).
Această demonstrație a fost prezentată de Ross Churchley în 2010 pe baza lucrării lui John Adrian Bondy în 2003. Finalul înlocuiește raționamentul lui Bondy cu alte lucrări, astfel încât să nu trebuiască să apeleze mai întâi la rezultatele referitoare la arborii din zona de adâncime .
În cele ce urmează, examinăm succesiv patru cazuri:
Principiul, în cazul graficelor neregulate , este de a ordona vârfurile într-un anumit mod și apoi de a le colora unul după altul folosind algoritmul lacom .
Fie G un grafic neregulat cu n vârfuri și grad maxim Δ. Deoarece G nu este regulat, există cel puțin un vârf x de grade s strict mai mic decât Δ. Plasăm acest vârf la sfârșitul planificării, adică v n = x (figura 1) . Vârfurile adiacente lui x sunt plasate chiar înainte în această ordonare, adică în v n-s , v n-s-1 , ..., v n-1 (figura 2) .
Luăm apoi în considerare vârfurile adiacente lui v n-1 care nu au fost deja ordonate (figura 3) , apoi cele care sunt adiacente lui v n-2 și care nu au fost încă ordonate și așa mai departe până când le ordonăm pe toate, care este posibil deoarece G este conectat (figura 4) .
În această ordonare (v 1 , v 2 ,…, v n ) , toate vârfurile au cel puțin un vârf adiacent posterior (de indice mai mare), cu excepția vârfului x . În consecință, toate au, cu excepția vârfului x , un număr de vârfuri adiacente anterioare (cu indice inferior) strict mai mic decât Δ. Ultimul vârf x are, de asemenea, prin alegerea sa inițială, un număr de vârfuri adiacente anterioare strict mai mici decât Δ.
Apoi colorăm vârfurile v i unul după altul, pentru i variind de la 1 la n . La fiecare pas, vârful v i nu a fost încă colorat. Vârfurile sale adiacente anterioare, care au fost deja colorate, au un număr maxim de Δ - 1 și, prin urmare, utilizează a fortiori un maxim de Δ - 1 culori. Prin urmare, putem lua pentru noul vârf, în cel mai rău caz, culoarea rămasă dintre Δ (figurile 5-8) .
Într-un grafic neconectat, există cel puțin un punct de articulare , adică un vârf care, dacă este eliminat, face graficul neconectat.
Luați în considerare un astfel de grafic regulat G al gradului Δ care nu este conectat și să fie x un punct de articulație al lui G (în roșu în figura 1).
Descompunem G prin înmulțirea punctului de articulație ca în FIG. 2. Obținem cel puțin două grafice neregulate conectate de grad maxim Δ: într-adevăr, vârfurile obținute prin înmulțirea x sunt fiecare de grad strict mai mic decât Δ.
Unul este astfel readus în cazul precedent și se poate colora fiecare componentă neconectată conectată utilizând metoda expusă anterior. Putem aranja ca vârfurile obținute prin înmulțirea x să aibă aceeași culoare: pentru aceasta, schimbăm culorile în componentele conectate, dacă este necesar.
Rămâne doar să reasamblați părțile grafului pentru a obține un grafic colorat cu with culori.
Singurul grafic regulat conectat de gradul 0 este graficul 0 regulat compus dintr-un singur vârf. Poate fi colorat cu 1 culoare (figura 1) . Întrucât se încadrează în categoria graficelor complete, satisface afirmația teoremei lui Brooks.
Singurul grafic regulat conectat de 1 grad este graficul 1 regulat format din doar două vârfuri, cu o margine între aceste două vârfuri (figura 2) . Poate fi colorat cu 2 culori și și aici suntem în cazul unui grafic complet: satisface afirmația teoremei lui Brooks.
Singurele grafice regulate conectate de gradul 2 sunt cicluri. Ciclurile cu un număr par de vârfuri pot fi colorate cu 2 culori (figura 4) și sunt necesare 3 culori pentru ciclurile cu un număr impar de vârfuri (figurile 3 și 5) . În ambele cazuri, afirmația teoremei lui Brooks susține.
Dacă graficul G este complet și de grad Δ, are Δ + 1 vârfuri pe care le putem colora fiecare cu o culoare diferită. Și în acest caz se menționează afirmația teoremei lui Brooks.
Dacă graficul nu este complet, vom comanda din nou un anumit număr de vârfuri, apoi le vom colora folosind algoritmul lacom. Cu toate acestea, nu este la fel de simplu ca în cazul graficului neregulat, deoarece nimic nu garantează a priori să avem o culoare liberă când ajungem la ultimul vârf. Prin urmare, vom aranja ca ultimul vârf colorat v să aibă doi vecini u și w deja colorați în aceeași culoare, ceea ce ne asigură că vom avea cel puțin încă o culoare liberă atunci când vine vorba de colorarea v .
Fie G un grafic necomplet, biconectat, de grad Δ ≥ 3. Există trei vârfuri u , v și w astfel încât
Deoarece G nu este complet, există două vârfuri a și b care nu sunt legate direct de o margine. Pe măsură ce graficul este conectat, există o cale ( a , v 1 , v 2 , ..., v p , b ) care leagă a la b . Fie eu cea mai mare valoare astfel încât v i să aibă legătură cu a . Se consideră u = a , v = v i și w = v i + 1 . Aceste trei vârfuri verifică dacă u și w sunt legate de v fără a fi legate între ele.
Deoarece graficul este biconectat, putem elimina u sau w din acesta fără a înceta să fim conectați: G - { u } și G - { w } sunt conectați. Putem chiar reuși să luăm u , v și w astfel încât G - { u , w } să fie încă conectat.
Demonstrație Lema 2 Într-un grafic biconectat G, de grad minim 3 sau mai mult și care nu este complet, putem găsi vârfurile u și w învecinate cu același vârf v , dar nu învecinate între ele, astfel încât G - { u , w } este încă conectat.Deoarece graficul nu este complet, există cel puțin un vârf a care nu este adiacent tuturor celorlalte.
Dacă G - { a } este biconectat, luăm, ca în dovada Lemei 1, u = a și w egală cu orice vârf la distanța 2 de a . Deoarece G - { a } este conectat, putem elimina w din acesta fără a pierde conectivitatea, iar G - { u , w } este conectat.
Luați în considerare acum cazul în care G - { a } este conectat, dar nu biconectat. Prin urmare, are puncte de articulare (în roșu în figură) . Fie z unul dintre aceste puncte de articulare. G - { a , z } nu este conectat, este chiar împărțit în cel puțin două componente conectate disjuncte. Fiecare dintre aceste componente conectate V 1 , V 2 ,… V n poate fi la rândul său tăiată în componente biconectate conectate prin punctele de articulație. Aceste componente biconectate formează un copac cu rădăcina z .
În G, a are un vecin în fiecare dintre frunze la capătul acestui copac. Într-adevăr, dacă eliminăm punctul de articulație z i de care este atașată frunza, dacă nu ar fi conectat la a la celălalt capăt, G - { z i } ar fi neconectat, ceea ce este imposibil, deoarece G este biconectat.
Să luăm u în una dintre frunze la sfârșitul lui V 1 și w într-una din frunze la sfârșitul lui V 2 și să v = a . Vârfurile u și w sunt foarte apropiate de v . Nu sunt adiacente, deoarece sunt luate din diferite componente conectate.
Vârfurile u și w fiind luate în componente biconectate ale lui G - { a } în timp ce sunt diferite de punctele de articulare ale lui G - { a }, G - { a , u , w } rămâne conectat. După cum, de altfel, gradul de o mai mare sau egal cu 3, există un al treilea nod care permite să se conecteze un G - { a , u , w }. Prin urmare, graficul G - { u , w } este conectat.
Deoarece G - { u , w } este conectat, îl putem comanda ca în cazurile anterioare dând v cel mai puternic număr. Apoi colorăm G după cum urmează:
Când ajungem să colorăm ultimul vârf v , avem garanția că rămâne o culoare liberă, deoarece cei doi vecini ai săi u și w au aceeași culoare (figura 2) .
O generalizare a teoremei lui Brooks se aplică colorării listelor : dat un grafic nedirecționat și conectat de grad maxim Δ care nu este nici un grafic complet, nici un ciclu de lungime impar și o listă de list culori pentru fiecare vârf, este posibil să alegeți un culoare pentru fiecare vârf luat în lista sa, astfel încât două vârfuri adiacente să nu aibă niciodată aceeași culoare. Cu alte cuvinte, numărul cromatic al listei unui grafic conectat nedirecționat nu este niciodată mai mare de Δ, cu excepția cazului unui grafic complet sau a unui ciclu de lungime impar. Acest lucru a fost demonstrat de Vadim Vizing în 1976.
Cu unele grafice, avem nevoie chiar de mai puține Δ culori. Bruce Reed arată că Δ - 1 culori sunt suficiente dacă și numai dacă graficul nu are Δ- clicuri când Δ este suficient de mare. Pentru graficele fără triunghi (fără un set de trei vârfuri adiacente în perechi), sau mai general pentru graficele în care vecinătatea fiecărui vârf este suficient de goală , culorile O (Δ / log Δ) sunt suficiente.
Gradul unui grafic apare și în limitele superioare ale numărului de culori necesare pentru alte tipuri de colorare:
O colorare cu Δ culori, sau chiar o colorare prin listă cu Δ culori, a unui grafic de grad maxim Δ poate fi obținută într-un timp liniar (proporțional cu numărul de vârfuri și margini). Sunt cunoscuți, de asemenea, algoritmi eficienți care fac posibilă găsirea petelor Brooks folosind prelucrări paralele sau distribuite.
(ro) Eric W. Weisstein , „ Brooks 'Theorem ” , pe MathWorld