Brooks-tétel

A Wikipédiából, a szabad enciklopédiából

A gráfelméletben a Brooks-tétel a gráf maximális fokszáma és kromatikus száma közötti összefüggés. A tétel Rowland Leonard Brooks-tól származik, aki 1941-ben publikálta On Coloring the Nodes of a Network cikkében.[1]

Legyen G véges, összefüggő gráf, ami nem páratlan hosszú kör vagy teljes gráf. Jelölje \Delta(G) a G maximális fokszámát, \chi(G) pedig a kromatikus számát. Ekkor

\chi(G)\le \Delta(G).

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

\Delta(G) = 2 -re nyilvánvaló az állítás, ugyanis ha a maximális fokszám 2, akkor vagy egy kört, vagy egy utat kapunk. Egy út vagy egy páros kör esetében 2 színnel ki tudjuk színezni a gráfot, és ha a kör páratlan hosszúságú akkor csak hárommal.

Most már feltehetjük, hogy \Delta(G)  \geq 3. A csúcsok számára való indukcióval bizonyítjuk az állítást.

Az első lépésben azt látjuk be, hogy elég kétszeresen összefüggő gráfokat vizsgálnunk. Indirekt tegyük fel, hogy nem kétszeresen összefüggő a vizsgálandó gráfunk, ami azt jelenti hogy létezik x pont, melyet elhagyva legalább két komponensre esik szét a gráfunk. Ha pontosan két komponensre esik szét, akkor rakjuk vissza mindkét komponensbe x-et, és nevezzük ezeket a komponenseket G_1 és G_2-nek. Ha több mint két komponensre esik szét, akkor maradjon G_1 továbbra is egy komponens és G_2 meg legyen az összes többi komponens és x uniója: G_2 = (G \ G_1) \cup {x}. A két komponensben minden csúcs fokszáma ugyanannyi marad, csak x fokszáma csökken. Tehát továbbra sem lesz egyik fokszám sem nagyobb mint \Delta(G), viszont x feltétlenül kisebb lesz mindkét komponensben \Delta(G)-nel. Ebből következik, hogy egyik komponens sem lehet \Delta(G) + 1 pontú teljes gráf. Tehát, az indukciós feltevésünk miatt, mindkét komponens kiszínezhető \Delta(G) színnel, és ha x-et mindkét komponensben ugyanolyan színűre választjuk, akkor ha újra „összerakjuk” a gráfot akkor az eredeti gráfunknak egy \Delta(G) színnel való jó színezését kapjuk.

Második lépésben pedig azt igazoljuk, hogy elég háromszorosan összefüggő gráfokat néznünk. Ismét indirekt tegyük fel hogy egy x és y pont elhagyásával szétesik a gráfunk G_1 és G_2-re. Végezzük el ugyanazt az eljárást mint az első lépésben. Itt csak akkor van gond, ha az egyik komponens minden színezése olyan hogy x és y egyforma színű, és a másik komponens minden színezésénél x és y különböző színű. Ebben az esetben nem tudjuk újra „összerakni” a gráfunkat. Ebben az esetben tekintsük a G_1 és G_2 komponenst és mindkettőben húzzunk be x és y között egy élet. Így x és y fokszáma továbbra is legfeljebb \Delta(G) marad, vagyis az indukciós feltevés miatt vagy mindkét komponens kiszínezhető \Delta(G) színnel, vagy legalább az egyik komponensünk egy \Delta(G) + 1 csúcsú teljes gráf. Ha színezhető mindkettő \Delta(G) színnel, akkor mindkét komponensben különböző színű x és y, tehát „össze tudjuk illeszteni” a két komponenst és készen vagyunk. Ha pedig az egyik komponensünk egy \Delta(G) + 1 pontú teljes gráf, akkor ebben a komponensben x-nek és y-nak is csak egy szomszédja volt a másik komponensben. Jelöljük ezeket x' és y'-vel. Ha most elvesszük mondjuk az x és y' csúcsot az eredeti gráfunkból, akkor ismét két részre esik a gráfunk. Ha ezzel a két ponttal végezzük el az előbbi algoritmust akkor nem kapunk olyan komponenst ami teljes gráf, tehát megkapjuk a gráf egy \Delta(G) színnel való jó színezését.

Innentől már csak háromszorosan összefüggő gráfokra kell bizonyítanunk az állítast. Legyenek v_1,v_2,v_n olyan csúcsai G-nek, hogy v_1 és v_n között fut él, v_2 és v_n között is fut él, viszont v_1 és v_2 között nem fut él (mivel G nem teljes gráf és összefüggő, ezért ilyen csúcsokat minden esetben találunk). Jelöljük a gráf többi pontját a következőképpen: v_3,v_4,…,v_{n-1} és minden pontnak legyen nagyobb indexű szomszédja is. Ha most elvesszük a gráfból a v_1 és v_2 csúcsokat akkor G továbbra is összefüggő marad, hiszen háromszorosan összefüggő volt. Ennek a gráfnak tekintsük egy feszítőfáját. Egy feszítőfának legalább két elsőfokú pontja van, tehát lesz elsőfokú pontja v_n-en kívül. Legyen ez a csúcsunk v_3. Tehát most elvehetjük v_1, v_2, és v_3-at a gráfból és összefüggő marad, és most ennek a gráfnak tekintjük a feszítőfáját, és hasonlóan kapjuk v_4-et.

Az utolsó lépésben már csak meg kell adnunk egy megfelelő színezést \Delta(G) színnel: Színezzük v_1-et és v_2-ot egyforma színűre. A többi csúcsot indexük szerint sorban színezzük ki mohó módon: v_i-hez mindig találunk majd szabad színt, mert ennek a csúcsnak mindig csak a kisebb indexű csúcsát színeztük még ki és ebből kevesebb van mint \Delta(G). Csak v_n-nek lehet \Delta(G) szomszédja, ezek között viszont kettő (v_1 és v_2) már egyforma színű. Ezzel igazoltuk az állítást.

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • Brooks, R. L. "On Coloring the Nodes of a Network." Proc. Cambridge Philos. Soc. 37, 194-197, 1941.
  • Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 80-82.

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Lovász - Pelikán - Vesztergombi: Diszkrét matematika. 209, 214. old. Typotex Kiadó, 2006. ISBN 963-9664-02-2