Gráfok színezése

Egy 6 pontból álló gráf színezése 3 színnel.

A gráfelméletben gráfok színezésének nevezzük, amikor színeket (vagy számokat) rendelünk egy gráf csúcsaihoz, esetleg éleihez. Ez utóbbit a gráf élszínezésének nevezzük. Az élszínezés tekinthető az élgráf csúcsszínezésének is. A csúcsszínezés a kiindulópontja a színezéseknek, tulajdonképpen valamennyi színezést erre vezetnek vissza és ily módon tanulmányozzák.

Egy gráf jó színezése csúcsainak olyan színezése, ahol összekötött csúcsok eltérő színeket kapnak.

A szükséges színek számának megállapítása általában NP-nehéz probléma.

Nagyon sok megoldatlan kérdés van a gráfok színezése terén, viszont számtalan érdekes használata is van a gráfszínezésnek.

Rövid történeti áttekintés

Az első gráfszínezési eredmények síkbarajzolható gráfokkal voltak kapcsolatosak, a legfontosabb feladat térképek színezése volt. Amíg Anglia megyéit próbálták meg színekkel ellátni, Francis Guthrie megfogalmazta a négyszín-sejtést, miszerint 4 szín elegendő a különböző tartományok megfestéséhez, ha szomszédos tartományok különböző színeket kapnak. Guthrie testvére továbbította ezt a kérdést a matematikatanára, Augustus de Morgan felé, aki szintén megosztotta a sejtést William Hamiltonnal. Arthur Cayley 1879-ben vetette fel a problémát a London Mathematical Society egy találkozóján. Még ebben az évben Alfred Kempe nyilvánosságra hozta bizonyítását, és egy évtizeden át helyesnek ítélték. Ennek köszönhetően elismerésben is részesült, a Royal Society tagjává választották, és később ő vált a London Mathematical Society elnökévé is.

1890-ben Heawood belátta, hogy Kempe bizonyítása hibás volt. Bár jó megoldást ő nem talált a problémára, az ötszín-tételt sikerült belátnia, vagyis bármilyen síktérkép kiszínezhető 5-nél nem több színnel. Ehhez Kempe ötleteit használta fel. A következő évszázadban rengeteg ötlet merült fel, hogy sikerüljön ezt a számot 4-re leszorítani, végül csak 1976-ban sikerül Kenneth Appel-nek és Wolfgang Haken-nek helyes bizonyítást adnia. Meglepetésre Heawoord és Kempe elgondolásait használták fel, számottevő kiterjesztés nélkül. A négyszín-tétel bizonyítása volt az első számítógépre alapozott bizonyítás.

1912-ben George David Birkhoff vezette be a kromatikus polinomot a színezési problémák megsegítésére, amit Tutte általánosított Tutte-polinom néven. Kempe már 1879-ben felhívta a figyelmet a nem síkbeli esetre, és a 20. század elején több eredmény is napvilágot látott magasabb dimenziójú felületek kiszínezésének terén.

1960-ban Claude Berge megfogalmazott egy másik gráfszínezéssel kapcsolatos sejtést, az erős perfekt gráf tételt, ami Shannon információ-elméleti munkásságából eredeztethető. A sejtés 40 évig megoldatlan maradt, 2002-ben sikerült a Chudnovsky, Robertson, Seymour, Thomas által alkotott csoportnak belátnia.

A gráfszínezést az 1970-es évek óta tanulmányozták algoritmuselméleti problémaként. A kromatikus szám problémája egyike Karp 21 NP-teljes problémájának 1972-ből, nagyjából ebben az időben jelent meg több exponenciális-idejű algoritmus is mely a Zykov-kontrakción alapszik. Az egyik legjelentősebb alkalmazási terület, a fordítóprogramok regiszter-allokációja 1981-ben került bevezetésre.

A kromatikus szám

A Petersen-gráf kromatikus száma 3

Egy $G$ hurokmentes gráf k színnel színezhető, hogyha minden csúcsot ki lehet színezni k szín felhasználásával úgy, hogy bármely két szomszédos csúcs színe különböző legyen. $G$ kromatikus száma $\chi(G)=k$, ha $G$ k színnel kiszínezhető, de k-1 színnel nem. Egy ilyen színezésnél az azonos színt kapott pontok halmazát színosztálynak nevezzük.

Ha hurokél csatlakozna egy ponthoz, akkor azt a pontot nem lehetne kiszínezni. Másrészt a színezés szempontjából a többszörös élek nem játszanak szerepet, ezért ebben a szakaszban csak egyszerű gráfokkal foglalkozunk.

Élkromatikus szám

Egy $G$ gráf élei k színnel kiszínezhetők, hogyha minden élet ki lehet színezni k szín felhasználásával úgy, hogy bármely két szomszédos él színe különböző legyen. $G$ élkromatikus száma $\chi_e(G)=k$,,ha $G$ élei k színnel kiszínezhetők, de k-1 színnel nem.

Megjegyezzük, hogy az élkromatikus szám megegyezik a gráf élgráfjának kromatikus számával. Nyilvánvaló, hogy az élkromatikus szám nem lehet kisebb a maximális fokszámnál, hiszen az egy pontra illeszkedő éleket mind különböző színekre kell színezni. Viszont egyszerű gráfokra az élkromatikus szám ennél legfeljebb eggyel lehet nagyobb.

Kromatikus polinom

Ez a gráfot 3 színnel 12 féleképpen tudjuk kiszínezni.

A kromatikus polinom összeszámolja az összes lehetőséget, hogy hányféleképp lehet egy gráfot kiszínezni egy adott számnál nem több színnel. Például 3 színnel a jobb oldalon látható gráf 12 módon színezhető. Csak 2 színnel nem lehet kiszínezni. 4 színnel 24+4*12=72 féleképpen és az összes színt használva 4! színezés van. Így tehát a példa gráf lehetséges színezések számának táblázat így kezdődik:

Felhasználható színek száma	1	2	3	4	…
Színezések száma	0	0	12	72	…

Az n csúcsú egyszerű $G$ gráf kromatikus polinomja n-edfokú, egész együtthatós és az együtthatók váltakozó előjelűek (a 0-t megengedjük az együtthatók között), főegyütthatója 1 főegyütthatós, konstans tagja zérus.

Kromatikus polinomok néhány gráfra

$K_3$	$t(t-1)(t-2)$
$K_n$ teljes gráf	$t(t-1)(t-2) \cdots (t-(n-1))$
fagráf	$t(t-1)^{n-1}$
$C_n$ körgráf	$(t-1)^n+(-1)^n(t-1)$
Petersen-gráf	$t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)$

Tulajdonságok

A továbbiakban a kromatikus számról és az élkromatikus számról néhány nyilvánvaló illetve bonyolultabb összefüggést közlünk.

$\chi(G) = 1$ akkor és csak akkor ha a gráf független pontokból áll (éleket nem tartalmaz)

$\chi(G) = 2$ akkor és csak akkor ha $G$ páros gráf.

Bizonyítás: Ha a gráf páros, akkor az egyik oldalon levő pontokat pirossal, a másik oldalon levőket kékkel színezve 2 színnel színeztük a gráfot. Ha a gráfnak van legalább egy éle, akkor ennek a két végpontját nem színezhetjük ugyanolyan színűre így $\chi(G)=2$. Ha $\chi(G)$ akkor a két színosztály épp a páros gráf definíciójában szereplő felbontásnak megfelelő két halmaz lesz.

$\chi(G)$ $\geq$ $3$ ha $G$ tartalmaz páratlan kört.

$\chi(G)$ $\geq$ $\omega(G)$ minden $G$ gráfra (ahol $\omega(G)$ $G$ klikkszámát jelöli)

Ha van a gráfban egy klikk, akkor ennek semelyik két pontja nem lehet azonos színű. Ez az alsó korlát a kromatikus számra éles például olyankor, ha a gráf egy teljes gráf. Másrészt van olyan gráf is, amire nagyon rossz ez a korlát

Ha $\chi(G)$ = $\omega(G)$ minden feszített részgráfjára, akkor a gráf perfekt.

$\chi(G)$ $\leq$ $\Delta(G) + 1$ (ahol $\Delta(G)$ $G$ maximális fokszámát jelöli)

Mohó színezés alapján könnyen belátható

$\chi(K_n) = n$ ahol $K_n$ az $n$ csúcsú teljes gráfot jelöli.

Négyszín-tétel: Ha $G$ síkbarajzolható gráf, akkor $\chi(G)\le4$

Vizing-tétel: Ha $G$ egyszerű gráf, akkor $\Delta(G)\le\chi_e(G)\le\Delta(G)+1$

Brooks-tétel Ha $G$ egyszerű, összefüggő gráf, nem teljes gráf és nem egy páratlan hosszúságú kör, akkor a kromatikus szám nem nagyobb, mint a maximális fokszám.

Mycielski-konstrukció: Minden $k$ $\geq$ $2$ egész számra van olyan $G_k$ gráf, hogy $\omega(G_k)=2$ és $\chi(G_k)=k$

Algoritmusok

Hatékony algoritmus

Annak meghatározása, hogy egy gráf két színnel színezhető-e, ekvivalens azzal, hogy meghatározzuk a gráf páros-e vagy sem, és eképp polinomidőben számítható. Általánosabban a kromatikus szám és a megfelelő színezés perfekt gráfok esetében megadható polinomidőben. Zárt formula is létezik sok gráftípusra például erdőre, körökre.

Brute-force keresés

Brute-force keresés egy $k$ színnel való kiszínezésnél szükséges az összes $\scriptstyle\binom{n}{k}$ csúcsszínezést és meg kel nézni, hogy a kapott színezés jó-e. Ahhoz, hogy kiszámítsuk a kromatikus számot és polinomot meg kell ismételni ezt az eljárást minden $k$-ra. Ennek futási ideje $O((n+1)!)$, következésképpen ezt csak kis gráfoknál praktikus használni.

Kontrakció

Egy G gráf $G/uv$ kontrakciója a G-hez egy olyan gráfot rendel, melyben az $u$ és $v$ közötti éleket elhagyjuk és a két csúcsot egy darab $w$ csúccsal helyettesítjük, ahol az összes él, aminek valamelyik végpontja $u$ és $v$ volt, kontrakció után a végpontja $w$ lesz. Ez a művelet fontos szerepet játszik a gráfok színezésének vizsgálatában.

A kromatikus szám kielégíti az alábbi rekurziót: $P(G-uv, k)= P(G/uv,k)+ P(G,k)$ Zykov szerint, ahol $u$ és v nemszomszédos csúcsok a $G+uv$ az a gráf, ahol $u$ és $v$ között egy él fut. Több algoritmus is azon alapszik, hogy ezen a rekurzió kiszámításán alapszik. A számítás eredményével kapott fa a Zykov-fa. A futási idő $u$ és $v$ megválasztásától függ.

A kromatikus polinom az alábbi rekurzív formulát elégíti ki:

$P(G-uv, k)= P(G/uv,k)+ P(G,k)$

ahol $u$ és $v$ szomszédos csúcsok $G-uv$ az a gráf, amit $uv$ elhagyásával kapunk. $P(G - uv, k)$ pedig az összes lehetséges színezését adja a gráfnak, ahol egy színt használhatunk többször is. A jó színezések száma ezen a módon két gráf színezésének összegeként áll elő: ha $u$ és $v$ különböző színűek, akkor tekinthetjük azt a gráfot, ahol $u$ és $v$ szomszédosak. Ha $u$ és $v$ azonos színűek, akkor pedig azt a gráfot nézzük ahol $u$ és $v$ kontrakcióban van.

Tutte kíváncsisága, hogy mely egyéb gráf tulajdonságok elégítik ki ezt a rekurziót, vezette el őt a róla elnevezett polinomhoz.

Mohó színezés

Két mohó színezése ugyanannak a gráfnak, a csúcsokon különböző sorrendben haladva.

A mohó színezés a csúcsok egy $v_1$,…,$v_n$ sorrendjét veszi és $v_i$-hoz azt a legkisebb színt rendeli hozzá, amit a $v_i$ szomszédai a $v_1$,…,$v_{i-1}$ nem használtak el. Ha nincs ilyen szín, akkor egy új színt rendel hozzá. A kapott színezés minősége a sorrendtől függ. Azonban létezik olyan sorrend a mohó színezésnél, amivel $\chi(G)$ színnel ki tudjuk színezni a gráfot. Másrészt a mohó színezéssel lehetséges, hogy kevésbbé jó színezést kapunk. Például a koronagráfok esetében. Ha a csúcsok fokszám szerint vannak csökkenő sorrendben a mohó színezés legfeljebb $n$ színt alkalmaz, vagyis 1-gyel többet mint a maximális fokszám. Ezt a sorrendválasztást szokták Welsh–Powell algoritmusnak nevezni. Másik lehetőség a sorrendet dinamikusan választja meg, az algoritmus futása közben. Ebben a soron következő lépésnek mindig azt a csúcsot választja, aminek a szomszédai közt a legtöbb szín szerepel. Ezeket az algoritmusokat gyűjtőnevükön szekvenciális színező algoritmusoknak nevezzük.

Alkalmazások

Színezés tulajdonképpen egy konfliktusmentes hozzárendelés, a gyakorlati alkalmazások során a célfüggvények: színek számának, színek összegének a minimalizálása.

A csúcsszínezés több időbeosztásos problémához alkalmazható. Legegyszerűbb eset munkák csoportjának meg kell határozni az időbeosztását. Minden munka egy időpontot foglal el. A munkákat akármilyen sorrendben végrehajthatjuk, de bizonyos munkák nem történhetnek azonos időben, mert például azonos munkaerő szükségeltetik hozzá. A megfelelő gráf ekkor egy munkának egy csúcsot feleltet meg és akkor fut él két csúcs között, ha a megfelelő két munka nem történhet ugyanabban az időpontban. A kromatikus szám éppen Az időbeosztási probléma részletei megadják a gráf struktúráját. (Amikor repülőgépekhez kell járatokat rendelni a kapott gráf egy intervallum gráf lesz és az intervallumgráfok színezésére ismert lineáris idejű algoritmus.)

Az élszínezést kétprocesszoros feladatok ütemezésére alkalmazzák, ekkor a gráf csúcsai a processzorok, a színek a lehetséges időpontok, a gráf élei pedig a két processzor együttes munkáját igénylő feladat.

Egyéb alkalmazások például a mintaillesztés vagy éppen a népszerű szúdoku rejtvény is tekinthető egy 81 csúcsú gráf 9 színnel való színezésének.

Egyéb színezések

Ramsey-elmélet

A „nem megfelelő színezések” egy fontos területét a Ramsey-elmélet tanulmányozza. A Ramsey-elmélet Frank Plumpton Ramsey matematikus–közgazdász harmincas években publikált eredménye által elindított igen fontos ága a kombinatorikanak és a gráfelméletnek. Az elméletet összefűző filozófiat nagyon egyszerűen meg lehet fogalmazni: Ha egy struktúra hatalmas, akkor az nem kerülheti el az igen szabályos nagy részstruktúrákat.

Ennek egyik része, hogy a gráf éleihez rendelünk színeket és nincs megkötés az közös csúcsban találkozó élek színére. Ramsey-tétel legegyszerűbb esete a $K_6$ éleit tetszőlegesen megszínezve két színnel biztosan keletkezik benne egyszínű háromszög.

Egyéb színezések

Listaszínezés

Minden csúcshoz egy listáról választunk ki egy színt

Totális színezés

Minden él és minden csúcs színezve van

Multiszínezés

minden csúcsra adott egy szám, ennyi színt kell neki adni úgy, hogy szomszédos színhalmazok diszjunktak legyenek.

Ívszínezés

Lista-élszínezés

Harmonikus-színezés

T-színezés

Erős színezés

Összeg színezés

Hivatkozások

• Katona, Recski, Szabó "A Számítástudomány alapjai." Typotex. Budapest, 2006.
• Gráfok színezése (angolul)
• [1]
• [2]
• Gráfszínezési problémák és ütemezési alkalmazásaik
• Gráfelmélet