Grafikonok színezése

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. június 26-án felülvizsgált verziótól ; az ellenőrzések 15 szerkesztést igényelnek .

A gráfszínezés egy gráfelméleti konstrukció, a gráfjelölés egy speciális esete . Színezéskor a gráfelemekhez bizonyos korlátozások mellett címkéket rendelnek; ezeket a címkéket hagyományosan "színeknek" nevezik. A legegyszerűbb esetben a gráf csúcsainak színezésének azt a módját, amelyben bármely két szomszédos csúcs különböző színeknek felel meg, csúcsszínezésnek nevezzük. Hasonlóképpen az élszínezés minden élhez hozzárendel egy színt, így bármely két szomszédos él eltérő színű [1] . Végül egy síkgráf régiószínezése minden régióhoz hozzárendel egy színt, így minden két, egy határon áteső régió nem lehet azonos színű.

A csúcsszínezés a gráfszínezés fő problémája, minden egyéb probléma ezen a területen erre redukálható. Például egy gráf éleinek színezése a vonalgráfja csúcsainak színezése, a síkgráf régióinak színezése pedig a duális gráf csúcsainak színezése [1] . Azonban más grafikonszínezési problémákat gyakran az eredeti beállításokban vetnek fel és oldanak meg. Ennek egyrészt az az oka, hogy jobb képet ad arról, hogy mi történik, és sokkal leleplezőbb, másrészt az, hogy bizonyos problémákat kényelmesebb így megoldani (például élszínezés).

A grafikon színezése számos gyakorlati területen alkalmazható, és nem csak elméleti problémákban. A klasszikus típusú problémákon kívül a grafikonon, a színek hozzárendelésének módjára vagy magukra a színekre is különféle korlátozások helyezhetők. Ezt a módszert például a népszerű Sudoku rejtvényben használják . Még mindig aktív kutatás folyik ezen a területen.

Történelem

Az első eredményeket a térképszínezési feladatban síkgráfokra kaptuk. Az angliai megyék térképének kiszínezésére tett kísérletben Francis Guthrie megfogalmazta a négyszín problémát , megjegyezve, hogy négy szín elegendő a térkép színezéséhez, hogy bármely két szomszédos régió eltérő színű legyen. Bátyja a kérdést matematikatanárának, Augustus de Morgannek utalta, aki William Hamiltonnak írt levelében 1852-ben említette. Arthur Cayley felvetette ezt a problémát a Londoni Matematikai Társaság 1878-as ülésén . Ugyanebben az évben Tate javasolta az első megoldást erre a problémára. Az eredeti gráf csúcsainak színezését a duális gráf éleinek színezésére redukálta, és azt javasolta, hogy ennek a problémának mindig van megoldása [2] . 1880-ban Alfred Kempe publikált egy cikket, amelyben azt állította, hogy sikerült megállapítania az eredményt, és egy évtizedig a négy szín problémáját megoldottnak tekintették. Emiatt az eredményért Kempét a Londoni Királyi Társaság tagjává, majd a Londoni Matematikai Társaság elnökévé választották [3] .

1890-ben Heawood hibát talált Kempe bizonyításában. Ugyanebben a cikkben bebizonyította az öt szín tételt , megmutatva, hogy bármely lapos térkép legfeljebb öt színnel színezhető. Ennek során Kempe elképzeléseire támaszkodott. A következő évszázadban számos elméletet dolgoztak ki a színek minimális számának csökkentésére. A Négyszínű tételt végül 1977-ben Kenneth Appel és Wolfgang Haken tudósok számítógépes felsorolással bizonyították. A bizonyítás ötlete nagymértékben támaszkodott Heawood és Kempe gondolataira, és figyelmen kívül hagyta a köztes tanulmányok többségét [4] . A négy szín tételének bizonyítása az egyik első olyan bizonyítás, amelyben számítógépet használtak.

1912-ben George David Birkhoff javasolta a kromatikus polinom használatát, amely az algebrai gráfelmélet fontos részét képezi a színezési problémák tanulmányozására . A kromatikus polinomot ezt követően William Tutt általánosította ( Tutt polinomja ). Kempe már 1879-ben felhívta a figyelmet arra az általános esetre, amikor a gráf nem síkbeli [5] . A XX. század elején számos eredmény jelent meg a magasabb rendű felületeken színező síkgrafikonok általánosításának.

1960-ban Claude Burge megfogalmazta a tökéletes gráfsejtést , amelyet egy információelméleti fogalom, nevezetesen a Shannon által bevezetett gráfkapacitás nulla hiba [6] motivált . Ezt az állítást 40 évig nem erősítették meg, mígnem Chudnovskaya , Robertson , Seymour és Thomas matematikusok 2002-ben bebizonyították, mint a híres szigorú tökéletes gráftételt .

A gráfszínezést, mint algoritmikus problémát az 1970-es évek óta tanulmányozzák: a kromatikus szám meghatározása Karp 21 NP-teljes feladatának egyike (1972). Ezzel egy időben különféle algoritmusokat fejlesztettek ki a visszalépésen és a Zykov -féle rekurzív törlésen és összehúzódáson [7] . 1981 óta használják a gráfszínezést a fordítóprogramok regiszterek kiosztására [8] .

Definíció és terminológia

Vertex színezés

Amikor az emberek a gráfok színezéséről beszélnek, akkor szinte mindig a csúcsaik színezésére gondolnak, vagyis a gráf csúcsaihoz színcímkéket rendelnek úgy, hogy bármely két csúcs, amelynek közös éle eltérő színű legyen. Mivel a hurkolt gráfokat így nem lehet színezni, szóba sem jöhet.

A terminológia, amelyben a címkéket színeknek nevezik, a politikai térképek színezéséből származik. A piros vagy kék címkéket csak akkor használják, ha a színek száma kicsi, de a címkéket általában egész számoknak tekintik . $\{1,2,3,...\}$

A színekkel való színezést -színezésnek nevezzük . A gráf színezéséhez szükséges legkisebb számú színt kromatikus számnak nevezzük, és gyakran úgy írják, hogy . Néha használják , mivel az Euler - karakterisztikát jelöli . A csúcsok egy színnel kiemelt részhalmazát színosztálynak nevezzük , minden ilyen osztály független halmazt alkot . Így a -színezés ugyanaz, mint a csúcsok független halmazokra való felosztása [1] . $k$ $k$ $G$ $\chi (G)$ $\gamma (G)$ $\chi (G)$ $k$ $k$

Kromatikus szám a Gromov-Hausdorff távolságban

Legyen tetszőleges gráf csúcskészlettel . Rögzítünk két pozitív valós számot , és metrikus térnek fogjuk tekinteni , amelyben a szomszédos csúcsok távolsága egyenlő , és minden más nem nulla távolság egyenlő -vel . Jelölje a metrikus térrel, amely egymástól távolsággal elválasztott pontokból áll . Végül bármely két és metrikus térre jelölje a Gromov-Hausdorff távolságot és között . Ekkor a következő eredmény érvényes. $G$ $V$ $a<b\leq 2a$ $V$ $b$ $a$ ${\displaystyle a\Delta _{m))$ $m$ $a$ $x$ $Y$ $d_{GH}(X,Y)$ $x$ $Y$

Tétel (A.O. Ivanov, A.A. Tuzhilin) [9] : Legyen az a legnagyobb természetes szám, amelyre (ha nem léteznek ilyen természetes számok, akkor beállítjuk ). Akkor .

m

d_{GH}(V,a\Delta _{m})=b

m=0

\chi (G)=m+1

Megjegyzés.

A kromatikus szám akkor és csak akkor, ha a gráf nem tartalmaz éleket. Ebben az esetben az egyenlőség nem áll fenn egyikre sem , ezért megegyezés szerint , ami a helyes egyenlőséghez vezet . $\chi (G)$ $egy$ $G$ $d_{GH}(V,a\Delta _{m})=b$ $m$ $m=0$ $\chi (G)=0+1=1$

Értelemszerűen nem haladja meg a halmaz elemeinek számát . Másrészt könnyen kimutatható, hogy mindegyik esetében tehát, és ennélfogva . $\chi (G)$ $n$ $V$ $d_{GH}(V,a\Delta _{p})\leq \max\{a,\,ba\}<b$ $p\geq n$ $m<n$ $\chi (G)=m+1\leq n$

Kromatikus polinom

A kromatikus polinom egy függvény , amely megszámolja a gráf t -színezéseinek számát . A névből az következik, hogy adott esetén ez a függvény t -től függő polinom . $P(G,t)$ $G$ $G$

Ezt a tényt Birkhoff és Lewis fedezte fel, miközben megpróbálta bizonyítani a négy szín sejtést [10] .

Például a jobb oldali képen látható grafikon 12 féleképpen színezhető 3 szín használatával. Két színnel elvileg nem festhető. 4 színt használva 24+4*12 = 72 színezési lehetőséget kapunk: mind a 4 szín felhasználása esetén 4! = 24 helyes mód ( minden 4 szín hozzárendelése bármely 4 csúcsból álló gráfhoz helyes); és ebből a 4-ből minden 3 színhez 12 mód van a színezésre. Ezután a példában szereplő grafikonnál a helyes színezések számtáblázata így kezdődik:

Elérhető színek száma	egy	2	3	négy	…
A színezési módok száma	0	0	12	72	…

A példában szereplő grafikonhoz és természetesen a . $P(G,t)=t(t-1)^{2}(t-2)$ $P(G,4)=72$

Egy kromatikus polinom legalább annyi színezhetőségi információt tartalmaz, mint egy kromatikus szám. Valójában az a legkisebb pozitív egész szám, amely nem egy kromatikus polinom gyöke. $G$ $\chi$

\chi (G)=\min\{t\,\kettőspont \,P(G,t)>0\}.

Kromatikus polinomok egyes gráfokhoz

Háromszög alakú $K_{3}$	$t(t-1)(t-2)$
Teljes grafikon $K_n$	$t(t-1)(t-2)\cdots(t-(n-1))$
bordás fa _ $n$	$t(t-1)^{{n}}$
Ciklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersen grófja	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Élszínezés

A gráf élszínezése azt jelenti, hogy az élekhez színeket rendelünk oly módon, hogy két azonos színű él ne tartozzon ugyanahhoz a csúcshoz. Ez a probléma megegyezik az arcok halmazának független laphalmazokra való felosztásával . Egy gráf élszínezéséhez szükséges legkisebb színszám a kromatikus indexe vagy élkromatikus száma . $G$ $\chi '(G)$

Teljes színezés

A teljes színezés a gráf csúcsainak és éleinek színezésének egy fajtája. Ez alatt a színek olyan hozzárendelését értjük, hogy sem a szomszédos csúcsok, sem a szomszédos élek, sem az őket összekötő csúcsok és élek nem azonos színűek. A gráf teljes kromatikus száma a színek legkisebb száma, amely a teljes színezéshez szükséges. $\chi ''(G)$ $G$

Tulajdonságok

A kromatikus polinom tulajdonságai

Ha egy üres gráf [11] , $G$

P(G,t)=1

Ha a gráf diszjunkt részgráfok és [11] uniója , $G$ $H$ $K$

P(G,t)=P(H,t)P(K,t)

Ha van hurok a [11]-ben , $G$

P(G,t)=0

A kromatikus szám korlátozásai

Az összes csúcshoz különböző színek hozzárendelése mindig a megfelelő színezést adja, így

1\leq \chi (G)\leq n.

Az egyetlen fajta grafikon, amely egy színnel színezhető, a nulla grafikonok .
A csúcsokból álló teljes gráf színeket igényel . $K_n$ $n$ $\chi (K_{n})=n$
Optimális színezés esetén minden két színosztály között legalább egy gráfélnek kell lennie , így [12] $m$

\chi (G)(\chi (G)-1)\leq 2m.

Ha az unió diszjunkt részgráfok és , akkor $G$ $H$ $K$

\chi (G)=max\{\chi (H),\chi (K)\}

Ha k méretű klikkeket tartalmaz , akkor ennek a klikknek a színezéséhez legalább k szín szükséges, vagyis a kromatikus szám nagyobb vagy egyenlő, mint a klikkszám : $G$

\chi (G)\geq \omega (G).

Az intervallumgráfok esetében ez a korlátozás pontos.

A négy szín tétele szerint bármely síkgráf négy színnel színezhető.
A 2 színezhető grafikonok kétoldalú gráfok , beleértve a fákat is .

Egy gráf akkor és csak akkor bipartit, ha nem tartalmaz páratlan hosszúságú ciklusokat [11] .

G

A mohó színezés azt mutatja, hogy bármely gráf kiszínezhető eggyel több színnel, mint a maximális csúcsfoka [12] .

\chi (G)\leq \Delta (G)+1.

A teljes gráfokon és , ciklusgráfokon van és , így számukra ez a megszorítás a legjobb, minden más esetben a megszorítás javítható: Brooks [13] tétele kimondja, hogy $\chi (G)=n$ $\Delta(G)=n-1$ $\chi (G)=3$ $\Delta(G)=2$

\chi (G)\leq \Delta (G)

összefüggő, egyszerű gráf esetén ha nem teljes gráf, sem ciklusgráf.

G

G

Grafikonok nagy kromatikus számmal

A nagy klikkeket tartalmazó grafikonok nagy kromatikus számokkal rendelkeznek, de ennek fordítottja nem mindig igaz. A Grötzsch-gráf egy példa egy háromszög nélküli, 4 színezhető gráfra, és ez a példa általánosítható a Mycielski-gráfra .

Mychelski tétele (Alexander Zykov 1949, Jan Mychelski 1955): Vannak háromszög nélküli gráfok tetszőlegesen nagy kromatikus számokkal.

Brooks tétele szerint a nagy kromatikus számmal rendelkező gráfoknak magas maximális csúcsfokozattal kell rendelkezniük. Egy másik helyi körülmény, amely miatt a kromatikus szám nagy lehet, a nagy klikk jelenléte. A grafikon színezhetősége azonban nem csak a helyi viszonyoktól függ: a nagy kerületű gráf lokálisan úgy néz ki, mint egy fa, tehát minden ciklus hosszú, de a kromatikus száma nem egyenlő 2-vel:

Erdős tétel : Vannak tetszőlegesen nagy kerületű és kromatikus számú gráfok [12] .

A kromatikus index korlátozásai

Az élszínezés a vonalgráf csúcsainak színezése . Azaz $G$ $L(G)$

\chi '(G)=\chi (L(G)).

Továbbá [14] ,

König tétele : , ha kétrészes.

\chi '(G)=\Delta (G)

G

Általánosságban elmondható, hogy a kapcsolat sokkal erősebb, mint a Brooks-féle csúcsszínezési tétel [14] :

Vizin tétele: A maximális csúcsfokozatú gráfnak élkromatikus száma vagy .

\Delta

\Delta

\Delta +1

Egyéb tulajdonságok

Egy gráf akkor és csak akkor k - kromatikus , ha aciklikus orientációja van , amelyre a leghosszabb út hossza k . Ezt a Gallai-Hasse-Roy-Vitaver tétel [15] bizonyította .
Síkgráfok esetén a csúcsszínezés a sehol nulla áramlással egyenértékű .
Sokkal kevesebbet tudunk a végtelen gráfokról. Az alábbiakban két eredmény látható a végtelen gráfok színezésére.

Ha egy végtelen gráf minden véges részgráfja k - kromatikus, akkor a k -kromatikus is az ( a választási axióma feltételezésével bizonyítva ). Ez a de Bruijn-Erdős tétel megfogalmazása [16] . $G$ $G$
Ha egy gráf teljes n -színezést tesz lehetővé bármely , akkor végtelen teljes színezést enged meg [17] . $n\geqslant n_{0}$

Nyitott kérdések

Annak a síknak a kromatikus száma, amelyben két pont szomszédos, ha egységnyi távolság van közöttük. Ez lehet 5, 6 vagy 7. A gráfok kromatikus számával kapcsolatos további nyitott kérdések közé tartozik a Hadwiger-sejtés , amely kimondja, hogy minden k kromatikus számú gráfnak van egy teljes gráfja k csúcsból , az Erdős-Faber-Lovas. sejtés , amely korlátozza azoknak a teljes gráfoknak a kromatikus számát, amelyeknek pontosan egy közös csúcsa van minden gráfpárnak, valamint Albertson sejtése, hogy a k - kromatikus gráfok közül a legkevesebb metszésponttal rendelkező gráfok teljesek .

Amikor Birkov és Lewis bevezette a kromatikus polinomot a Négyszín Tétel megoldására, azzal érveltek, hogy síkgráfok esetében a polinomnak nincsenek nullák a tartományban . Bár ismert, hogy egy ilyen kromatikus polinomnak nincs nullája a tartományban , és ez , állításuk nem bizonyított. Nyitott kérdés marad az is, hogyan lehet megkülönböztetni az azonos kromatikus polinommal rendelkező gráfokat, és hogyan lehet meghatározni, hogy egy polinom kromatikus-e. $G$ $P(G,t)$ $[4,\infty )$ $[5,\infty )$ $P(G,4)\neq 0$

Színező algoritmusok

Polinom algoritmusok

Kétrészes gráf esetén a színezési probléma lineáris időben kerül kiszámításra a szélesség -első keresés segítségével . Tökéletes gráfok esetén a kromatikus szám és a hozzá tartozó színezés polinomiális időben , félig meghatározott programozással megkereshető . A kromatikus szám meghatározására szolgáló pontos képletek számos gráfosztályhoz ismertek (erdők, ciklusok , kerekek , akkordgráfok ), és polinomiális időben is kiszámíthatók.

Pontos algoritmusok

A k-színezés esetére kimerítő keresési algoritmus figyelembe veszi a színelrendezések összes kombinációját egy n csúcsú gráfban, és ellenőrzi azok helyességét. A kromatikus szám és a kromatikus polinom kiszámításához ez az algoritmus minden k-t figyelembe vesz 1-től n-ig. A gyakorlatban egy ilyen algoritmus csak kis gráfokra alkalmazható. $k^{n}$

Dinamikus programozással és a legnagyobb független halmaz méretének becslésével időben megoldható a k-színezés lehetősége egy gráfban [18] . A 3 és 4 színezéshez ismertek gyorsabb algoritmusok, amelyek időben futnak [19] , illetve [20] . $O(2,445^{n})$ $O(1,3289^{n})$ $O(1,7272^{n})$

Összehúzódás

A csúcsösszehúzás egy olyan művelet, amely gráfot készít gráfból úgy, hogy azonosítja a csúcsokat , és eltávolítja az őket összekötő éleket, és egy csúcsra cseréli őket , ahol az élek a csúcsokhoz esnek , és átirányítják őket . Ez a művelet fontos szerepet játszik a gráf színezésének elemzésében. $G$ $tulaj$ $u$ $v$ $w$ $u$ $v$

A kromatikus szám kielégíti az ismétlődési relációt

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

ahol és a nem szomszédos csúcsok, egy gráf hozzáadott éllel . Egyes algoritmusok ezen az arányon alapulnak, és ennek eredményeként fát hoznak létre, amelyet néha Zykov-fának is neveznek. A végrehajtási idő a csúcskiválasztási módszertől és a . $u$ $v$ $G+uv$ $UV$ $u$ $v$

A kromatikus polinom kielégíti az ismétlődési relációt

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

ahol és a szomszédos csúcsok, egy gráf, amelynek éle eltávolítva . a gráf lehetséges helyes színezéseinek számát jelenti, amikor a és csúcsok azonos vagy eltérő színűek lehetnek. Ha és különböző színűek, akkor tekinthetünk egy gráfot, ahol és szomszédosak. Ha a és ugyanazok a színek, akkor fontolóra vehetünk egy olyan grafikont, ahol és összevonják. $u$ $v$ $Tulaj$ $UV$ $P(G-uv,t)$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$

A fent megadott kifejezések egy rekurzív eljáráshoz vezetnek, az úgynevezett eltávolítási és szerződéskötési algoritmushoz , amely számos gráfszínező algoritmus alapját képezte. A futási idő ugyanazt az ismétlődési relációt elégíti ki, mint a Fibonacci-számok , így a legrosszabb esetben az algoritmus időben futni fog n csúcson és m élen [21] . A gyakorlatban az elágazó és kötött módszer és az izomorf gráfok elutasítása elkerüli a rekurzív hívásokat, a futási idő a csúcspár kiválasztásának módszerétől függ. $((1+{\sqrt 5})/2)^{{n+m}}=O(1,6180^{{n+m}})$

Mohó színezés

A mohó algoritmus rendezi a ,… csúcsokat, és sorrendben hozzárendeli a csúcshoz azt a legkisebb elérhető színt, amelyet nem használtak a ,…, , szomszédok színezésére , vagy hozzáad egy újat. A kapott színezés minősége a választott sorrendtől függ. Mindig van egy sorrend, amely a mohó algoritmust az optimális színszámra hozza . Másrészt egy mohó algoritmus tetszőlegesen rossz lehet; például egy n csúcsú koronát 2 színnel lehet színezni, de van olyan csúcssorrend, ami a színek mohó színezését eredményezi. $v_{1}$ $v_{n}$ $v_{i}$ $v_{i}$ $v_{1}$ $v_{{i-1}}$ $\chi (G)$ $n/2$

Egy akkordgráfnál és speciális eseteinél (például intervallumgráfnál ) a mohó színezési algoritmus használható az optimális színezés megtalálására polinomiális időben, ha a csúcsok sorrendjét a tökéletes eliminációs sorrend fordítottjaként választjuk meg . Ez az algoritmus a gráfok szélesebb osztályára alkalmazható ( teljesen rendezhető gráfok ), de ilyen sorrend megtalálása az ilyen gráfokhoz NP-nehéz probléma.

Ha a csúcsokat fokuk szerint rendezzük, akkor a mohó színező algoritmus legfeljebb színeket használ, ami legfeljebb 1-gyel több, mint (itt a csúcs foka ). Ezt a heurisztikus algoritmust néha Welsh-Powell algoritmusnak is nevezik [22] . Egy másik algoritmus dinamikusan állítja be a sorrendet, kiválasztva a következő csúcsot abból a csúcsból, amelyiknek a legszomszédosabb, különböző színű csúcsai vannak. Sok más gráfszínező algoritmus mohó színezésen alapul, és statikus vagy dinamikus csúcsrendezési stratégiákat használ. $max_{i}min\{d(v_{i})+1,i\}$ $\Delta$ $d(v_{i})$ $v_{i}$

Párhuzamos és elosztott algoritmusok

Hasonló probléma jelentkezik az elosztott algoritmusok területén is. Tegyük fel, hogy a gráf csúcsai olyan számítógépek, amelyek képesek kommunikálni egymással, ha éllel vannak összekötve. A cél az, hogy minden számítógép válasszon egy "színt" magának, így a szomszédos számítógépek más-más színt választanak. Ez a probléma szorosan összefügg a szimmetriatörés problémájával . A legfejlettebb valószínűségi algoritmusok gyorsabbak, mint a determinisztikus algoritmusok kellően nagy maximális csúcsfokozatú gráfokhoz . A leggyorsabb valószínűségi algoritmusok a többszörös próbálkozás technikáját használják [23] . $\Delta$

A szimmetrikus gráfokban a determinisztikus elosztott algoritmusok nem találják meg az optimális csúcsszínezést. További információra van szükség a szimmetria elkerülése érdekében. Egy szabványos feltételezés szerint kezdetben minden csúcsnak van egy egyedi azonosítója, például a halmazból . Más szóval, feltételezzük, hogy n -színezést kapunk. A feladat a színek számának csökkentése n -ről például -re . Minél több színt használunk (például a helyett ), annál kevesebb üzenetváltásra lesz szükség [23] . $\{1,2,...,N\}$ $(\Delta+1)$ $O(\Delta)$ $(\Delta+1)$

A színezés elosztott mohó algoritmusának egyszerű változata a legrosszabb esetben kommunikációs köröket igényel – előfordulhat, hogy az információnak a hálózat egyik végéről a másikra kell eljutnia. $(\Delta+1)$ $\Theta(n)$

A legegyszerűbb érdekes eset az n - ciklus. Richard Cole és Uzi Vishkin [24] kimutatta, hogy létezik egy elosztott algoritmus, amely n -ről -re csökkenti a színek számát , egyetlen szomszédos üzenetküldéssel. Ugyanezt az eljárást megismételve kaphatunk n -ciklusú 3-színezést a kapcsolódási körökben (feltéve, hogy egyedi csomópontazonosítókat adunk meg). $O(log(n))$ $O(log^{*}(n))$

A függvény , az iterált logaritmus , egy rendkívül lassan növekvő függvény, "majdnem állandó". Ezért Cole és Vishkin eredményei felvetik a kérdést, hogy létezik-e elosztott n-ciklusú 3 színezési algoritmus, amely állandó időben fut. Nathan Linial megmutatta, hogy ez lehetetlen: minden determinisztikus elosztott algoritmushoz kommunikációs körökre van szükség ahhoz, hogy egy N -színezést 3-as színezésre redukáljon egy n-ciklusban [25] . $napló^{*}$ $\Omega (log^{*}(n))$

Cole és Vishkin technikája alkalmazható tetszőleges, korlátos fokú csúcsokkal rendelkező gráfra is, ebben az esetben a futási idő [26] . Ezt a módszert Schneider és munkatársai általánosították az egységkör gráfra [27] . $P(\Delta )+O(log^{*}(n))$

Az élszínezés problémáját elosztott modellben is tanulmányozták. Pansonezzi és Rizzi elérte a színezést ebben a modellben [28] . Az elosztott csúcsszínezés Linial által elért alsó korlátja az elosztott élszínezés problémájára is alkalmazható [25] . $(2\Delta -1)$ $O(\Delta +log^{*}(n))$

Decentralizált algoritmusok

A decentralizált algoritmusokat olyan algoritmusoknak nevezzük, amelyekben a belső üzenettovábbítás nem engedélyezett (ellentétben az elosztott algoritmusokkal , ahol a folyamatok adatokat cserélnek egymással). Vannak hatékony decentralizált algoritmusok, amelyek sikeresen megbirkóznak a gráfok színezésével. Ezek az algoritmusok azon a feltételezésen dolgoznak, hogy egy csúcs képes "érezni", hogy bármelyik szomszédos csúcsa ugyanolyan színű, mint ő. Más szóval, lehetséges egy helyi konfliktus meghatározása. Ez a feltétel meglehetősen gyakran teljesül a valós alkalmazásokban - például vezeték nélküli csatornán keresztüli adatátvitel során az adóállomás általában képes észlelni, hogy egy másik állomás egyidejűleg próbál sugározni ugyanazon a csatornán. Az ilyen információk megszerzésének képessége elegendő ahhoz, hogy a tanulási automatákon alapuló algoritmusok egyes valószínűséggel helyesen oldják meg a gráf színezési problémáját [29] [30] .

Számítási összetettség

A grafikonok színezése számítási szempontból nehéz feladat. Annak megállapítása , hogy egy gráf k színezhető-e adott k esetén, NP-teljes feladat, kivéve a k = 1 és k = 2 eseteket. A kromatikus szám kiszámításának problémája NP-nehéz [31]. . A 3 színezési probléma NP-teljes még egy 4-es fokú síkgráf esetében is [32] .

Szintén NP-nehéz probléma egy 3 színezhető gráf 4 színnel színezése [33] és egy k színezhető gráf kellően nagy k értékéhez [34] . $k^{{log(k)/25}}$

A kromatikus polinom együtthatóinak kiszámítása #P-nehéz probléma. Bebizonyosodott, hogy nincs FPRAS algoritmus a kromatikus polinom kiszámítására bármely k ≥ 1,5 racionális számra , kivéve k = 2, kivéve, ha NP = RP [35] .

Alkalmazás

Tervezés

A csúcsszínezés számos tervezési problémát modellez [36] . A legegyszerűbb beállításban egy adott feladatkészletet időintervallumokra kell osztani, minden ilyen feladat egy szegmenst foglal el. Bármilyen sorrendben végrehajthatók, de a két munka ütközhet abban az értelemben, hogy nem hajthatók végre egyszerre, mert például megosztott erőforrásokat használnak. A megfelelő gráf minden feladathoz tartalmaz egy csúcsot és minden ütköző párhoz egy élt. A megszerkesztett gráf kromatikus száma az a minimális idő, amely alatt az összes feladat konfliktusmentesen befejeződik.

Az ütemezési probléma részletei határozzák meg a gráf szerkezetét. Például, amikor a repülőgépeket repülésekre osztják, az eredményül kapott konfliktusgráf egy intervallumgráf , így a színezési probléma hatékonyan megoldható. A rádiófrekvenciák elosztása során egységkonfliktuskörök grafikonját kapjuk, és egy ilyen problémára van egy 3-as közelítési algoritmus .

Regisztráció kiosztása

A fordítóprogram egy számítógépes program , amely az egyik számítógépes nyelvet a másikra fordítja. Az eredményül kapott kód végrehajtási idejének javítása érdekében az egyik fordítóoptimalizálási technika a regiszterallokáció , amelyben a lefordított program leggyakrabban használt változóit nagy sebességű processzor regiszterekben tárolják . Ideális esetben a változókat regiszterekben tárolják, így használatuk időpontjában mindegyik regiszterben van.

Ennek a problémának a standard megközelítése a gráf színezési problémára való redukálása [8] . A fordító összeállít egy interferenciagráfot , ahol a csúcsok változóknak felelnek meg, és egy él összeköti kettőt, ha egyszerre van szükség rájuk. Ha ez a gráf k -kromatikus, akkor a változók k regiszterben tárolhatók .

Digitális vízjelek

A digitális vízjelek technológiája ( eng. digital watermarking ) lehetővé teszi néhány rejtett üzenet átvitelét az adatokkal együtt (legyenek azok médiafájlok , végrehajtható fájlok és egyebek) (" vízjel ", vízjel ). Az ilyen rejtett üzenet a szerzői jogvédelemben felhasználható az adatok tulajdonosának azonosítására.

Ez fontos például az illegális terjesztésük forrásának megállapításához. Vagy az adatokhoz való jogok megerősítésére, például - szoftverrendszerek chipen ( system-on-chip ).

Az üzenet a regiszterek kiosztásának módjában is kódolható. Az egyik ilyen technikát Qu és Potkonjak [37] javasolta (ezért néha QP algoritmusnak is nevezik).

Ez a következőkből áll: legyen a processzorregiszterek eloszlásának inkompatibilitási gráfja (interferenciagráf), amit fentebb említettünk. A színezését a program használja – ráadásul úgy, hogy a grafikon tartalmát a kromatikus szám enyhe növelésével is meg lehet változtatni . Kiderült, hogy lehetséges egy üzenet kódolása egy szoftvertermékben gráfszínezéssel , vagyis a regiszterek elosztásával. $G$ $G$

Ezt az üzenetet úgy bonthatja ki, hogy összehasonlítja a regiszterek eloszlását az eredeti színezéssel; [38] Vannak módok is annak ellenőrzésére, hogy egy üzenet kódolva volt-e a programban az eredeti használata nélkül.

Ezt követően különböző szerzők fejlesztették ki és finomították Qu és Potkonjak [39] gondolatait . [38] [40]

Egyéb felhasználások

A grafikon színezési problémája számos más alkalmazásban is felmerült, beleértve a mintaillesztést is .

A Sudoku rejtvény megfejtése úgy is felfogható, mint egy adott, 81 csúcsból álló gráf 9 színű színezése.

Jegyzetek

↑ 1 2 3 ( Molloy & Reed 2002 , Az alapvető definíciók )
↑ ( Donets & Shor 1982 , Történelmi háttér )
↑ ( Kubale 2004 , A gráfszínezés története )
↑ ( van Lint & Wilson 2001 , 33. fejezet)
↑ ( Jensen és Toft 1995 , 2. o.)
↑ CE Shannon, "Egy zajos csatorna nulla hibamentes kapacitása", IEEE Trans. Információelmélet , pp. 1956. 8-19.
↑ ( Zykov 1949 )
↑ 1 2 ( Chaitin 1982 )
↑ AOIvanov, AATuzhilin (2019), The Gromov-Hausdorff Distance between Simplexes and Two-Distance Spaces , < https://arxiv.org/pdf/1907.09942.pdf > Archivált : 2019. július 29. a Wayback Machine -nél
↑ ( Birkhoff és Lewis 1946 )
↑ 1 2 3 4 ( Tutte 1984 , kromatikus polinom )
↑ 1 2 3 ( Diestel 2005 , Csúcsok színezése )
↑ ( Brooks & Tutte 1941 )
↑ 1 2 ( Diestel 2005 , Élek színezése )
↑ ( Nesetřil és Ossona de Mendez 2012 )
↑ ( de Bruijn, Erdős 1951 )
↑ ( Fawcett 1978 )
↑ ( Lawler 1976 )
↑ ( Beigel és Eppstein 2005 )
↑ ( Fomin, Gaspers és Saurabh 2007 )
↑ ( Sekine, Imai és Tani 1995 )
↑ ( Welsh & Powell 1967 )
↑ 1 2 ( Schneider 2010 )
↑ ( Cole és Vishkin 1986 ), lásd még ( Cormen, Leiserson és Rivest 1990 , 30.5. szakasz)
↑ 1 2 ( Linial 1992 )
↑ ( Goldberg, Plotkin és Shannon 1988 )
↑ ( Schneider 2008 )
↑ ( Panconesi & Rizzi 2001 )
↑ ( Leith és Clifford 2006 )
↑ ( Duffy, O'Connell és Sapozhnikov 2008 )
↑ ( Garey, Johnson és Stockmeyer 1974 ); ( Garey és Johnson 1979 ).
↑ ( Dailey 1980 )
↑ ( Guruswami és Khanna 2000 )
↑ ( Khot 2001 )
↑ ( Goldberg és Jerrum 2008 )
↑ ( Marx 2004 )
↑ ( Qu és Potkonjak 1998 )
↑ 1 2 ( Zhu & Thomborson 2006 )
↑ ( Collberg, Thomborson és Townsend 2004 )
↑ ( Myles és Collberg 2003 )

Irodalom

Donets, G. A. & Shor, N. Z. (1982), An Algebraic Approach to the Plane Graph Coloring Problem , Naukova Dumka, p. 5-7
Zykov, A. A. (1949), A lineáris komplexek néhány tulajdonságairól , Mat. Ült. T. 24(66) (2): 163–188 , < http://mi.mathnet.ru/eng/msb5974 >
Beigel, R. & Eppstein, D. (2005), 3-coloring in time O(1,3289 n ) , Journal of Algorithms 54. kötet (2)): 168–204 , DOI 10.1016/j.jalgor.2004.06.008
Birkhoff, G. D. & Lewis, D. C. (1946), Chromatic Polynomials , Trans. amer. Math. szoc. T. 60 : 355-451 , >
Brélaz, D. (1979), Új módszerek a gráf csúcsainak színezésére , Communications of the ACM vol. 22 (4): 251–256 , DOI 10.1145/359094.359101
Brooks, R. L. & Tutte, WT (1941), A hálózat csomópontjainak színezéséről , Proceedings of the Cambridge Philosophical Society , 37. kötet (2): 194–197 , DOI 10.1017/S030500410002168X
N. G. de Bruijn, P. Erdős . Színprobléma végtelen gráfokhoz és probléma a relációelméletben (angol) // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . - S. 371-373 . (= Indag. Math. 13 )
Byskov, JM (2004), Maximális független halmazok felsorolása gráfszínezési alkalmazásokkal , Operations Research Letters 32 (6): 547–556 , DOI 10.1016/j.orl.2004.03.002
Cormen, T. H.; Leiserson, CE & Rivest, RL (1990), Introduction to Algorithms (1. kiadás), The MIT Press
Collberg, Christian; Thomborson, Clark & Townsend, Gregg M. (2004), Dynamic Graph-Based Software Watermarking , < ftp://ftp.cs.arizona.edu/reports/2004/TR04-08.pdf >
Chaitin , GJ (1982), Regiszterek kiosztása és kiszóródása grafikonszínezéssel , Proc. 1982 SIGPLAN Symposium on Compiler Construction , p. 98–105, ISBN 0-89791-074-5 , DOI 10.1145/800230.806984
Cole, R. & Vishkin, U. (1986), Determinisztikus érmefeldobás alkalmazásokkal az optimális párhuzamos listás rangsoroláshoz , Information and Control 70. kötet (1): 32–53 , DOI 10.1016/S0019-9958(86)80023-7
Dailey, D. P. (1980): A síkbeli 4-reguláris gráfok színezhetőségének egyedisége és színezhetősége NP-teljesek , Discrete Mathematics 30 (3): 289–293 , DOI 10.1016/0012-365X(80-802365)
Diestel, R. (2005), Graph theory , < http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf > Archiválva 2014. november 25-én a Wayback Machine -nél
Duffy, K.; O'Connell, N. & Sapozhnikov, A. (2008), Decentralizált gráfszínező algoritmus komplexitáselemzése , Information Processing Letters 107. köt.: 60–63, doi : 10.1016/j.ipl.2008.01.002 , < http: //www.hamilton.ie/ken_duffy/Downloads/cfl.pdf >
Fawcett, BW (1978), A gráfok végtelen teljes színezéséről, Can. J Math. T. XXX: 455–457
Fomin, FV; Gaspers, S. & Saurabh, S. (2007), Improved Exact Algorithms for Counting 3- and 4-Colorings , Proc. 13th Annual International Conference, COCOON 2007 , vol. 4598, Lecture Notes in Computer Science , Springer, p. 65-74, ISBN 978-3-540-73544-1
Garey, MR & Johnson, DS (1979), Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez , W. H. Freeman, ISBN 0-7167-1045-5
Goldberg, LA & Jerrum, M. (2008. július), Inapproximability of the Tutte polinom , Information and Computation 206. kötet (7): 908–929 , DOI 10.1016/j.ic.2008.04.003.
Goldberg, A. V .; Plotkin, SA & Shannon, GE (1988), Parallel symmetry-breaking in sparse graphs , SIAM Journal on Discrete Mathematics 1. kötet (4): 434–446 , DOI 10.1137/0401044
Guruswami, V. & Khanna, S. (2000), On the hardness of 4-coloring a 3-colorable graph , Proceedings of the 15th Annual IEEE Conference on Computational Complexity , p. 188–197, ISBN 0-7695-0674-7 , DOI 10.1109/CCC.2000.856749
Jaeger, F.; Vertigan, DL és Welsh, DJA (1990), A Jones- és Tutte-polinomok számítási összetettségéről , Mathematical Proceedings of the Cambridge Philosophical Society , 108. kötet , 35–53, DOI 10.1017/S030506049360
Jensen, Tommy R. és Toft, Bjarne (1995), Graph Coloring Problems , John Wiley & Sons, ISBN 0-471-02865-7
Khot, S. (2001), MaxClique, kromatikus szám és közelítő gráfszínezés javított megközelíthetetlenségi eredményei , Proc. 42. éves szimpózium a számítástechnika alapjairól , p. 600–609, ISBN 0-7695-1116-3 , DOI 10.1109/SFCS.2001.959936
Kubale, M. (2004), Graph Colorings , American Mathematical Society, ISBN 0-8218-3458-4
Kuhn, F. (2009), Gyenge gráfszínezés: elosztott algoritmusok és alkalmazások , Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures , p. 138–144, ISBN 978-1-60558-606-9
Lawler, EL (1976), Megjegyzés a kromatikus számprobléma összetettségéhez , Information Processing Letters , 5. kötet (3): 66–67 , DOI 10.1016/0020-0190(76)90065-X
Leith, DJ & Clifford, P. (2006), A Self-Managed Distributed Channel Selection Algorithm for WLAN , Proc. RAWNET 2006, Boston, MA , < http://www.hamilton.ie/peterc/downloads/rawnet06.pdf >
Linial, N. (1992), Lokalitás elosztott gráfalgoritmusokban , SIAM Journal on Computing 21. kötet (1): 193–201 , DOI 10.1137/0221015
van Lint, JH és Wilson, R. M. (2001), A Course in Combinatorics (2. kiadás), Cambridge University Press, ISBN 0-521-80340-3
Molloy, Michael & Reed, Bruce (2002), Grafikonszínezés és valószínűségi módszer , Springer, ISBN 3-540-42139-4 , ISSN 0937-5511
Marx, Dániel (2004), Grafikonszínezési problémák és alkalmazásaik az ütemezésben, Periodica Polytechnica, Elektrotechnika , vol. 48. o. 11–16., CiteSeerX:10.1.1.95.4268
Mycielski, J. (1955), Sur le coloriage des graphes , Colloq. Math. Vol. 3: 161–162 , < http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf > .

Myles, Ginger és Collberg, Christian S. (2003), Software Watermarking Through Register Allocation: Implementation, Analysis, and Attacks , ICISC , p. 274-293 , DOI 10.1007/b96249

Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), 3.13. tétel , Sparity: Graphs, Structures, and Algorithms , vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, p. 42, ISBN 978-3-642-27874-7 , DOI 10.1007/978-3-642-27875-4 .
Panconesi, Alessandro & Rizzi, Romeo (2001), Néhány egyszerű elosztott algoritmus ritka hálózatokhoz , Elosztott számítástechnika (Berlin, New York: Springer-Verlag ). — V. 14 (2): 97–100, ISSN 0178-2770 , DOI 10.1007/PL00008932
Panconesi, A. & Srinivasan, A. (1996), Az elosztott hálózati dekompozíció összetettségéről, Journal of Algorithms , vol. húsz
Qu, Gang és Potkonjak, Miodrag (1998), Analysis of Watermarking techniks for graph coloring problem , ICCAD , p. 190-193 , DOI 10.1145/288548.288607
Schneider, J. (2010), Egy új technika az elosztott szimmetriatöréshez , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf > Archivált : 2013. július 30. a Wayback Machine
Schneider, J. (2008), A log-star elosztott maximális független halmazalgoritmus növekedési határos gráfokhoz , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podc08SW. pdf > Archiválva : 2013. július 30. a Wayback Machine -nél
Sekine, K.; Imai, H. & Tani, S. (1995), Computing the Tutte polynomial of a medium size size , Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995) , vol. 1004, Lecture Notes in Computer Science , Springer, p. 224–233, ISBN 3-540-60573-8 , DOI 10.1007/BFb0015427
Tutte, WT (1984), Graph theory, Encyclopedia of Mathematics and Applications (Cambridge University Press). - Vol. 21, ISBN 0-521-30241-2
Welsh, DJA & Powell, MB (1967), A gráf kromatikus számának felső korlátja és alkalmazása az időbeosztási problémákra , The Computer Journal 10. kötet (1): 85–86 , DOI 10.1093/comjnl/10.1.85
Wilf, H. S. (1986), Algorithms and Complexity , Prentice–Hall
Zhu, William & Thomborson, Clark (2006), Recognition in software watermarking , MCPS '06: Proceedings of the 4th ACM international workshop on Contents protection and security , ACM, p. 29–36, ISBN 1-59593-499-5 , DOI 10.1145/1178766.1178776