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
Háromszögmentes gráfok nagy kromatikus számmal (Zykov-konstrukció)
Minden $k \geq 2$ esetén létezik olyan $G_k$ gráf, amelyre $\omega(G_k) = 2$ (azaz nem tartalmaz háromszöget) és $\chi(G_k) = k$.
Induktív Bizonyítás (Zykov, 1949)
Alapesetek: Ha $k = 2$, legyen $G_2 = K_2$ (egyetlen él, $\omega=2, \chi=2$). Ha $k = 3$, legyen $G_3 = C_5$ (ötcsúcsú kör, $\omega=2, \chi=3$).
Induktív lépés ($k \to k+1$): Tegyük fel, hogy $G_k$ már létezik $\omega(G_k) = 2$ és $\chi(G_k) = k$ tulajdonságokkal.
- Vegyük $G_k$-nak $k$ darab diszjunkt példányát: $V_1, V_2, \dots, V_k$.
- Minden lehetséges $(v_1, v_2, \dots, v_k) \in V_1 \times V_2 \times \dots \times V_k$ csúcs-k-ashoz vegyünk fel egy új $z$ csúcsot.
- Ezt a $z$ csúcsot kössük össze a k-as minden elemével ($v_1, v_2, \dots, v_k$-val). A kapott gráf a $G_{k+1}$.
Nem elég $k$ szín: Indirekt, ha elég lenne, minden $V_i$-ben mind a $k$ színnek szerepelnie kéne. Válasszunk minden $V_i$-ből egy $i$-edik színű $v_i$ csúcsot. A hozzájuk tartozó $z$ is valamilyen $j$ színt kapott, így szomszédos lenne egy azonos színű $v_j$-vel. Ellentmondás!
Az Algoritmus Leírása: Mohó Színezés
Bemenet: $G = (V, E)$ gráf, $v_1, v_2, \dots, v_n$ csúcssorrend.
// C a jelenleg használt színek száma
1. C $\leftarrow$ 1; c($v_1$) $\leftarrow$ 1
2. ciklus: i fut 2-től n-ig
3. t $\leftarrow$ legkisebb szín $\in \{1,\dots,C,C+1\}$, amelyre $v_i$-nek nincs t-színű szomszédja
4. c($v_i$) $\leftarrow$ t; ha t = C+1: C $\leftarrow$ C+1
5. ciklus vége
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.