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 fokszáma és kromatikus száma közötti összefüggés. A tétel R.L Brooks-tól származik, aki 1941-ben publikálta On Coloring the Nodes of a Network könyvében.

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

$\chi(G)\le D(G).$

[szerkesztés] Megjegyzés

A kizárt esetekre az állítás nyilvánvalóan nem igaz.

[szerkesztés] Bizonyítás

$Δ(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 $Δ(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 $Δ(G)$ , viszont $x$ feltétlenül kisebb lesz mindkét komponensben $Δ(G)$ -nel. Ebből következik, hogy egyik komponens sem lehet $Δ(G)$ + 1 pontú teljes gráf. Tehát, az indukciós feltevésünk miatt, mindkét komponens kiszínezhető $Δ(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 $Δ(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 $Δ(G)$ marad, vagyis az indukciós feltevés miatt vagy mindkét komponens kiszínezhető $Δ(G)$ színnel, vagy legalább az egyik komponensünk egy $Δ(G)$ + 1 csúcsú teljes gráf. Ha színezhető mindkettő $Δ(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 $Δ(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 $Δ(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 $Δ(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 $Δ(G)$ . Csak $v n$ -nek lehet $Δ(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.

[szerkesztés] Hivatkozások

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.