4. Gráfok színezése
Páros gráfok definíciója
A $G$ gráfot páros gráfnak nevezzük, ha a $V(G)$ csúcshalmáza felbontható az $A$ és $B$ diszjunkt halmazok egyesítésére úgy, hogy $G$ minden éle egy $A$-béli csúcsot köt össze egy $B$-bélivel.
Jelölés: Ilyenkor a szokásos $G = (V,E)$ helyett a $G = (A,B;E)$ jelölést használjuk.
Strukturális felépítés
A páros gráfokban nincsenek halmazon belüli élek, minden kapcsolat a két csoport (partíció) között jön létre.
A fák mindegyike páros gráf.
Páratlan körök és párosság
A $G$ gráf akkor és csak akkor páros gráf, ha nem tartalmaz páratlan hosszú kört.
Bizonyítás
I. irány ($\implies$):
Ha $G = (A,B;E)$ páros gráf, akkor nem tartalmazhat páratlan kört. Mivel minden él $A$ és $B$ között vezet, egy $a \in A$ csúcsból indulva páratlan sok lépés után csak $B$-beli csúcsba érhetünk, így páratlan sok él után nem térhetünk vissza $a$-ba.
II. irány ($\impliedby$):
Tegyük fel, hogy $G$ nem tartalmaz páratlan kört. Fussunk le egy BFS algoritmust egy tetszőleges $s$ csúcsból. Legyen:
- $A = \{v \in V(G) \mid t(v) \text{ páros}\}$
- $B = \{v \in V(G) \mid t(v) \text{ páratlan}\}$
Azt kell megmutatnunk, hogy tetszőleges $\{u,v\}$ él esetén $u$ és $v$ paritása különböző. BFS során belátható, hogy $|t(u) - t(v)| \leq 1$. Ha $t(u) = t(v)$ lenne, akkor az $u$-ból és $v$-ből az $s$ felé induló utak egy közös $w$ csúcsnál találkoznának, és egy $2k+1$ hosszú páratlan kört alkotnának, ami ellentmondás.
BFS alapú partíció
A távolságok ($t(v)$) paritása határozza meg, hogy egy csúcs melyik halmazba kerül.
Konklúzió: A nem összefüggő gráfokra az állítás komponensenként alkalmazható. Minden $K_i$ komponens páros gráf, így az egész gráf is az.
Gráfszínezés és kromatikus szám
Legyen $G$ egy gráf és $k \geq 1$ egész szám. A $G$ gráf $k$ színnel színezhető, ha $G$ minden csúcsát kiszínezhetjük $k$ adott (tetszőleges) szín valamelyikével úgy, hogy $G$ bármely két szomszédos csúcsának a színe különböző.
A $G$ kromatikus száma $k$, ha $G$ $k$ színnel színezhető, de $(k-1)$-gyel már nem. $G$ kromatikus számának a jele: $\chi(G)$.
A színezhetőség elve
A szomszédos pontok soha nem kaphatják ugyanazt a színt. A kromatikus szám a legkevesebb szín, amivel ez megoldható.
Példafeladat: Kromatikus szám
6.2. Feladat
Határozzuk meg az alábbi $G$ gráf kromatikus számát, $\chi(G)$-t!
Megoldás
Három színnel könnyen megszínezhetők a gráf csúcsai például úgy, ahogyan a 6.1. ábrán látható.
Miért nem elegendő két szín?
Két szín viszont biztosan nem volna elegendő: mivel (például) az $a, d$ és $e$ csúcsok közül bármely kettő szomszédos, ezért már ezekre is három különböző színt kell használnunk.6.1. ábra: Érvényes 3-színezés
A mohó színezés korlátai
Minden $k \geq 1$ egész esetén létezik olyan ($2k$ csúcsú) $G$ gráf és a $G$ csúcsainak egy olyan sorrendje, hogy $\chi(G) = 2$, de a mohó színezést a $G$-re a csúcsoknak ebben a sorrendjében futtatva az eljárás $k$ színt használ.
Konstruktív bizonyítás
Készítsük el azt a páros gráfot, aminek a két pontosztálya $A = \{a_1, a_2, \dots, a_k\}$ és $B = \{b_1, b_2, \dots, b_k\}$. Minden $1 \leq i \leq k$ esetén az $a_i$-t kössük össze a $b_i$-n kívül minden más $b_j \in B$ ($j \neq i$) csúccsal, de $b_i$-vel ne (lásd a 6.3. ábrát).
A színezési folyamat: $(a_1, b_1, a_2, b_2, \dots, a_k, b_k)$
Az $a_1$ és $b_1$ az 1. színt kapják, mert nem szomszédosak.
Mivel $a_2$ és $b_2$ már szomszédosak $b_1$-gyel, illetve $a_1$-gyel, de egymással nem, ezért a 2. színt kapják.
Hasonlóan: minden $1 \leq i \leq k$ esetén $a_i$-nek és $b_i$-nek az eljárás az $i$. színt adja, mert mindketten szomszédosak az 1., 2., ..., ($i-1$). színt kapott csúcsokkal (de egymással nem).
Így a mohó színezés végül valóban $k$ színnel színezi ki a gráfot, miközben $\chi(G) = 2$ valóban igaz, hiszen a gráf páros.
6.3. ábra: Ellenpélda gráf
Páros gráf konstrukciója a mohó algoritmus teszteléséhez
A maximális fokszám és a színezés kapcsolata
Legyen $G$ (hurokélmentes) gráf és jelölje $\Delta(G)$ a $G$-béli maximális fokszámot. Ekkor a mohó színezést a csúcsok tetszőleges sorrendjében végrehajtva az legföljebb $\Delta(G)+1$ színt használ.
Azt kell megmutatni, hogy a mohó színezést lefuttatva $C$ értéke nem növekszik $\Delta(G) + 1$ fölé. Tegyük fel, hogy $C$ már elérte a $C = \Delta(G)+1$ értéket és a soron következő csúcs a $v_i$.
Mivel tehát $C > \Delta(G)$, ezért kell létezzen olyan $t \in \{1, \dots, C\}$ szín, amit a mohó eljárás (a paletta bővítése nélkül) $v_i$-nek adhat.
A színpaletta és a fokszám viszonya
Ha a csúcsnak legfeljebb $\Delta(G)$ szomszédja van, egy $\Delta(G)+1$ méretű palettán mindig marad szabad szín.
Minden (hurokélmentes) $G$ gráfra $\chi(G) \leq \Delta(G)+1$.
Mivel a mohó színezés $\Delta(G)+1$ színnel kiszínezi $G$-t, a kromatikus szám ($\chi(G)$) értéke ennél több nem lehet.
Vizuális algoritmus-elemzés
Felső korlát
Bármilyen sorrendet választunk, a mohó színezés sosem lépi át ezt az értéket:
Hatékonysági rés
A mohó algoritmus "rossz" sorrend esetén elpazarolhatja a színeket:
Hogyan téved a mohó algoritmus?
Kezdeti lépés ($a_1, b_1$)
Mivel $a_1$ és $b_1$ nem szomszédosak, mindketten megkapják az 1. színt.
Kényszerpálya ($a_2, b_2$)
Szomszédosak az 1. színt kapott csúcsokkal, de egymással nem, így kénytelenek a 2. színt felvenni.
Végállapot
Minden újabb pár új színt követel, így az algoritmus $k$ színt használ egy amúgy 2-színezhető gráfon.
A tanulság
Bár a mohó algoritmus gyors, az eredménye sorrendfüggő. A $\Delta(G)+1$ korlát biztonságot ad, de nem garantálja az optimális $\chi(G)$ értéket.
A klikkszám fogalma
A $G$ gráf klikkszáma $k$, ha $G$-ben található $k$ darab csúcs úgy, hogy ezek közül bármely kettő szomszédos, de $k+1$ ilyen csúcs már nem található.
Hogyan ismerjük fel a klikket?
A klikk nem más, mint egy teljes részgráf (mindenki mindenkivel össze van kötve). Az alábbi ábrán egy olyan gráfot látsz, ahol a legnagyobb teljes részgráf 4 csúcsból áll.
Összefüggés a klikkszám és a színezhetőség között
Minden (hurokélmentes) $G$ gráfra $\omega(G) \leq \chi(G)$ teljesül.
$G$-ben található $\omega(G)$ darab csúcs, amik közül bármely kettő szomszédos.
Így $G$ minden színezése legalább $\omega(G)$ színt használ, amiből $\omega(G) \leq \chi(G)$ valóban következik.
Vizuális szemléltetés
Egy 3-as klikk ($K_3$) jelenléte a gráfban azonnal kikényszeríti legalább 3 különböző szín használatát.
Mivel a klikk minden pontja szomszédos, a klikk mérete megadja a színezéshez szükséges színek minimumát.
Gyakorló feladat: $\omega(G)$ és $\chi(G)$ vizsgálata
6.12. Feladat
Határozzuk meg az alábbi $G$ gráfok $\omega(G)$ klikkszámát és $\chi(G)$ kromatikus számát!
1 Bal oldali gráf elemzése
Klikkszám: Könnyű találni négy csúcsot, amik közül bármely kettő szomszédos: például $\{a, b, e, f\}$. Ebből $\omega(G) \geq 4$ következik. Öt méretű klikk ($K_5$) már nem található a gráfban.
Kromatikus szám: A gráf kiszínezhető négy színnel (pl. $a, c$ piros; $b, d$ kék; $e, g$ zöld; $f, h$ sárga). Mivel találtunk benne 4-es klikket, 4-nél kevesebb szín biztosan nem elég.
2 Jobb oldali gráf elemzése
Kromatikus szám: A gráf tartalmaz egy 5 hosszúságú kört ($C_5$). Mivel a páratlan körök nem 2-színezhetőek, $\chi(G) \geq 3$. Három színnel a gráf már kiszínezhető, tehát $\chi(G) = 3$.
Klikkszám: Ebben a gráfban nincsenek háromszögek, így a legnagyobb teljes részgráf mérete 2 (maguk az élek).
Számhalmazok kromatikus száma
6.13. Feladat
A $G$ gráf csúcsai legyenek az $1$ és $1000$ közé eső természetes számok. Két különböző csúcsot akkor kössünk össze, ha a különbségük legföljebb $9$. Mennyi $G$ kromatikus száma?
Felső korlát: 10-színezés
Adjunk minden $n$ számhoz egy színt az utolsó számjegye alapján (maradékosztályok modulo $10$).
Bármely két azonos színű szám különbsége legalább $10$, tehát nem szomszédosak. Ebből következik: $\chi(G) \leq 10$.
Alsó korlát: A 10-es klikk
Vizsgáljuk az $\{1, 2, \dots, 10\}$ részhalmazt. Itt bármely két szám különbsége legfeljebb $9$.
Mivel a gráfban van $10$-es klikk, a színezéshez legalább $10$ szín kell: $\chi(G) \geq \omega(G) = 10$.
Konklúzió
$\chi(G) = 10$
Intervallumgráfok
A $G$ egyszerű gráfot akkor nevezzük intervallumgráfnak, ha léteznek a számegyenesen olyan $I_1, I_2, \dots, I_n \subseteq \mathbb{R}$ (korlátos és zárt) intervallumok, hogy $G$ ezekből megkapható a következő módon:
- $G$ csúcsai megfelelnek az intervallumoknak;
- két különböző csúcs pontosan akkor szomszédos $G$-ben, ha a két megfelelő intervallumnak van közös pontja.
Ilyenkor azt mondjuk, hogy az $\{I_1, \dots, I_n\}$ intervallumrendszer reprezentálja a $G$ intervallumgráfot.
Vizuális reprezentáció
Az 1 és 2 szomszédosak, mert intervallumaiknak van közös pontja. 1 és 3 nem szomszédosak.
Gyakorlat: Intervallumgráf-e?
6.16. Feladat
Döntsük el az alábbi gráfokról, hogy intervallumgráfok-e!
A bal oldali gráf intervallumgráf
A bal oldali gráf intervallumgráf, mert reprezentálja (például) a következő intervallumrendszer:
- $a = [0, 1]$
- $b = [0, 3]$
- $c = [4, 7]$
- $d = [6, 7]$
- $e = [0, 5]$
- $f = [2, 7]$
A jobb oldali gráf nem intervallumgráf
Ennek oka a $b, e, c$ és $f$ csúcsok alkotta négy pontú körben rejlik.
Tegyük fel, hogy mégis intervallumgráf! Mivel $b$ és $f$ nem szomszédosak, $I_b$ és $I_f$ diszjunktak kell legyenek (legyen $b_2 < f_1$).
Mivel $c$ szomszédos $b$-vel és $f$-fel is, $I_c$-nek metszenie kell mindkettőt $\implies [b_2, f_1] \subseteq I_c$. Ugyanez igaz $e$-re is $\implies [b_2, f_1] \subseteq I_e$.
Optimális színezési stratégia
Legyen $G$ intervallumgráf, amit az $\{I_1, I_2, \dots, I_n\}$ intervallumrendszer reprezentál. Ha az intervallumokat a bal oldali végpontjuk szerinti növekvő sorrendbe rendezzük, és ezen sorrendben hajtjuk végre a mohó színezést, akkor az eljárás optimális színszámú, $\chi(G)$ színezést ad.
Tegyük fel, hogy az intervallumok már rendezettek: $a_1 \le a_2 \le \dots \le a_n$. Legyen $k$ a mohó eljárás által használt színek száma. Azt kell belátnunk, hogy létezik $k$ csúcsú klikk a gráfban.
Legyen $I_j$ az az intervallum, ami először kapta meg a $k$-adik színt, és legyen $t = a_j$ ennek a bal oldali végpontja.
Mivel $I_j$ nem kaphatott $1, 2, \dots, k-1$ közötti színt, lennie kell olyan szomszédos $I_{i_1}, I_{i_2}, \dots, I_{i_{k-1}}$ intervallumoknak, amiket korábban már kiszíneztek ezekkel a színekkel.
A rendezés miatt ezen intervallumok bal oldali végpontjára $a_{i_m} \le t$ teljesül, mivel pedig metszik $I_j$-t, a jobb oldali végpontjukra $b_{i_m} \ge t$ adódik.
Ebből következik, hogy mind a $k$ darab intervallum tartalmazza a $t$ pontot, tehát klikket alkotnak a gráfban, így $\chi(G) = k$.
Vizuális bizonyítás: A "kényszerített" szín
Minden korábban színezett intervallum áthalad a $t$ ponton, így klikket alkotnak.
Az intervallumgráfok tökéletessége
Ha $G$ intervallumgráf, akkor rá $\omega(G) = \chi(G)$ teljesül.
A korábbi tétel bizonyításában megmutattuk, hogy minden intervallumgráf esetén létezik olyan $k$ szám, amire $G$ megszínezhető $k$ színnel, és $G$ tartalmaz $k$ csúcsú klikket.
A színezésből adódóan:
$\chi(G) \leq k$
A klikk létezéséből adódóan:
$\omega(G) \geq k$
Az állításokból a következő egyenlőtlenség-sorozat adódik:
$k \leq \omega(G) \leq \chi(G) \leq k$
amiből tehát $\omega(G) = \chi(G)$ valóban következik.
Intervallumgráfok struktúrája
Míg általános gráfoknál a klikkszám csak alsó korlátja a színezhetőségnek, az intervallumgráfoknál ez a két érték mindig megegyezik.
Színezési Kihívás: Találd meg a $\chi(G)$-t!
Paletta választó
Kattints egy színre, majd a csúcsra!
Intervallumgráf-építő Labor
Húzd a szakaszokat vagy a végpontjaikat! Két csúcs akkor lesz szomszédos, ha a szakaszok metszik egymást.
Összefoglaló Kvíz
Kromatikus kihívás
Vidd az egeret a kártyák fölé a helyes válaszért!
#01 Párosság
Milyen strukturális feltétel mellett színezhető egy gráf pontosan 2 színnel?
#02 Mohó korlát
Mi a mohó színezés által garantált felső korlát a színek számára?
#03 Klikk-reláció
Miért igaz általános gráfokra, hogy $\omega(G) \leq \chi(G)$?
#04 Intervallumgráfok
Hogyan érhető el az optimális színezés egy intervallumgráf esetén a mohó algoritmussal?
Tudtad-e?
A Sudoku valójában egy gráf
A Sudoku nem más, mint egy 81 csúcsú gráf színezése 9 színnel. Két csúcs akkor szomszédos, ha egy sorban, oszlopban vagy $3 \times 3$-as blokkban vannak. A játék célja megtalálni a gráf egy érvényes 9-színezését a megadott "szín-töredékek" alapján.
A négyszín-sejtés diadala
Ez volt az első nagy matematikai tétel, amit 1976-ban számítógéppel bizonyítottak be. Azt állítja, hogy bármely síkba rajzolt térkép tartományai kiszínezhetők legfeljebb 4 színnel úgy, hogy a szomszédos országok színe különböző legyen.
Regiszter-allokáció
Amikor a számítógéped egy programot futtat, a "fordítóprogram" (compiler) gráfszínezést használ. A változók a csúcsok, és akkor szomszédosak, ha egyszerre van szükség rájuk. A színek a processzor szűkös regisztereit jelentik – a cél minél kevesebb regiszterrel megoldani a futtatást.
Klikkek és a titkosszolgálat
A hálózatelemzők klikk-kereső algoritmusokat használnak a közösségi médiában vagy a híváslistákban, hogy azonosítsák a szorosan együttműködő csoportokat. Mivel a maximális klikk ($\omega(G)$) megtalálása rendkívül nehéz feladat, ez a terület a modern kriptográfia egyik kulcskérdése.