Gráfok színezése

A matematika, azon belül a gráfelmélet területén a gráfok színezése a gráfcímkézés speciális esete: bizonyos megszorítások mentén „színeket” (vagy számokat) rendelünk hozzá egy gráf valamilyen alkotóelemeihez. A leggyakoribb formájában a gráf csúcsaihoz történik a hozzárendelés, ez csúcsszínezés vagy egyszerűen színezés. Ha a gráf éleihez rendelünk színeket, az a gráf élszínezése, ha pedig a csúcsok és az élek is színezésre kerülnek, totális színezésről beszélhetünk. Síkbarajzolható gráf tartományszínezésénél pedig a lerajzolás tartományaihoz rendelünk színeket.

A Petersen-gráf jó csúcsszínezése 3 színnel, ami a legkevesebb lehetséges szín (kromatikus szám=3).

A gráfszínezéseknél jó színezésnek azt tekintjük, ha a szomszédos elemek (csúcsszínezésnél az egymással összekötött csúcsok, élszínezésnél az egy csúcsból kiinduló élek, tartományszínezésnél a közös határral rendelkező területek) különböző színűek. Színezés alatt külön jelző nélkül is általában jó színezés értendő.

A gráfok színezése területének kiindulópontjában a csúcsszínezés áll, és a többi színezési probléma is visszavezethető csúcsszínezésre: például egy gráf élszínezése megegyezik élgráfjának, totális színezése totális gráfjának, síkgráf tartományszínezése pedig duálisának csúcsszínezésével. Mégis, a nem-csúcsszínezési problémákat gyakran eredeti változatukban vizsgálják – ennek oka a perspektíva, egyes problémák, mint az élszínezés, egyszerűen jobban átláthatók, jobban kezelhetők eredeti formájukban.

A színek hozzárendelésének hagyománya a térképek országainak színezéséből ered, ahol a tartományokat szó szerint kiszínezték. Ezt általánosították a síkba ágyazott gráf tartományainak színezésére. A dualitás miatt ebből csúcsok színezése lett, amit aztán minden gráfra általánosítottak. A matematikai és számítógépes megvalósításokban jellemzően az első néhány pozitív vagy nemnegatív számot használják „színekként”. Bármilyen véges halmaz alkalmas lehet „színhalmaznak” – a színezési probléma természete csak a színek számosságán múlik, nem a minőségükön.

A gráfszínezés területén számos gyakorlati alkalmazással, még több elméleti kihívással lehet találkozni. A klasszikusnak mondható problémák mellett különböző korlátok állíthatók fel a szóba jövő gráfra, a szín hozzárendelésének módjára vagy a színre magára. Jelenleg is igen aktívan kutatott terület.

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

Bővebben: Négyszín-tétel

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 Rowan 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 Appelnek és Wolfgang Hakennek 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.

Definíció és terminológia

Ez a gráf 12-féleképpen színezhető ki 3 színnel.

Csúcsszínezés

Ha egyéb jelző nélkül egy gráf színezését említjük, csaknem mindig a gráf jó csúcsszínezése értendő alatta, tehát a gráf csúcsainak színekkel való olyan címkézése, melyben ugyanazon éllel érintkező két csúcs színe mindig különböző. Ha egy csúcsból hurokél indulna ki, a gráfnak nem létezhetne jó csúcsszínezése, ezért ebben a szakaszban csak hurokmentes gráfokat veszünk figyelembe.

A csúcsok címkézésénél a színek használata a térképek színezésére vezethető vissza. Ha csak 2-3 szín fordul elő, piros, kék stb. címkéket használnak, de általában úgy tekintik, hogy a címkék az {1, 2, 3, ...} egész számok közül kerülnek ki.

Az olyan színezést, ami legfeljebb k színt használ, (jó) k-színezésnek neveznek. Az a legkisebb k szám, amire a G gráfnak van jó k-színezése, a gráf kromatikus száma (színezési száma), amit általában χ(G)-vel jelölnek. Néha az γ(G) jelölést is használatos, mivel a χ(G) a gráf karakterisztikáját is jelöli. Az olyan gráf, amihez tartozik (jó) k-színezés, k-színezhető, továbbá k-kromatikus, amennyiben kromatikus száma pontosan k.

A színezésnél azonos színt kapott csúcsok halmazát színosztálynak neveznek. Minden színosztály független csúcshalmazt alkot, tehát egy gráf k-színezése ugyanazt jelenti, mint csúcsainak k független csúcshalmazba való osztása, ezért a k-színezhető és a k-részes gráf fogalmak ugyanazt jelentik.

Kromatikus polinom

A 3 csúcsú nem izomorf gráfok és a hozzájuk tartozó kromatikus polinomok. Az E₃ üres gráf (piros) 1-színezhető, a többi nem. A zöld gráfnak 12 3-színezése létezik.

Bővebben: Kromatikus polinom

Egy gráf kromatikus polinomja megszámolja a gráf adott számú színnel történő csúcsszínezéseinek lehetőségét. Például a jobb oldalon látható gráfot három színnel tizenkétféleképpen lehet kiszínezni, két színnel egyáltalán nem lehetséges a színezés, négy színnel pedig 24 + 4⋅12 = 72-féleképpen lehetséges a színezés: mind a négy színt felhasználva 4! = 24 érvényes színezés lehetséges (bármely 4 csúcsú gráfban egy mind a 4 színt felhasználó színezés jó színezés); a négy színből hármat választva pedig 12 érvényes 3 színezés található. Így tehát a példagráf lehetséges színezések számának táblázata így kezdődik:

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

A kromatikus polinom olyan P(G, t) függvény, ami G t-színezéseit számolja meg. Ahogy a neve is mutatja, adott G esetén a függvény valóban t polinomja. A példagráf esetén P(G, t) = t(t − 1)²(t − 2), és valóban, P(G, 4) = 72.

A kromatikus polinom minimálisan annyi információt hordoz G gráf színezhetőségéről, mint a kromatikus szám. Valójában χ az a legkisebb pozitív egész szám, ami nem gyöke a kromatikus polinomnak:

${\displaystyle \chi (G)=\min\{k\,\colon \,P(G,k)>0\}.}$

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

Néhány gráf kromatikus polinomja

${\displaystyle K_{3}}$ háromszög	${\displaystyle t(t-1)(t-2)}$
${\displaystyle K_{n}}$ teljes gráf	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
n csúcsú fagráf	${\displaystyle t(t-1)^{n-1}}$
${\displaystyle C_{n}}$ körgráf	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Petersen-gráf	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Élszínezés

Bővebben: Élszínezés

Egy gráf élszínezése alatt éleinek jó színezése értendő, olyan színezés tehát, ahol egyetlen csúcs sem illeszkedik két azonos színű élre. A k színnel történő jó élszínezést k-élszínezésnek nevezik, és ekvivalens az élhalmaz k párosításra történő szétosztásával (particionálásával). Az a legkisebb k szám, amire a G gráfnak van jó k-élszínezése, a gráf élkromatikus száma vagy kromatikus indexe, amit χ′(G)-vel jelölnek. Tait-színezésnek a 3-reguláris gráfok 3-élszínezését nevezik. A négyszín-tétel azzal az állítással ekvivalens, miszerint minden síkbarajzolható 3-reguláris hídmentes gráfnak létezik Tait-színezése.

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.

Totális színezés

Bővebben: Totális színezés

A totális színezés során a gráf csúcsaihoz és éleihez is színeket rendelnek. Ha külön nem jelölik, általában jó totális színezésről van szó, amikor a gráfnak sem érintkező élei, sem valamely élének végpontjai nem lehetnek azonos színűek. A χ″(G) totális kromatikus szám a G totális színezéséhez szükséges legkevesebb szín száma.

Tulajdonságok

A kromatikus számra vonatkozó korlátok

Ha minden csúcsot különbözőre színezünk, az mindig jó színezés, ezért:

${\displaystyle 1\leq \chi (G)\leq n.}$

Az 1-színezhető gráfok – ${\displaystyle \chi (G)=1}$ – pontosan megegyeznek az élmentes gráfokkal, a 2-színezhetőek – ${\displaystyle \chi (G)=2}$ – pedig az éllel rendelkező páros gráfokkal (köztük a fákkal, illetve erdőkkel). ${\displaystyle \chi (G)}$ ${\displaystyle \geq }$ ${\displaystyle 3}$ ha ${\displaystyle G}$ tartalmaz páratlan kört. Az n csúcsú ${\displaystyle K_{n}}$ teljes gráfok színezéséhez ${\displaystyle \chi (K_{n})=n}$ színre van szükség. Egy optimális színezésben a gráf m' éle közül legalább egy él húzódik minden színosztály-pár között, ezért:

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.}$

Ha G tartalmaz k méretű klikket, annak színezéséhez legalább k színre van szükség – a kromatikus szám tehát legalább akkora, mint az ${\displaystyle \omega (G)}$ klikkszám:

${\displaystyle \chi (G)\geq \omega (G).}$

Ez az egyenlőtlenség perfekt gráfokra (így teljes gráfokra is) éles – ugyanis ha a gráf perfekt ${\displaystyle \chi (G)}$ = ${\displaystyle \omega (G)}$ minden feszített részgráfjára – néhány gráfra viszont nagyon rossz becslést ad.

A négyszín-tétel alapján minden síkbarajzolható gráf 4-színezhető – ${\displaystyle \chi (G)\leq 4}$.

Mohó színezéssel megmutatható, hogy minden gráf kiszínezhető maximális fokszámánál legfeljebb 1-gyel több színnel:

${\displaystyle \chi (G)\leq \Delta (G)+1.}$

Teljes gráfok esetében ${\displaystyle \chi (G)=n}$ és ${\displaystyle \Delta (G)=n-1}$, páratlan körökre pedig ${\displaystyle \chi (G)=3}$ és ${\displaystyle \Delta (G)=2}$, tehát ezekre a gráfokra a korlát a lehető legjobb. Más esetekben kissé javítható; a Brooks-tétel^[1] szerint:

${\displaystyle \chi (G)\leq \Delta (G)}$ a G összefüggő, egyszerű gráfra, kivéve ha G teljes gráf vagy páratlan kör.

A kromatikus számra vonatkozó alsó korlátok

Az évek során a kromatikus szám több alsó korlátját felfedezték:

Hoffman-féle korlát: Legyen ${\displaystyle W}$ valós szimmetrikus mátrix, melyben ${\displaystyle W_{i,j}=0}$ akkor áll fenn, ha ${\displaystyle (i,j)}$ nem egy él ${\displaystyle G}$-ben. Definiáljuk ${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$-t, ahol ${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$ a ${\displaystyle W}$ legnagyobb, illetve legkisebb sajátértékei. Legyen továbbá ${\displaystyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$, ahol ${\displaystyle W}$ az előbbi definíció szerinti. Ekkor:

${\displaystyle \chi _{H}(G)\leq \chi (G)}$.

Vektorkromatikus szám: Legyen ${\displaystyle W}$ pozitív szemidefinit mátrix, melyben ${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$, amennyiben ${\displaystyle (i,j)}$ egy él ${\displaystyle G}$-ben. Legyen továbbá ${\displaystyle \chi _{V}(G)}$ a legkisebb olyan k, melyre ez a ${\displaystyle W}$ mátrix létezik. Ekkor:

${\displaystyle \chi _{V}(G)\leq \chi (G)}$.

Lovász-szám: A komplementer gráf Lovász-száma a kromatikus szám alsó korlátja egyben:

${\displaystyle \vartheta ({\bar {G}})\leq \chi (G)}$.

Frakcionális kromatikus szám: a gráf frakcionális kromatikus száma a kromatikus szám alsó korlátja is:

${\displaystyle \chi _{f}(G)\leq \chi (G)}$.

Ezeket a korlátokat így lehet sorba rendezni:

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G)}$.

Magas kromatikus számú gráfok

A nagy klikkekkel rendelkező gráfok kromatikus száma mindig magas, de ennek a megfordítása nem általánosan igaz. A Grötzsch-gráf egy háromszöggel nem rendelkező 4-kromatikus gráf, és a példa a Mycielski-konstrukció segítségével általánosítható.

Mycielski-tétel (Alexander Zykov 1949, Jan Mycielski 1955): Tetszőlegesen nagy kromatikus számú háromszögmentes gráfok léteznek. Más megfogalmazásban: minden ${\displaystyle k\geq 2}$ egész számra létezik olyan ${\displaystyle G_{k}}$ gráf, melyre ${\displaystyle \omega (G_{k})=2}$ és ${\displaystyle \chi (G_{k})=k}$

A Brooks-tétel alapján a magas kromatikus számú gráfoknak magas maximális fokszámmal kell rendelkezniük. További lokális tulajdonság, ami magas kromatikus számhoz vezet, a nagy klikkek jelenléte. A színezhetőség azonban nem teljes mértékben lokális jelenség: egy magas girthű gráf lokálisan úgy néz ki, mint egy fa, hiszen az összes kör hosszú, kromatikus száma azonban mégsem feltétlenül 2:

Tétel (Erdős): Léteznek tetszőlegesen magas girthparaméterrel és kromatikus számmal rendelkező gráfok.^[2]

Az élkromatikus számra vonatkozó korlátok

A G gráf élszínezése megegyezik ${\displaystyle L(G)}$ élgráfjának csúcsszínezésével és viszont. Ezért:

${\displaystyle \chi '(G)=\chi (L(G)).}$

Szoros összefüggés van az élszínezhetőség és a gráf ${\displaystyle \Delta (G)}$ maximális fokszáma között. Mivel az ugyanabból a csúcsból kiinduló összes élnek különböző színűnek kell lennie, ezért:

${\displaystyle \chi '(G)\geq \Delta (G).}$

Továbbá,

Kőnig-tétel: ${\displaystyle \chi '(G)=\Delta (G)}$, ha G páros gráf.

Általában véve a kapcsolat még erősebb, mint ami a csúcsszínezésre vonatkozó Brooks-tételnél tapasztalható:

Vizing-tétel: a ${\displaystyle \Delta }$ maximális fokszámú gráf élkromatikus száma (kromatikus indexe) vagy ${\displaystyle \Delta }$, vagy ${\displaystyle \Delta +1}$.

Egyéb tulajdonságok

Egy gráfnak pontosan akkor van k-színezése, ha létezik olyan körmentes irányítása, melyben a leghosszabb út hossza legfeljebb k; ez a Gallai–Hasse–Roy–Vitaver-tétel (Nešetřil & Ossona de Mendez 2012).

Síkbarajzolható gráfok esetén a csúcsszínezések lényegében a sehol sem nulla folyamok duálisai.

Végtelen gráfokról jóval kevesebbet lehet elmondani – néhány eredmény a végtelen gráfok színezésével kapcsolatban:

• Ha egy G végtelen gráf minden véges részgráfja k-színezhető, akkor G is az, ha igaznak fogadjuk el a kiválasztási axiómát. Ez a De Bruijn–Erdős-tétel (de Bruijn & Erdős 1951).
• Ha egy gráfnak van teljes n-színezése minden n ≥ n₀-ra, akkor létezik végtelen teljes színezése (Fawcett 1978).

Nyitott kérdések

A fentiek alapján ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$ Reed egy 1998-as sejtése szerint a kromatikus szám lényegében az alsó korláthoz esik közelebb: ${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

A sík kromatikus száma, ahol két pont akkor van összekötve, ha éppen egység távolságra vannak, ismeretlen, mindenesetre a 4, 5, 6 és 7 számok valamelyike. További, kromatikus számmal kapcsolatos megoldatlan kérdések közé tartozik a Hadwiger-sejtés, ami szerint a k kromatikus számú gráfok mindig tartalmazzák a k csúcsú teljes gráfot gráfminorként, az Erdős–Faber–Lovász-sejtés ami a teljes gráfok páronként pontosan egy közös csúcsot tartalmazó uniójának kromatikus számára állít fel korlátot, valamint az Albertson-sejtés, ami szerint a k-kromatikus gráfok között a teljes gráfoknak a legalacsonyabb a metszési száma.

Amikor Birkhoff és Lewis a négyszínsejtés megoldásának céljából bevezették a kromatikus polinomot, azt a sejtést fogalmazták meg, hogy G síkbarajzolható gráfok ${\displaystyle P(G,t)}$ polinomja nem tartalmaz zérushelyet a ${\displaystyle [4,\infty )}$ régióban. Bár azt már sikerült igazolni, hogy ezen kromatikus polinomoknak nincs zérushelye az ${\displaystyle [5,\infty )}$ régióban és hogy ${\displaystyle P(G,4)\neq 0}$, a sejtés mégis bizonyítatlan. További nyitott kérdés az azonos kromatikus polinommal rendelkező gráfok karakterizációja, valamit annak meghatározása, hogy melyik polinomok lehetnek gráfok kromatikus polinomjai.

Algoritmusok

Polinom idejű algoritmusok

Annak meghatározása, hogy egy gráf két színnel színezhető-e, ekvivalens a gráf párosságának tesztelésével, így akár szélességi, akár mélységi kereséssel lineáris időben számítható. Általánosabban, a perfekt gráfok kromatikus száma és az ahhoz tartozó színezés szemidefinit programozással polinom időben meghatározható. A kromatikus polinom zárt alakban is előállítható sok gráftípus esetén, például erdőkre, merev körű gráfokra, körökre, kerékgráfokra és létragráfokra, ezeket így polinom időben ki lehet értékelni.

Ha a gráf síkba rajzolható, és alacsony a fafelbontásuk szélessége (vagy nem síkba rajzolható, de fafelbontásuk ismert), akkor dinamikus programozással szintén polinom időben színezhetők. Általánosan elmondható, hogy a szükséges idő a gráf méretének polinom, a fafelbontás szélességének viszont exponenciális függvénye.

Egzakt algoritmusok

Egy k-színezés brute-force keresése a k szín n csúcshoz való ${\displaystyle k^{n}}$ hozzárendelésének érvényességét vizsgálja. A kromatikus szám, illetve kromatikus polinom kiszámításánál ezt a módszert alkalmazzák minden ${\displaystyle k=1,\ldots ,n-1}$ értékre, ami csak a legkisebb bemeneti gráfoknál használható a gyakorlatban.

Dinamikus programozást használva, és a maximális független csúcshalmazok számának korlátját feltételezve a k-színezhetőség ${\displaystyle O(2,445^{n})}$ időben és térben eldönthető.^[3] A tartalmazás és kizárás elvének, illetve Yates gyors zéta-transzformációs algoritmusának felhasználásával a k-színezhetőség ${\displaystyle O(2^{n}n)}$^[4] időben eldönthető tetszőleges k-ra. Ennél gyorsabb algoritmusok ismertek a 3- és 4-színezhetőségre, melyek ${\displaystyle O(1,3289^{n})}$,^[5] illetve ${\displaystyle O(1,7272^{n})}$^[6] időben eldönthetők.

Élösszehúzás

Egy G gráf ${\displaystyle G/uv}$ élösszehúzása vagy kontrakciója a G-hez egy olyan gráfot rendel, melyben az ${\displaystyle u}$ és ${\displaystyle v}$ közötti éleket elhagyjuk és a két csúcsot egy darab ${\displaystyle w}$ csúcsban egyesítjük, ami az összes, korábban ${\displaystyle u}$-ban vagy ${\displaystyle v}$-ben végződő él végpontja lesz. Ez a művelet fontos szerepet játszik a gráfok színezésének vizsgálatában.

A kromatikus szám (Zykov 1949) alapján kielégíti az alábbi rekurrencia-relációt:

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\},}$

ahol u és v nem szomszédos csúcsok, ${\displaystyle G+uv}$ pedig az a gráf, ahol ${\displaystyle u}$ és ${\displaystyle v}$ közé egy él be van húzva. Több algoritmus is ennek a rekurziónak a kiszámításán alapszik. A számítás eredményével kapott számítási fát néha Zykov-fának nevezik. A futási idő ${\displaystyle u}$ és ${\displaystyle v}$ megválasztásától függ.

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

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k),}$

ahol ${\displaystyle u}$ és ${\displaystyle v}$ szomszédos csúcsok ${\displaystyle G-uv}$ az a gráf, amit az ${\displaystyle uv}$ él elhagyásával kapunk. ${\displaystyle P(G-uv,k)}$ 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 ${\displaystyle u}$ és ${\displaystyle v}$ különböző színűek, akkor nyugodtan vizsgálhatjuk azt a gráfot, ahol ${\displaystyle u}$ és ${\displaystyle v}$ szomszédosak, ha pedig ${\displaystyle u}$ és ${\displaystyle v}$ azonos színűek, akkor azt a gráfot vizsgáljuk, ahol az ${\displaystyle u}$ és ${\displaystyle v}$ csúcsokat egyesítettük.

Tuttét az iránti érdeklődése, hogy milyen egyéb gráftulajdonságok elégítenek ki hasonló rekurrenciákat, vezette el a kromatikus polinom kétváltozós általánosításának, a Tutte-polinomnak a felfedezéséhez.

Ezek a kifejezések adtak teret a deletion–contraction, avagy törlés-összevonás algoritmusnak, ami számos gráfszínezési algoritmus alapját képezi. A futásidő megegyezik a Fibonacci-számok rekurziójának felel meg, így a legrosszabb futási idő esetén az algoritmus ${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1,6180^{n+m})}$ polinom faktorában fut, ahol n a csúcsok, m az élek száma.^[7] Az analízis javítható a bemeneti gráf feszítőfáinak ${\displaystyle t(G)}$ számának polinom faktoráig.<^[8] A gyakorlatban branch and bound („korlátozás és elágazás”) heurisztikák és az izomorfizmusok kiküszöbölése segítségével néhány rekurzív hívás kiküszöbölhető. A futásidő a csúcspár kiválasztásának stratégiáján múlik.

Mohó színezés

Bővebben: Mohó színezés

Ugyanannak a gráfnak két, különböző csúcssorrendet alapul vevő mohó színezése. A jobboldali példa n csúcsú 2-színezhető gráfokra általánosítható, ahol a mohó algoritmus ${\displaystyle n/2}$ színt használ fel.

A színezés mohó algoritmusa a csúcsokat specifikus, ${\displaystyle v_{1}}$,…,${\displaystyle v_{n}}$ sorrendben veszi figyelembe, és ${\displaystyle v_{i}}$-hez azt a legkisebb elérhető színt rendeli hozzá, amit ${\displaystyle v_{i}}$ szomszédai ${\displaystyle v_{1}}$,…,${\displaystyle v_{i-1}}$ között még 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 választott sorrendtől függ. Mindig létezik olyan sorrend, ami az optimális, azaz ${\displaystyle \chi (G)}$ színt használó mohó színezéshez vezet. Másrészt a mohó színezéssel nagyon rossz eredmények is kijöhetnek. Például a két színnel színezhető, n csúcsú koronagráfok esetében a mohó színezés akár ${\displaystyle n/2}$ színt is felhasználhat.

Merev körű gráfok, és annak speciális esetei, az intervallumgráfok és egység-intervallumgráfok esetében a mohó algoritmussal polinom időben megtalálható az optimális színezés, a csúcsok sorrendjét a gráf perfekt eliminációs rendezésének fordítottjának választva. A perfekt rendezhető gráfok általánosítják ezt a tulajdonságot, de NP-nehéz ezen gráfok perfekt eliminációs rendezését megtalálni.

Ha a csúcsok fokszám szerint csökkenő sorrendben szerepelnek, a mohó színezés legfeljebb a gráf maximális fokszámánál 1-gyel több színt használ. Ezt a heurisztikát szokták Welsh–Powell-algoritmusnak nevezni.^[9] A Brélaz által alkalmazott heurisztika 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 fajta szín szerepel.^[10] Ezeket az algoritmusokat gyűjtőnevükön szekvenciális színező algoritmusoknak nevezik.

Adott gráf mohó színezése során (a csúcsok sorrendjének legrosszabb megválasztásával) elérhető maximális számú színt a gráf Grundy-szám-nak nevezik.

Párhuzamos és elosztott algoritmusok

Az elosztott algoritmusok területén a gráfszínezés szorosan kapcsolódik a szimmetriasértés problémájához. Elegendően nagy Δ maximális fokszámú gráfokon a legkorszerűbb véletlen algoritmusok gyorsabban végeznek a determinisztikus algoritmusoknál. A leggyorsabb véletlen algoritmusok a Schneider et al. által kifejlesztett multi-trials technikát („többszörös próba”) használják.^[11]

Szimmetrikus gráfban determinisztikus algoritmus nem képes a jó csúcsszínezést megtalálni. Szükség van valamilyen segédinformációra a szimmetria elrontásához. Egy általános megoldás szerint minden csúcs eredetileg rendelkezik egyedi azonosítóval, például az {1, 2, ..., n} halmazból. Más megközelítésben, feltehetjük, hogy egy n-színezésből indulunk ki. A feladat a szükséges színek számának csökkentése n-ről például Δ + 1-re. Minél több felhasználható szín van, például használható fel, például Δ + 1 helyett O(Δ), annál kevesebb kommunikációs körre van szükség.^[11]

A (Δ + 1)-színezés mohó algoritmusának kézenfekvő elosztott változata legrosszabb esetben Θ(n) kommunikációs kört igényel − az információnak el kell jutnia a hálózat egyik oldaláról a másikig.

A legegyszerűbb érdekes eset az n-kör. Richard Cole és Uzi Vishkin^[12] megmutatja, hogy létezik olyan elosztott algoritmus, ami a felhasznált színek számát n-ről O(log n)-re csökkenti egyetlen szinkron kommunikációs lépésben. Ugyanezt a műveletet ismételgetve az n-kör 3-színezését O(log* n) kommunikációs lépésben el lehet végezni (feltéve, hogy egyedi csomóponti azonosítók vannak).

A log* művelet, avagy az iterált logaritmus (a tetráció inverz művelete) egy rendkívül lassan növekvő függvény, „szinte konstans”. Ezért Cole és Vishkin eredménye kapcsán felmerült a kérdés, hogy létezik-e konstans idejű elosztott algoritmus egy n-kör 3-színezésére. (Linial 1992) megmutatta, hogy ez nem lehetséges: bármely determinisztikus elosztott algoritmusnak Ω(log* n) kommunikációs lépésre van szüksége az n-kör n-színezésének 3-színezésre való redukálásához.

Cole és Vishkin technikáját tetszőleges, korlátos fokszámú gráfokra is alkalmazni lehet; a futási idő poly(Δ) + O(log* n).^[13] A technikát Schneider et al. terjesztette ki egységkörgráfokra^[14] A leggyorsabb, kis Δ értékre (Δ + 1)-színezést végző determinisztikus algoritmust Leonid Barenboim, Michael Elkin és Fabian Kuhn jegyzi.^[15] Barenboim et al. algoritmusa O(Δ) + log*(n)/2 időben fut, ami n tekintetében optimális, mivel az ½ konstans faktor nem javítható Linial alsó korlátja miatt. (Panconesi & Srinivasan 1996) hálózati dekompozíciók segítségével talál Δ+1-színezést ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$ időben.

Az élszínezés elosztott modellű problémáját szintén megvizsgálták. (Panconesi & Rizzi 2001) (2Δ − 1)-színezést végzett O(Δ + log* n) időben ezzel a modellel. Az elosztott csúcsszínezés (Linial 1992)-féle alsó korlátja az elosztott élszínezési problémára is érvényes.

Decentralizált algoritmusok

A decentralizált algoritmusokban az üzenetküldés sem megengedett (ellentétben az elosztott algoritmusokkal, ahol a helyi üzenetküldés fontos szerepet kap). Léteznek hatékony decentralizált algoritmusok, melyek képesek egy gráf jó színezését megtalálni, ha az létezik. Ezek felteszik, hogy egy csúcs képes annak érzékelésére, ha bármelyik szomszédja vele megegyező színt használna, azaz ha egy helyi konfliktus történik. Ez egy több alkalmazásnál előforduló enyhe feltételezés, például a vezeték nélküli hálózatok kiosztásánál általában észszerű feltételezni, hogy egy bázisállomás észreveszi, hogy egy vele interferáló adó ugyanazt a csatornát használja (pl. a SINR, azaz „jel-zaj+interferencia viszony” mérésével). Ez az érzékelési képesség már elegendő ahhoz, hogy a tanuló gépeken alapuló algoritmusok 1 valószínűséggel rátaláljanak egy jó gráfszínezésre.^[16]

Számítási bonyolultság

A gráfszínezés egy bonyolult számítási művelet. NP-teljes nehézségű annak eldöntése, hogy adott gráfnak adott k értékre létezik-e jó k-csúcsszínezése, kivéve a k ∈ {0,1,2} eseteket. NP-nehéz feladat a gráf kromatikus számának kiszámítása.^[17] A 3-színezési probléma NP-teljes még 4-reguláris síkbarajzolható gráfok esetében is.^[18] Mindazonáltal a k > 3 értékekre a síkbarajzolható gráfoknak mindig létezik k-színezése, a négyszín-tétel értelmében, ami polinom időben meg is található.

A legjobb ismert approximációs algoritmus a kromatikus szám O(n(log log n)²(log n)⁻³) faktorában számol színezést.^[19] Tetszőleges ε > 0-ra a kromatikus szám n^1−ε-n belüli approximációja NP-nehéz.^[20]

Szintén NP-nehéz egy 3-színezhető gráf 4-színezését megtalálni,^[21] vagy egy k-színezhető gráfot k^{(log k ) / 25} színnel kiszínezni elegendően nagy k konstansra.^[22]

A kromatikus polinom együtthatóinak kiszámítása #P-nehéz. Valójában még a ${\displaystyle \chi (G,k)}$ értékének kiszámítása bármely k racionális ponton is #P-nehéz, kivéve a k = 1 és k = 2 esetet.^[23] Nem létezik FPRAS (teljesen polinom idejű randomizált approximációs séma) a kromatikus polinom kiszámítására bármely k ≥ 1,5 racionális ponton, a k = 2 esetet kivéve – hacsak nem igaz az, hogy NP = RP.^[24]

Élszínezés Vizing eredményének bizonyítása meg is ad egy legfeljebb Δ+1 színt használó algoritmust. Annak eldöntése azonban, hogy az élkromatikus szám a két szóba jövő érték közül melyik, NP-teljes.^[25] Approximációs algoritmusok tekintetében a Vizing-féle algoritmusból látható, hogy az élkromatikus szám 4/3-ra közelíthető, és a bonyolultsági eredmények azt mutatják, hogy semmilyen ε > 0 értékre nem létezik (4/3 − ε )-algoritmus, kivéve, ha P = NP. Ezek az approximációs algoritmusok között a legrégebbi eredmények közé tartoznak, bár egyik cikkben sem jelennek meg explicit módon.^[26]

Alkalmazások

Ütemezés

A csúcsszínezés több ütemezési probléma modelljének tekinthető.^[27] Legtisztább formájában feladatok adott halmazához időréseket kell rendelni, minden feladat egy időrést foglal el. A feladatok tetszőleges sorrendben végrehajthatók, de egyes feladatpárok konfliktusban lehetnek egymással, például mert ugyanazt a közös erőforrást (munkaerőt, helyiséget stb.) használják. Az ennek megfelelő gráf minden csúcsa egy-egy feladatnak felel meg, a konfliktusban lévő feladatok között húzódik él. A gráf kromatikus száma megegyezik a minimális teljes átfutási idővel, a feladatok konfliktusmentes végrehajtásának optimális idejével.

Az ütemezési probléma részletei határozzák meg a gráf szerkezetét. Ha például az egyes járatokhoz kell hozzárendelni repülőgépeket, a kapott konfliktusgráf egy intervallumgráf, aminek a színezése hatékonyan megoldható. Ha rádióállomások sávszélesség-kiosztását tekintjük, a kapott konfliktusgráf egységkörgráf, melynek színezése 3-approximálható.

Regiszterallokáció

Bővebben: Regiszterallokáció

A fordítóprogramok olyan számítógépes programok, melyek az egyik számítógépes nyelvről a másikra fordítanak. Az eredményül kapott kód futási idejének javítására szolgáló optimalizálási technikák egyike a regiszterallokáció, ahol a lefordított program leggyakrabban használt értékeit a processzor által gyorsan elérhető regiszterekben tárolják. Ideális esetben az értékadások és az értékekkel való műveletek is a (korlátozott számú) regiszterek valamelyikében történnek.

A tankönyvi megoldás a probléma gráfszínezésként történő modellezése.^[28] A fordító ún. interferenciagráfot (interference graph) konstruál, melynek csúcsai a változók, és két csúcsot akkor köt össze él, ha a hozzájuk tartozó változókra azonos időben van szükség. Ha a gráf k színnel színezhető, akkor azokat a változókat, amikre a programnak azonos időben van szüksége, k regiszterben el lehet tárolni.

Egyéb alkalmazások

A gráfszínezés problémája számos gyakorlati területen felmerül, ilyenek például a mintaillesztés, sportesemények lebonyolítási rendjének meghatározása, ülésrendek, vizsgák időbeosztásának, taxik menetrendjének összeállítása, szúdoku rejtvények megoldása.^[29]

Egyéb színezések

Ramsey-elmélet

Bővebben: Ramsey-tétel

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 kombinatorikának és a gráfelméletnek. Az elméletet összefűző filozófiát 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 a közös csúcsban találkozó élek színére. A Ramsey-tétel legegyszerűbb esete: a ${\displaystyle K_{6}}$ éleit tetszőlegesen megszínezve két színnel biztosan keletkezik benne egyszínű háromszög.

Egyéb színezések

Aciklikus színezés bármely két szín által meghatározott részgráf körmentes AVD-totális színezés szomszédos csúcsokat megkülönböztető totális színezés B-színezés a csúcsok olyan színezése, ahol minden színosztályhoz található olyan csúcs, aminek létezik szomszédja az összes többi színosztályból Csillagszínezés bármely két szín által meghatározott feszített részgráf csillaggráfok diszjunkt uniója Defektív színezés olyan, nem feltétlen jó színezés, ahol minden színosztályhoz korlátos fokszámú feszített részgráf tartozik Egzakt színezés minden színpár pontosan egy élen jelenik meg Erős színezés az azonos méretű partíciókban minden szín pontosan egyszer jelenik meg Erős élszínezés az élek úgy vannak színezve, hogy minden színosztály egy párosítást indukál (megegyezik az élgráf négyzetének színezésével) Egyenletes színezés a színosztályok mérete legfeljebb eggyel tér el egymástól Frakcionális színezés(wd) (tört színezés) egy csúcspont egyszerre többszínű is lehet, az egyes színeknek valamilyen súlyozása van 0 és 1 között, de összegük <1 Gyenge színezés nem jó színezés, ahol minden nem izolált csúcsnak van legalább egy különböző színű csomszédja Harmonikus színezés minden színpár legfeljebb egy élen jelenik meg Háromszögmentes élszínezés az élek olyan színezése, ahol minden színosztály háromszögmentes részgráfot alkot Incidenciaszínezés minden csúcs-él incidenciánál (illeszkedésnél) a csúcsnak és az élnek különböző színűnek kell lennie Intervallum-élszínezés egy közös csúcsban találkozó élek színeinek (címkéinek) folytonosnak kell lennie

Ívszínezés Komplementer színezés a csúcsok olyan (nem jó) színezése, ahol a színosztályok vagy klikket, vagy független csúcshalmazt feszítenek ki Körkörös színezés olyan feladatrendszerek motiválják, melyben a feldolgozás ciklikusan halad Középpontos színezés minden összefüggő feszített részgráfban van pontosan egyszer felhasznált szín L(h, k)-színezés a szomszédos csúcsok színeinek távolsága legalább h, a 2 távolságra lévő csúcsok színeinek távolsága legalább k. A h=1 és k=0 eset megegyezik a normál csúcsszínezéssel. Listaszínezés minden csúcshoz egy listáról választunk ki egy színt Lista-élszínezés minden élhez egy listáról választunk ki egy színt Megkülönböztető színezés a csúcsok olyan (nem jó) színezése, ami a gráf összes szimmetriáját megszünteti Multiszínezés minden csúcsra adott egy szám, ennyi színt kell neki adni úgy, hogy szomszédos színhalmazok diszjunktak legyenek Orientált színezés figyelembe veszi a gráf éleinek orientációját is Összegszínezés cél a színek összegének minimalizálása Rádiószínezés a csúcsok távolságának és a színeik közötti különbségnek az összege nagyobb mint k+1, ahol k pozitív egész szám. Rangszínezés ha két csúcs ugyanabba az i színosztályba tartozik, akkor minden köztük lévő útnak tartalmaznia kell i-nél magasabb színű csúcsot Részszínezés a csúcsok olyan (nem jó) színezése, ahol a színosztályok klikkek diszjunkt unióját feszítik ki T-színezés két szomszédos csúcs különbségének abszolút értéke nem tartozhat a rögzített T halmazhoz Teljes színezés minden színpár legalább egy élen megjelenik Totális színezés minden él és minden csúcs színezve van Útszínezés útválasztási problémát modellez a gráfban

A színezési probléma előjeles gráfokra is értelmezhető.

Források

• Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006.
• Archiválva 2012. március 10-i dátummal a Wayback Machine-ben
• Gráfszínezési problémák és ütemezési alkalmazásaik
• Gráfelmélet^{[halott link]}

Irodalom

• (= Indag. Math. 13)

• .
• .
• . Translated into English in Amer. Math. Soc. Translation, 1952, MR0051516.

Jegyzetek

1. (Brooks 1941)
2. .
3. (Lawler 1976)
4. (Björklund, Husfeldt & Koivisto 2009)
5. (Beigel & Eppstein 2005)
6. (Fomin, Gaspers & Saurabh 2007)
7. (Wilf 1986)
8. (Sekine, Imai & Tani 1995)
9. (Welsh & Powell 1967)
10. (Brélaz 1979)
11. (Schneider 2010)
12. (Cole & Vishkin 1986), lásd még (Cormen, Leiserson & Rivest 1990, Section 30.5)
13. (Goldberg, Plotkin & Shannon 1988)
14. (Schneider 2008)
15. (Barenboim & Elkin 2009); (Kuhn 2009)
16. Pl. lásd (Leith & Clifford 2006) és (Duffy, O'Connell & Sapozhnikov 2008).
17. (Garey, Johnson & Stockmeyer 1974); (Garey & Johnson 1979).
18. (Dailey 1980)
19. (Halldórsson 1993)
20. (Zuckerman 2007)
21. (Guruswami & Khanna 2000)
22. (Khot 2001)
23. (Jaeger, Vertigan & Welsh 1990)
24. (Goldberg & Jerrum 2008)
25. (Holyer 1981)
26. (Crescenzi & Kann 1998)
27. (Marx 2004)
28. (Chaitin 1982)
29. Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.