Főmenü megnyitása
A teljes gráfok színezéséhez a maximális fokszámnál eggyel több színre van szükség. Ők és a páratlan hosszú körök adják a Brook-tétel kivételes eseteit.

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 véges, összefüggő gráf, ami nem teljes gráf vagy páratlan csúcsú körgráf. Jelölje a maximális fokszámát, pedig a kromatikus számát. Ekkor

BizonyításSzerkesztés

  = 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     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   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  -et, és nevezzük ezeket a komponenseket   és  -nek. Ha több mint két komponensre esik szét, akkor maradjon   továbbra is egy komponens és   meg legyen az összes többi komponens és x uniója:   = (  \  )   { }. 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  , viszont   foka feltétlenül kisebb lesz mindkét komponensben  -nél. Ebből következik, hogy egyik komponens sem lehet   + 1 pontú teljes gráf. Tehát, az indukciós feltevésünk miatt, mindkét komponens kiszínezhető   színnel, és ha  -et mindkét komponensben ugyanolyan színűre választjuk, akkor ha újra „összerakjuk” a gráfot akkor az eredeti gráfunknak egy   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   és   pont elhagyásával szétesik a gráfunk   és  -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   és   egyforma színű, és a másik komponens minden színezésénél   és   különböző színű. Ebben az esetben nem tudjuk újra „összerakni” a gráfunkat. Ebben az esetben tekintsük a   és   komponenst és mindkettőben húzzunk be   és   között egy élt. Így   és   fokszáma továbbra is legfeljebb   marad, vagyis az indukciós feltevés miatt vagy mindkét komponens kiszínezhető   színnel, vagy legalább az egyik komponensünk egy   + 1 csúcsú teljes gráf. Ha színezhető mindkettő   színnel, akkor mindkét komponensben különböző színű   és  , tehát „össze tudjuk illeszteni” a két komponenst és készen vagyunk. Ha pedig az egyik komponensünk egy   + 1 pontú teljes gráf, akkor ebben a komponensben  -nek és  -nak is csak egy szomszédja volt a másik komponensben. Jelöljük ezeket   és  -vel. Ha most elvesszük mondjuk az   és   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   színnel való jó színezését.

Innentől már csak háromszorosan összefüggő gráfokra kell bizonyítanunk az állítást. Legyenek  , ,  olyan csúcsai  -nek, hogy   és   között fut él,   és   között is fut él, viszont   és   között nem fut él (mivel   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:  , ,…,  és minden pontnak legyen nagyobb indexű szomszédja is. Ez megtehető: Ha elvesszük a gráfból a   és   csúcsokat, akkor   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  -en kívül. Legyen ez a csúcsunk  . Tehát most elvehetjük  ,  , és  -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  -et stb.

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

HivatkozásokSzerkesztés

  • 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ásokSzerkesztés

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