Egységes színezés

Az egységes színezés a színek  hozzárendelése egy irányítatlan gráf csúcsaihoz oly módon, hogy:

Vagyis a csúcsok különböző színekre bontása a lehető legegyenletesebb. Például, ha minden csúcsnak különböző színt adunk, az egységes színezést jelent, de általában sokkal több színt használ, mint amennyi az optimális egységes színezéshez szükséges. Egyenértékű módja az egységes színezés meghatározásának, ha egy adott gráfot részgráfként ágyazunk be egy ugyanolyan csúcskészletű Turan-gráfba . Az egyenletes színezéshez kétféle kromatikus szám tartozik [1] . A G gráf egyenletes kromatikus száma az  a legkisebb k szám, amelynél a G gráf egységes színezésű k színnel. Előfordulhat azonban, hogy a G grafikon egyes nagyobb színkészletei nem egységesek. A G gráf egyenletes kromatikus küszöbe  a legkisebb k szám, amelynél a G gráf egyenletes színezetű tetszőleges számú színre, amely nagyobb vagy egyenlő k -val [2] .

A Hajnal-Szemeredy tétel , amelyet Erdős Pal [3] sejtésként fogalmazott meg, és Hajnal András és Szemeredy Endre [4] igazolt , kimondja, hogy minden maximális fokozatú gráf színekkel egyenletesen színeződik . Számos kapcsolódó hipotézis nyitott marad. Léteznek polinomiális idő algoritmusok is az ennek a határnak megfelelő színezés megtalálására [5] , valamint algoritmusok a speciális gráfosztályok optimális színezésének megtalálására, de általánosabb probléma annak meghatározása, hogy egy tetszőleges gráf egyenletes színezésű-e egy adott gráfnál. a színek száma NP-teljes .

Példák

Az ábrán látható K 1.5 csillag egy teljes kétrészes gráf , ezért két színnel színezhető. A kapott színezésnek azonban egy csúcsa egy szín, és öt csúcsa egy másik színű, ezért a színezés nem egyenletes. Ennek a gráfnak a legkisebb színszáma egységes színezésben négy, amint az az ábrán is látható - a központi csúcsnak egyetlen csúcsú osztályhoz kell tartoznia, tehát a másik öt csúcsot legalább három színre kell felosztani úgy, hogy mindegyik osztály legfeljebb két csúcsot tartalmaz. Általánosabban Meyer [6] megjegyezte, hogy minden K 1, n csillaghoz színekre van szükség az egyenletes színezéshez, ezért a gráf kromatikus száma legfeljebb n /4-szer térhet el a kromatikus egyenletes számától. Mivel K 1,5 maximális foka öt, a Hajnal-Szemeredi tétel által garantált színek száma hat, amit úgy kapunk, hogy minden csúcshoz más-más színt rendelünk.

Egy másik érdekes jelenség egy másik teljes bipartit gráfot mutat, . Ennek a gráfnak a bipartitja által meghatározott egyenletes 2 színezése van. Ennek azonban nincs egységes (2 n  + 1) színezése - a csúcsok ilyen számú színre való egyenletes felosztásához színenként pontosan két csúcsnak kell lennie, de a kétrészes gráf két része nem párosítható, mert páratlan számú csúcsot tartalmaznak. Ezért ennek a gráfnak az egységes kromatikus küszöbértéke , ami sokkal nagyobb, mint az egyenletes kromatikus száma, amely kettő.

A Hainal-Semeredi tétel

Brooks tétele kimondja, hogy két kivétellel ( teljes gráfok és páratlan ciklusok) bármely összekapcsolt gráf maximális fokával -színezhető. Ez a színezés azonban általában távolról sem lehet egységes. Erdős Pál [3] úgy sejtette, hogy egyetlen komplementer színnel egyenletes színezés lehetséges – minden maximális fokozatú gráfnak egységes színezése van a színekkel. A tok egyszerű (az utak és hurkok bármely kombinációja egységesen színezhető háromszínű ismétlődő mintákkal, enyhe módosításokkal a zárt hurkokhoz). Az ügyben Corradi és Hainal döntött [7] . A teljes sejtést Hajnal és Semeredi [4] igazolta, és ma Hajnal-Szemeredi tételként ismerték. Eredeti bizonyításuk hosszú és bonyolult volt. Egy egyszerűbb bizonyítékot Kirsted és Kostochka [8] adott . Kiersted és Kostochka egy polinomiális időalgoritmust írt le az egységes színezés megtalálására ennyi színnel. Marcelo Midlarznak és Szemedi Endrének egy eltérő, korábban kidolgozott, publikálatlan polinomiális időalgoritmust tulajdonítanak. Kiersted és Kostochka egy erősebb változatát is bejelentette annak a tételnek, miszerint egyenletes k -színezés létezik, ha bármely két szomszédos csúcs fokszáma legfeljebb , de a bizonyítást soha nem publikálták.

Meyer [6] Brooks egységes színezési tétele alapján sejtette, hogy minden összekapcsolt gráf, amelynek maximális foka , egyenletes színezésű vagy kevesebb színnel rendelkezik, kivéve a teljes gráfokat és a páratlan ciklusokat. A sejtés erősebb változata azt állítja, hogy minden ilyen gráfnak egyenletes színezése van, pontosan színekkel, kivéve a teljes kétrészes gráfot , amelyben mindkét résznek azonos páratlan számú csúcsa van [1] .

Seymour [9] a Hajnal-Szemeredi tétel erősítését javasolta, amely magában foglalja azt a Dirac-tételt is, hogy a sűrű gráfok Hamilton -féleek  – úgy sejtette, hogy ha egy n csúcsú gráf bármely csúcsának vannak legalább szomszédai, akkor a gráf részgráfként tartalmazza a gráf, amelyet egy n -ciklusban legfeljebb k lépésnyire lévő csúcsok összekapcsolásával alkotunk meg. A k  = 1 eset Dirac saját tétele. A Hajnal-Szemeredi tétel felülírható ezzel a hipotézissel, ha a nagy k értékre vonatkozó hipotézist alkalmazzuk a gráf komplementerére, és színosztályként az n -ciklusból származó folytonos csúcssorozatokat használjuk . Seymour sejtése bebizonyosodott olyan gráfoknál, ahol n elég nagy k -hoz képest [10] . A bizonyítás néhány mély eszközt használ, beleértve magát a Hajnal-Szemeredi tételt is.

A Haynal-Szemeredi tétel másik általánosítása a Bollobash-Eldridge-Katlin hipotézis (vagy röviden a BEC hipotézis) [11] . Kimondja, hogy ha G 1 és G 2 n -csúcs gráfok maximális fokú és rendre, és ha , akkor G 1 és G 2 csomagolható. Azaz G 1 és G 2 ugyanazon az n csúcsból álló halmazon ábrázolható közös élek nélkül. A Hajnal-Szemeredi tétel egy speciális esete annak a sejtésnek, amelyben G 2 a diszjunkt klikkek uniója . Catlin [12] egy hasonló, de erősebb feltételt ad , amelyen és amely mellett egy ilyen csomagolás garantáltan létezik.

A grafikonok speciális esetei

A maximális fokszámú fa esetében az egységes kromatikus szám nem haladja meg

[6]

a legrosszabb esetben egy csillagon. A legtöbb fa egységes kromatikus száma azonban sokkal kisebb – ha egy n csúcsú fának van , akkor egységes színe van, csak három színnel [13] . Furmanchik [1] a gráfok szorzatainak egységes kromatikus számát tanulmányozta .

Számítási összetettség

Vizsgálták azt a problémát is, hogy a lehető legkevesebb színnel (a Hainal-Semeredi határ alatt) egységes színezéseket találjunk. A gráfszínezésről az egyenletes színezésre való közvetlen redukciót igazolhatjuk, ha elegendő izolált csúcsot adunk a gráfhoz, ami azt mutatja, hogy annak tesztelése, hogy adott számú (kettőnél nagyobb) színnel egyenletes színezésű-e egy gráf, NP-teljes . A probléma azonban érdekesebbé válik, ha a gráfok egy speciális osztályára korlátozódik, vagy a paraméterezett komplexitás szempontjából . Bodlander és Fomin [14] kimutatta, hogy egy G gráf és számos c szín mellett ellenőrizhető, hogy G egyenletesen c színezhető-e O( n O( t ) ) idő alatt, ahol t  a G fa szélessége . Különösen az egyenletes színezés oldható meg optimálisan polinomiális időben fák (amint az Chen és Lee [15] ) és a külső sík gráfok esetében is ismert . Létezik egy polinomiális idő algoritmus is az osztott gráfok egyenletes színezésére [16] . Fellowes, Fomin, Lokshtanov és munkatársai [17] azonban bebizonyították, hogy ha a faszélesség egy algoritmus paraméter, akkor a probléma W[1]-nehéz. Így nem valószínű, hogy létezik ettől a paramétertől független polinomiális időalgoritmus, sőt az sem valószínű, hogy a paramétertől való függést a kitevő zárójelbe teheti a futási idő képletében.

Alkalmazások

Az egységes színezés megfontolásának egyik okát Meyer [6] javasolta ütemezési problémákkal kapcsolatban . Ebben az alkalmazásban a gráf csúcsai végrehajtandó feladatok halmazát jelentik, az élek pedig két olyan feladatot kötnek össze, amelyeket nem lehet egyszerre végrehajtani. A grafikon színezése a feladatok egyidejűleg végrehajtható részhalmazokra való felosztását jelzi. Ekkor a színezésben szereplő színek száma megegyezik a feladat teljes elvégzéséhez szükséges lépések számával. A terheléselosztási konvenciók szerint kívánatos, hogy minden lépésben ugyanannyi vagy közel azonos számú feladatot végezzünk el, és pontosan ezt a kiegyenlítést adja az egységes színezés. Furmanchik [1] említette az ilyen típusú ütemezési probléma sajátos alkalmazását, nevezetesen az egyetemi kurzusok akadémiai órákonkénti elosztását úgy, hogy a kurzusok egyenlően oszlanak el a rendelkezésre álló idősávok között, hogy elkerülhető legyen az összeférhetetlen tanpárok azonos időponthoz való hozzárendelése.

A Hajnal-Szemeredi tételt a korlátos függésű valószínűségi változók összegeinek varianciájának korlátozására is alkalmazták [18] [19] . Ha (mint a lokális Lovas-lemma feltétele esetén ) minden változó legfeljebb másoktól függ, akkor a függőségi gráf egységes színezése felhasználható a változók független részhalmazokra történő felosztására, amelyeken belül Chernoff-határok számíthatók , ami jobb korlátokat ad a variancia, mintha nem egységes módon lenne particionálva.

Jegyzetek

  1. ↑ 1 2 3 4 Furmańczyk, 2006 .
  2. ↑ Figyeljük meg, hogy ha k nagyobb, mint a gráf csúcsainak száma, mindig egyenletes színezés van k színnel, amelyben minden színosztálynak nulla vagy osztályonként egy csúcsa van, így minden gráfnak egyenletes kromatikus küszöbe van.
  3. ↑ 12 Erdős , 1964 .
  4. ↑ 1 2 Hajnal, Szemerédi, 1970 .
  5. ↑ Kierstead, Kostochka, Mydlarz, Szemerédi, 2010 , p. 217–224.
  6. ↑ 1 2 3 4 Meyer, 1973 .
  7. ↑ Corrádi, Hajnal, 1963 .
  8. ↑ Kierstead, Kostochka, 2008 .
  9. ↑ Seymour, 1974 .
  10. ↑ Komlós, Sárközy, Szemerédi, 1998 .
  11. ↑ Bollobás, Eldridge, 1978 .
  12. ↑ Catlin, 1974 .
  13. ↑ Bollobás, Guy, 1983 .
  14. ↑ Bodlaender, Fomin, 2005 .
  15. ↑ Chen, Lih, 1994 .
  16. ↑ Chen, Ko, Lih, 1996 .
  17. ↑ Fellows, Fomin, Lokshtanov, 2007 .
  18. ↑ Pemmaraju, 2001 .
  19. ↑ Janson, Ruciński, 2002 .

Irodalom

Linkek