Värityskaaviot

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. kesäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 15 muokkausta .

Graafin väritys on graafiteoreettinen rakenne , graafimerkinnän erikoistapaus. Väritettäessä kaavioelementeille annetaan tunnisteita tietyin rajoituksin; näitä etikettejä kutsutaan perinteisesti "väreiksi". Yksinkertaisimmassa tapauksessa sellaista tapaa värjätä graafin kärkipisteitä , joissa mitkä tahansa kaksi vierekkäistä kärkeä vastaavat eri värejä, kutsutaan vertex coloringiksi . Samoin reunan väritys määrittää värin jokaiselle reunalle siten, että kahdella vierekkäisellä reunalla on eri värit [1] . Lopuksi tasograafin alueiden väritys määrittää värin jokaiselle alueelle, jotta kahdella alueella, joilla on yhteinen reuna, ei voi olla samaa väriä.

Vertex-värjäys on graafin värjäyksen pääongelma, kaikki muut tämän alueen ongelmat voidaan pelkistää siihen. Esimerkiksi graafin reunojen väritys on sen viivagraafin kärkien väritys ja tasograafin alueiden väritys sen kaksoisgraafin kärkien väritystä [1] . Muut graafin väritysongelmat kuitenkin usein asetetaan ja ratkaistaan alkuperäisessä asetuksessa. Syynä tähän on osittain se, että se antaa paremman käsityksen siitä, mitä tapahtuu ja on paljastavampi, ja osittain siksi, että jotkut ongelmat on helpompi ratkaista tällä tavalla (esim. reunavärjäys).

Graafisten värjäystä voidaan käyttää monilla käytännön aloilla, ei vain teoreettisissa ongelmissa. Klassisten tehtävien lisäksi erilaisia rajoituksia voidaan asettaa myös kuvaajalle, värien määrittelytavalle tai itse väreille. Tätä menetelmää käytetään esimerkiksi suositussa Sudoku -pulmapelissä . Tällä alueella on edelleen aktiivista tutkimusta.

Historia

Ensimmäiset tulokset saatiin karttaväritystehtävän tasokaavioista . Yrittäessään värittää Englannin kreivikuntien karttaa Francis Guthrie muotoili neliväriongelman huomauttaen, että neljä väriä riittää värittämään kartan niin, että kahdella vierekkäisellä alueella on eri värit. Hänen veljensä välitti kysymyksen matematiikan opettajalleen Augustus de Morganille , joka mainitsi sen kirjeessään William Hamiltonille vuonna 1852. Arthur Cayley otti tämän ongelman esiin Lontoon matemaattisen seuran kokouksessa vuonna 1878. Samana vuonna Tate ehdotti ensimmäistä ratkaisua tähän ongelmaan. Hän pelkisti alkuperäisen graafin kärkien värityksen kaksoisgraafin reunojen värjäykseen ja ehdotti, että tähän ongelmaan on aina ratkaisu [2] . Vuonna 1880 Alfred Kempe julkaisi artikkelin, jossa hän väitti onnistuneensa saamaan tuloksen, ja vuosikymmenen ajan neljän värin ongelmaa pidettiin ratkaistuna. Tästä saavutuksesta Kempe valittiin Lontoon kuninkaallisen seuran jäseneksi ja myöhemmin London Mathematical Societyn presidentiksi [3] .

Vuonna 1890 Heawood löysi virheen Kempen todistuksesta. Samassa artikkelissa hän todisti viiden värin lauseen osoittaen, että mikä tahansa tasainen kartta voidaan värittää enintään viidellä värillä. Näin tehdessään hän nojautui Kempen ideoihin. Seuraavalla vuosisadalla kehitettiin suuri määrä teorioita, joilla yritettiin vähentää värien vähimmäismäärää. Tiedemiehet Kenneth Appel Wolfgang Haken vahvistivat värin lauseen lopulta vuonna 1977 tietokoneella laskemalla. Ajatus todisteesta nojautui vahvasti Heawoodin ja Kempen ajatuksiin ja jätti huomiotta suurimman osan välitutkimuksista [4] . Neljän värin lauseen todistus on yksi ensimmäisistä todisteista, joissa käytettiin tietokonetta.

Vuonna 1912 George David Birkhoff ehdotti kromaattisen polynomin käyttöä , joka on tärkeä osa algebrallista graafiteoriaa, väritysongelmien tutkimiseen . Tämän jälkeen William Tutt ( Tuttin polynomi ) yleisti kromaattisen polynomin . Kempe jo vuonna 1879 kiinnitti huomion yleiseen tapaukseen, jolloin kuvaaja ei ollut tasomainen [5] . 1900-luvun alussa ilmestyi monia tuloksia korkeampien pintojen väritystasokaavioiden yleistyksistä.

Vuonna 1960 Claude Burge muotoili täydellisen graafisen olettamuksen informaatioteorian käsitteestä , nimittäin Shannonin esittämästä graafikapasiteetin nollavirheestä [6] . Väite pysyi vahvistamattomana 40 vuotta, kunnes matemaatikot Chudnovskaya , Robertson , Seymour ja Thomas osoittivat sen kuuluisaksi tiukan täydellisen graafin lauseeksi vuonna 2002.

Graafisten värjäystä algoritmisena ongelmana on tutkittu 1970-luvulta lähtien: kromaattisen luvun määrittäminen on yksi Karpin 21 NP-täydestä tehtävästä (1972). Ja suunnilleen samaan aikaan kehitettiin erilaisia algoritmeja, jotka perustuivat taaksepäin ja Zykovin rekursiiviseen poistoon ja supistukseen [7] . Vuodesta 1981 lähtien graafien väritystä on käytetty kääntäjien rekisterien allokoinnissa [8] .

Määritelmä ja terminologia

Vertex väritys

Kun ihmiset puhuvat graafien värittämisestä, he tarkoittavat melkein aina niiden kärkien värittämistä, toisin sanoen värimerkintöjen osoittamista graafin kärkipisteille siten, että kahdella pisteellä, joilla on yhteinen reuna, on eri värit. Koska silmukkakaavioita ei voi värjätä tällä tavalla, ne eivät tule kysymykseen.

Terminologia, jossa tarroja kutsutaan väreiksi, tulee poliittisten karttojen värityksestä. Tarroja, kuten punaista tai sinistä , käytetään vain, kun värejä on vähän, mutta tarrojen oletetaan yleensä olevan kokonaislukuja . $\{1,2,3,...\}$

Värjäämistä väreillä kutsutaan -värjäytykseksi . Pienin määrä värejä, jotka tarvitaan graafin värittämiseen, kutsutaan sen kromaattiseksi numeroksi ja se kirjoitetaan usein nimellä . Joskus käytetään , koska se tarkoittaa Eulerin ominaisuutta . Yhdellä värillä korostettua kärkien osajoukkoa kutsutaan väriluokiksi , jokainen tällainen luokka muodostaa itsenäisen joukon . Siten -värjäys on sama kuin kärkien jakaminen itsenäisiksi joukoiksi [1] . $k$ $k$ $G$ $\chi (G)$ $\gamma (G)$ $\chi (G)$ $k$ $k$

Kromaattinen luku Gromov-Hausdorffin etäisyydellä

Antaa olla mielivaltainen graafi, jonka kärkipiste on asetettu . Kiinnitämme kaksi positiivista reaalilukua , ja pidämme sitä metrianavaruutena, jossa vierekkäisten kärkien väliset etäisyydet ovat yhtä suuria kuin , ja kaikki muut nollasta poikkeavat etäisyydet ovat yhtä suuria kuin . Merkitään metriavaruudella, joka koostuu pisteistä, jotka on erotettu toisistaan etäisyyden päässä . Lopuksi kahdelle metriselle välilyönnille ja merkitse Gromov -Hausdorffin välinen etäisyys ja . Sitten seuraava tulos pätee. $G$ $V$ $a<b\leq 2a$ $V$ $b$ $a$ ${\displaystyle a\Delta _{m))$ $m$ $a$ $X$ $Y$ $d_{GH}(X,Y)$ $X$ $Y$

Lause (A.O. Ivanov, A.A. Tuzhilin) [9] : Olkoon suurin luonnollinen luku, jolle (jos tällaisia luonnollisia lukuja ei ole, asetamme ). Sitten .

m

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

m = 0

{\näyttötyyli \chi (G)=m+1}

Kommentti.

Kromaattinen luku on , jos ja vain jos graafi ei sisällä yhtään reunaa. Tässä tapauksessa tasa -arvo ei päde mihinkään , joten sopimuksen mukaan , joka johtaa oikeaan tasa-arvoon . $\chi (G)$ $yksi$ $G$ $d_{GH}(V,a\Delta _{m})=b$ $m$ $m = 0$ ${\näyttötyyli \chi (G)=0+1=1}$

Määritelmän mukaan ei ylitä joukon elementtien määrää . Toisaalta on helppo osoittaa, että jokaiselle , siis ja siten . $\chi (G)$ $n$ $V$ $d_{GH}(V,a\Delta _{p})\leq \max\{a,\,ba\}<b$ $p\geq n$ $m<n$ ${\näyttötyyli \chi (G)=m+1\leq n}$

Kromaattinen polynomi

Kromaattinen polynomi on funktio , joka laskee graafin t -väritysten määrän . Nimestä seuraa, että annetulle tämä funktio on polynomi , joka riippuu t :stä . $P(G,t)$ $G$ $G$

Tämän tosiasian löysivät Birkhoff ja Lewis yrittäessään todistaa neljän värin olettamusta [10] .

Esimerkiksi oikeanpuoleisen kuvan kaavio voidaan värittää 12 eri tavalla käyttämällä kolmea väriä. Periaatteessa sitä ei voi maalata kahdella värillä. 4 väriä käytettäessä saamme 24+4*12 = 72 väritysvaihtoehtoa: kun käytät kaikkia 4 väriä, niitä on 4! = 24 oikeaa tapaa ( jokainen 4 värin määritys mille tahansa 4 kärjen graafille on oikea); ja jokaista kolmea väriä kohden näistä neljästä on 12 erilaista väriä. Sitten esimerkin kaaviossa oikeiden värien lukumäärätaulukko alkaa seuraavasti:

Saatavilla useita värejä	yksi	2	3	neljä	…
Väritapojen lukumäärä	0	0	12	72	…

Esimerkin kaaviolle ja tietysti . $P(G,t)=t(t-1)^{2}(t-2)$ $P(G,4)=72$

Kromaattinen polynomi sisältää vähintään yhtä paljon väritystietoa kuin kromaattinen luku. Todellakin, on pienin positiivinen kokonaisluku, joka ei ole kromaattisen polynomin juuri. $G$ $\chi$

\chi (G)=\min\{t\,\kaksoispiste \,P(G,t)>0\}.

Joidenkin graafien kromaattiset polynomit

Kolmion muotoinen $K_{3}$	$t(t-1)(t-2)$
Täydellinen kaavio $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
puu kylkiluilla _ $n$	$t(t-1)^{{n}}$
Kierrä $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersenin kreivi	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Reunojen väritys

Graafin reunaväritys tarkoittaa värien osoittamista reunoihin siten, että kaksi samanväristä reunaa ei kuulu samaan kärkeen. Tämä ongelma vastaa kasvojen joukon jakamista itsenäisten kasvojen joukoiksi . Pienin graafin reunavärjäykseen tarvittava määrä värejä on sen kromaattinen indeksi eli reunan kromaattinen luku . $G$ $\chi '(G)$

Väritys yhteensä

Kokonaisvärjäys on eräänlainen graafin kärkien ja reunojen värjäys. Sillä tarkoitetaan sellaista värien määritystä, että vierekkäisillä pisteillä, vierekkäisillä reunoilla tai niitä yhdistävillä pisteillä ja reunoilla ei ole samaa väriä. Kuvaajan kromaattinen kokonaislukumäärä on pienin värien määrä, joka tarvitaan täydelliseen värjäämiseen. $\chi ''(G)$ $G$

Ominaisuudet

Kromaattisen polynomin ominaisuudet

Jos on tyhjä graafi [11] , $G$

P(G,t)=1

Jos graafi on hajaantuneiden osagraafien ja [11] liitto , $G$ $H$ $K$

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

Jos kohdassa [11] on silmukka , $G$

P(G,t)=0

Kromaattisten lukujen rajoitukset

Eri värien määrittäminen kaikkiin pisteisiin antaa aina oikean värityksen, joten

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

Ainoat kaaviot, jotka voidaan värjätä yhdellä värillä, ovat nollakuvaajat .
Täydellinen graafi , joka koostuu pisteistä, vaatii värejä. $K_n$ $n$ $\chi (K_{n})=n$
Optimaalisessa värityksessä jokaisen kahden väriluokan välillä tulee olla vähintään yksi graafin reuna, joten [12] $m$

{\näyttötyyli \chi (G)(\chi (G)-1)\leq 2m.}

Jos on unionin disjoint subgraphs ja , Sitten $G$ $H$ $K$

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

Jos sisältää klikejä , joiden koko on k , niin tämän klikkin värittämiseen tarvitaan vähintään k väriä, toisin sanoen kromaattinen luku on suurempi tai yhtä suuri kuin klikkiluku : $G$

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

Intervallikaavioille tämä rajoitus on tarkka.

Neljän värin teoreeman mukaan mikä tahansa tasograafi voidaan värjätä neljällä värillä.
Kaksiväriset graafit ovat kaksiosaisia kaavioita , mukaan lukien puut .

Graafi on kaksiosainen silloin ja vain, jos se ei sisällä parittoman pituisia syklejä [11] .

G

Ahne väritys osoittaa, että mikä tahansa graafi voidaan värjätä yhdellä värillä enemmän kuin sen maksimipisteaste [ 12] .

{\näyttötyyli \chi (G)\leq \Delta (G)+1.}

Täydellisissä grafiikoissa on ja , syklikaavioissa on ja , joten niille tämä rajoite on paras, kaikissa muissa tapauksissa rajoitusta voidaan parantaa: Brooksin lause [13] sanoo, että $\chi (G) = n$ $\Delta(G)=n-1$ $\chi (G) = 3$ $\Delta(G)=2$

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

yhdistetylle, yksinkertaiselle graafille if ei ole täydellinen kaavio eikä syklikaavio.

G

G

Kuvaajat, joissa on suuri kromaattinen luku

Suurilla klikkeillä varustetuissa kaavioissa on suuria kromaattisia lukuja, mutta päinvastoin ei aina ole totta. Grötzsch-graafi on esimerkki kolmiosta vapaasta 4-väritystä graafista, ja tämä esimerkki voidaan yleistää Mycielski-graafiksi .

Mychelskin lause (Alexander Zykov 1949, Jan Mychelski 1955): On olemassa graafisia kolmioita , joissa on mielivaltaisen suuria kromaattisia lukuja.

Brooksin lauseen mukaan graafilla, jolla on suuri kromaattinen luku, täytyy olla korkea maksimipisteaste. Toinen paikallinen ehto, jonka vuoksi kromaattinen luku voi olla suuri, on suuren klikkin läsnäolo. Mutta graafin värittävyys ei riipu vain paikallisista olosuhteista: graafi, jolla on suuri ympärysmitta , näyttää paikallisesti puulta, joten kaikki syklit ovat pitkiä, mutta sen kromaattinen luku ei ole yhtä suuri kuin 2:

Erdősin lause : On graafia, joilla on mielivaltaisen suuri ympärysmitta ja kromaattinen luku [12] .

Kromaattisen indeksin rajoitukset

Reunan väritys on sen viivagraafin kärkien värjäys . Tuo on $G$ $L(G)$

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

Lisäksi [14] ,

Königin lause : , jos on kaksiosainen.

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

G

Yleisesti ottaen yhteys on paljon vahvempi kuin Brooksin lause vertex-värjäyksestä [14] antaa :

Visingin lause: Graafilla , jolla on maksimipisteaste, on reunan kromaattinen numero tai .

\Delta

\Delta

\Delta +1

Muut ominaisuudet

Graafi on k - kromaattinen silloin ja vain, jos sillä on asyklinen orientaatio , jonka pisimmän polun pituus on k . Tämä todistettiin Gallai-Hasse-Roy-Vitaver-lauseella [15] .
Tasokaavioissa kärkiväritys vastaa nollan virtausta ei missään .
Äärettömistä kaavioista tiedetään paljon vähemmän. Alla on kaksi tulosta äärettömien kaavioiden värittämisestä.

Jos kaikki äärettömän graafin äärelliset osagraafit ovat k -kromaattisia, niin on myös k -kromaattisia (todistettu valintaaksiooman oletuksen perusteella ). Tämä on de Bruijn-Erdősin lauseen [16] muotoilu . $G$ $G$
Jos graafi sallii täydellisen n -värityksen mille tahansa , niin se sallii äärettömän täydellisen värityksen [17] . $n\geqslant n_{0}$

Avoimet kysymykset

Sen tason kromaattista lukua, jossa kaksi pistettä ovat vierekkäin, jos niiden välillä on yksikköetäisyys, ei tiedetä. Se voi olla 5, 6 tai 7. Muita avoimia kysymyksiä graafien kromaattisesta lukumäärästä ovat Hadwigerin arvelu , jonka mukaan minkä tahansa graafin, jonka kromaattinen luku on k , sivuna on täydellinen k pisteen graafi , Erdős-Faber-Lovas. oletus , joka rajoittaa täydellisten graafien kromaattista määrää, joilla on täsmälleen yksi yhteinen kärki jokaiselle graafiparille, ja Albertsonin olettamus, että k - kromaattisten graafien joukossa ne, joissa on vähiten leikkauskohtia, ovat täydellisiä .

Kun Birkov ja Lewis esittelivät kromaattisen polynomin yrittäessään ratkaista neljän värin lausetta, he väittivät, että tasograafien kohdalla polynomilla ei ole nollia alueella . Vaikka tiedetään, että sellaisella kromaattisella polynomilla ei ole nollia alueella , ja että , niiden väite jää todistamatta. Avoimeksi jää myös kysymys, kuinka erottaa graafit, joilla on sama kromaattinen polynomi, ja kuinka määrittää, että polynomi on kromaattinen. $G$ $P(G,t)$ $[4,\infty )$ $[5,\infty )$ $P(G,4)\neq 0$

Väritysalgoritmit

Polynomialgoritmit

Kaksiosaisessa graafissa väritysongelma lasketaan lineaarisessa ajassa käyttämällä leveyshakua . Täydellisten graafien tapauksessa kromaattinen luku ja sitä vastaava väritys voidaan löytää polynomiajassa käyttämällä puolimääräistä ohjelmointia . Tarkat kaavat kromaattisen luvun löytämiseksi tunnetaan monille graafiluokille (metsät, syklit , pyörät , sointukaaviot ) ja ne voidaan myös laskea polynomiajassa.

Tarkat algoritmit

Kattava hakualgoritmi k-värityksen tapauksessa ottaa huomioon kaikki väriasetelmien yhdistelmät graafissa, jossa on n kärkeä, ja tarkistaa niiden oikeellisuuden. Kromaattisen luvun ja kromaattisen polynomin laskemiseksi tämä algoritmi ottaa huomioon jokaisen k:n välillä 1 - n. Käytännössä tällaista algoritmia voidaan soveltaa vain pieniin kaavioihin. $k^{n}$

Käyttämällä dynaamista ohjelmointia ja arvioimalla suurimman riippumattoman joukon kokoa k-värityksen mahdollisuus graafissa voidaan ratkaista ajassa [18] . Tunnetaan nopeammat algoritmit 3- ja 4-värityksille, jotka toimivat ajassa [19] ja [20] , vastaavasti. $O(2 445^{n})$ $O(1,3289^{n})$ $O(1,7272^{n})$

Supistuminen

Vertex-supistus on operaatio, joka tekee graafista graafin tunnistamalla pisteet ja poistamalla niitä yhdistävät reunat ja korvaamalla ne yhdellä pisteellä, jossa kärkiin kohdistuvat reunat ohjataan uudelleen . Tällä toiminnolla on tärkeä rooli kuvaajan väritysanalyysissä. $G$ $g/uv$ $u$ $v$ $w$ $u$ $v$

Kromaattinen luku täyttää toistuvuussuhteen

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

missä ja ovat ei-viereisiä kärkipisteitä, on graafi, jossa on lisätty reuna . Jotkut algoritmit perustuvat tähän suhteeseen ja tuottavat tuloksena puun, jota joskus kutsutaan Zykov-puuksi. Suoritusaika riippuu kärjen valintamenetelmästä ja . $u$ $v$ $G+uv$ $UV$ $u$ $v$

Kromaattinen polynomi täyttää toistuvuusrelaation

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

jossa ja ovat vierekkäisiä kärkipisteitä, on graafi, jonka reuna on poistettu . edustaa graafin mahdollisten oikeiden värjäysten määrää, kun pisteillä ja voi olla samat tai eri värit. Jos ja niillä on eri värit, voimme harkita kaaviota, jossa ja ovat vierekkäin. Jos ja niillä on samat värit, voimme harkita kaaviota, jossa ja ovat yhdistetty. $u$ $v$ $G-uv$ $UV$ $P(G-uv,t)$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$ $u$ $v$

Yllä annetut lausekkeet johtavat rekursiiviseen menettelyyn, jota kutsutaan poista- ja sopimusalgoritmiksi , joka on muodostanut perustan monille graafin väritysalgoritmeille. Ajoaika täyttää saman toistuvuussuhteen kuin Fibonacci-luvut , joten pahimmassa tapauksessa algoritmi ajaa ajassa n kärkeä ja m reunaa [21] . Käytännössä haara- ja sidottumenetelmä sekä isomorfisten graafien hylkääminen välttävät joitain rekursiivisia kutsuja, ajoaika riippuu pisteparin valintamenetelmästä. $((1+{\sqrt 5})/2)^{{n+m}}=O(1,6180^{{n+m}})$

Ahne väritys

Ahne algoritmi lajittelee pisteet ,… ja antaa peräkkäin kärkipisteelle pienimmän saatavilla olevan värin, jota ei käytetty värjäämään naapureita joukossa ,…, tai lisää uuden. Tuloksena olevan värityksen laatu riippuu valitusta tilauksesta. Aina on järjestys, joka tuo ahneelle algoritmille optimaalisen värimäärän. Toisaalta ahne algoritmi voi olla mielivaltaisen huono; esimerkiksi kruunu , jossa on n kärkeä, voidaan värjätä kahdella värillä, mutta on olemassa kärkijärjestys, joka johtaa värien ahneeseen värjäämiseen. $v_{1}$ $v_{n}$ $v_{i}$ $v_{i}$ $v_{1}$ $v_{{i-1}}$ $\chi (G)$ $n/2$

Sointugraafille ja sen erikoistapauksille (kuten intervalligraafille ) ahneella väritysalgoritmilla voidaan löytää optimaalinen väritys polynomiajassa valitsemalla kärkien järjestys täydellisen eliminointijärjestyksen käänteiseksi . Tätä algoritmia voidaan soveltaa laajempaan graafiluokkaan (täysin järjestettävät graafit ), mutta tällaisen järjestyksen löytäminen tällaisille kaavioille on NP-kova ongelma.

Jos kärjet on järjestetty asteidensa mukaan, ahne väritysalgoritmi käyttää korkeintaan värejä, mikä on enintään 1 enemmän kuin (tässä kärjen aste ). Tätä heuristista algoritmia kutsutaan joskus Welsh-Powell-algoritmiksi [22] . Toinen algoritmi asettaa järjestyksen dynaamisesti ja valitsee seuraavan huippupisteen siitä, jossa on eniten vierekkäisiä erivärisiä kärkipisteitä. Monet muut graafin väritysalgoritmit perustuvat ahneeseen värjäämiseen ja käyttävät staattisia tai dynaamisia huippupisteiden järjestysstrategioita. $max_{i}min\{d(v_{i})+1,i\}$ $\Delta$ $d(v_{i})$ $v_{i}$

Rinnakkais- ja hajautetut algoritmit

Samanlainen ongelma esiintyy hajautettujen algoritmien alalla. Oletetaan, että graafin kärjet ovat tietokoneita, jotka voivat kommunikoida keskenään, jos ne on yhdistetty reunalla. Tavoitteena on, että jokainen tietokone valitsee itselleen "värin", jotta naapuritietokoneet valitsevat eri värit. Tämä ongelma liittyy läheisesti symmetrian murtumisongelmaan . Kehitetyimmät todennäköisyysalgoritmit ovat nopeampia kuin deterministiset algoritmit graafiille, joissa on riittävän suuri maksimipisteaste . Nopeimmat todennäköisyysalgoritmit käyttävät useiden yritysten tekniikkaa [23] . $\Delta$

Symmetrisissä kaavioissa deterministiset hajautetut algoritmit eivät löydä optimaalista kärkiväriä. Lisää tietoa tarvitaan symmetrian välttämiseksi. Vakiooletuksena on, että aluksi jokaisella kärjellä on yksilöllinen tunniste, esimerkiksi joukosta . Toisin sanoen oletetaan, että meille annetaan n - väri. Tehtävänä on vähentää värien lukumäärä n :stä esimerkiksi arvoon . Mitä enemmän värejä käytetään (esimerkiksi : n sijaan ), sitä vähemmän sanomia tarvitaan [23] . $\{1,2,...,N\}$ $(\Delta+1)$ $O(\Delta )$ $(\Delta+1)$

Yksinkertainen versio hajautetusta ahneesta -värjäysalgoritmistasta vaatii pahimmassa tapauksessa viestintäkierroksia – tiedot saattavat joutua kulkemaan verkon puolelta toiselle. $(\Delta+1)$ $\Theta(n)$

Yksinkertaisin mielenkiintoinen tapaus on n - sykli. Richard Cole ja Uzi Vishkin [24] ovat osoittaneet, että on olemassa hajautettu algoritmi, joka vähentää värien lukumäärän n :stä arvoon , käyttämällä vain yhtä naapuriviestintää. Toistamalla samaa menettelyä voidaan saada n -syklinen 3-värjäys yhteyskierroksilla (edellyttäen, että yksilölliset solmutunnisteet annetaan). $O(log(n))$ $O(log^{*}(n))$

Funktio , iteroitu logaritmi , on erittäin hitaasti kasvava funktio, "melkein vakio". Siksi Colen ja Vishkinin tulokset herättävät kysymyksen, onko olemassa hajautettua n-syklistä 3-väritysalgoritmia, joka toimii vakioajassa. Nathan Linial osoitti, että tämä on mahdotonta: mikä tahansa deterministinen hajautettu algoritmi vaatii viestintäkierroksia vähentääkseen N -värin 3-väriseksi n-syklissä [25] . $loki^{*}$ $\Omega (log^{*}(n))$

Colen ja Vishkinin tekniikkaa voidaan soveltaa myös mielivaltaiseen graafiin, jossa on rajoitettu kärkiaste, jolloin suoritusaika on [26] . Schneider ym . [27] on yleistänyt tämän menetelmän yksikköympyräkaavioon . $P(\Delta )+O(log^{*}(n))$

Reunojen väritysongelmaa on tutkittu myös hajautetussa mallissa. Pansonezzi ja Rizzi saavuttivat -värjäyksen tässä mallissa [28] . Linialin saavuttama hajautettujen pistevärjäysten alaraja soveltuu myös hajautettujen reunaväritysten ongelmaan [25] . $(2\Delta -1)$ $O(\Delta +log^{*}(n))$

Hajautetut algoritmit

Hajautettuja algoritmeja kutsutaan algoritmeiksi, joissa sisäinen viestien välittäminen ei ole sallittua (toisin kuin hajautetut algoritmit , joissa prosessit vaihtavat tietoja keskenään). On olemassa tehokkaita hajautettuja algoritmeja, jotka selviävät onnistuneesti graafien värittämisestä. Nämä algoritmit toimivat olettaen, että huippupiste pystyy "tuntemaan", että jollakin sen naapuripisteistä on sama väri kuin sillä. Toisin sanoen on mahdollista määritellä paikallinen konflikti. Tällainen ehto täyttyy varsin usein tosielämän sovelluksissa – esimerkiksi siirrettäessä dataa langattoman kanavan kautta lähettävällä asemalla on pääsääntöisesti kyky havaita, että toinen asema yrittää lähettää samanaikaisesti samalla kanavalla. Kyky hankkia tällaista tietoa riittää oppimisautomaatteihin perustuville algoritmeille ratkaisemaan oikein graafin väritysongelman [29] [30] todennäköisyydellä yksi .

Laskennallinen monimutkaisuus

Graafisten värjäys on laskennallisesti vaikea tehtävä. Sen selvittäminen, voiko graafi olla k - värinen tietylle k :lle, on NP-täydellinen tehtävä, lukuun ottamatta tapauksia k = 1 ja k = 2. Erityisesti kromaattisen luvun laskentaongelma on NP-kova [31] . . Kolmiväritysongelma on NP-täydellinen jopa 4-asteisen tasograafin tapauksessa [32] .

On myös NP-kova ongelma värjätä 3-värjättävä graafi 4 värillä [33] ja k -väritettävä graafi riittävän suurille k :n arvoille [34] . $k^{{log(k)/25}}$

Kromaattisen polynomin kertoimien laskeminen on #P-kova ongelma. On todistettu, ettei ole olemassa FPRAS- algoritmia kromaattisen polynomin laskemiseksi millekään muulle rationaaliluvulle k ≥ 1,5 kuin k = 2, ellei NP = RP [35] .

Sovellus

Suunnittelu

Vertex väritys mallintaa monia suunnitteluongelmia [36] . Yksinkertaisimmassa asetuksessaan tietty joukko töitä tulisi jakaa aikaväleille, jokainen tällainen työ vie yhden segmentin. Ne voidaan suorittaa missä tahansa järjestyksessä, mutta nämä kaksi työtä voivat olla ristiriidassa siinä mielessä, että niitä ei voida tehdä samanaikaisesti, koska ne käyttävät esimerkiksi yhteisiä resursseja. Vastaava graafi sisältää kullekin työlle kärjen ja kullekin ristiriitaiselle parille reunan. Muodostetun graafin kromaattinen numero on vähimmäisaika kaikkien töiden suorittamiseen ilman ristiriitoja.

Ajoitusongelman yksityiskohdat määräävät kaavion rakenteen. Esimerkiksi kun lentokoneet jaetaan lentoihin, tuloksena oleva konfliktikaavio on intervallikaavio , joten väritysongelma voidaan ratkaista tehokkaasti. Radiotaajuuksia jaettaessa saadaan yksikkökonfliktiympyröiden kuvaaja , ja tällaiselle ongelmalle on olemassa 3-approksimaatioalgoritmi .

Rekisterin allokaatio

Kääntäjä on tietokoneohjelma, joka kääntää yhden tietokonekielen toiseksi. Tuloksena olevan koodin suoritusajan parantamiseksi yksi kääntäjän optimointitekniikoista on rekisterin allokointi , jossa käännetyn ohjelman useimmin käytetyt muuttujat tallennetaan nopeiden prosessorien rekistereihin . Ihannetapauksessa muuttujat tallennetaan rekistereihin niin, että ne ovat kaikki rekistereissä niiden käyttöhetkellä.

Tavallinen lähestymistapa tähän ongelmaan on pelkistää se graafin väritysongelmaksi [8] . Kääntäjä rakentaa interferenssigraafin , jossa kärjet vastaavat muuttujia ja reuna yhdistää kaksi niistä, jos niitä tarvitaan samanaikaisesti. Jos tämä graafi on k -kromaattinen, muuttujat voidaan tallentaa k rekisteriin.

Digitaaliset vesileimat

Digitaalisten vesileimojen ( eng. digital watermarking ) tekniikan avulla voit siirtää piiloviestejä tietojen (olipa ne mediatiedostot , suoritettavat tiedostot ja muut) mukana (" vesileima ", vesileima ). Tällaista piiloviestiä voidaan käyttää tekijänoikeussuojassa tietojen omistajan tunnistamiseen.

Tämä on tärkeää esimerkiksi niiden laittoman jakelun lähteen selvittämiseksi. Tai vahvistaa oikeudet tietoihin, esimerkiksi - ohjelmistojärjestelmät sirulle ( system-on-chip ).

Viesti voidaan myös koodata tapaan, jolla rekistereitä allokoidaan. Yhtä tällaista tekniikkaa ehdottivat Qu ja Potkonjak [37] (siksi sitä kutsutaan joskus QP-algoritmiksi).

Se koostuu seuraavista: olkoon prosessorirekisterien jakauman yhteensopimattomuusgraafi (häiriögraafi), joka mainittiin edellä. Sen väritystä käytetään ohjelmassa - lisäksi sitä käytetään siten, että on sallittua muuttaa graafin sisältöä lisäämällä sen kromaattista numeroa hieman . Osoittautuu, että ohjelmistotuotteessa on mahdollista koodata viesti käyttämällä graafin väritystä eli rekisterien jakamista. $G$ $G$

Voit purkaa tämän viestin vertaamalla rekisterien jakautumista alkuperäiseen väritykseen; [38] On myös tapoja tarkistaa, onko viesti koodattu ohjelmaan ilman alkuperäistä.

Myöhemmin useat kirjailijat kehittivät ja jalostivat Qun ja Potkonjakin ajatuksia [39] . [38] [40]

Muut käyttötarkoitukset

Kuvaajan väritysongelma on esitetty monissa muissa sovelluksissa, mukaan lukien kuvioiden sovittaminen .

Sudoku -pulman ratkaiseminen voidaan ajatella tietyn 81 pisteen graafin 9-värisen värjäyksenä.

Muistiinpanot

↑ 1 2 3 ( Molloy & Reed 2002 , Perusmääritelmät )
↑ ( Donets & Shor 1982 , Historiallinen tausta )
↑ ( Kubale 2004 , Graafisen värityksen historia )
↑ ( van Lint & Wilson 2001 , luku 33)
↑ ( Jensen & Toft 1995 , s. 2)
↑ CE Shannon, "kohinaisen kanavan nollavirhekapasiteetti", IEEE Trans. Tietoteoria , s. 8-19, 1956.
↑ ( Zykov 1949 )
↑ 1 2 ( Chaitin 1982 )
↑ AOIvanov, AATuzhilin (2019), Gromov-Hausdorff Distance between Simplexes and Two-Distance Spaces , < https://arxiv.org/pdf/1907.09942.pdf > Arkistoitu 29. heinäkuuta 2019 Wayback Machinessa
↑ ( Birkhoff & Lewis 1946 )
↑ 1 2 3 4 ( Tutte 1984 , kromaattinen polynomi )
↑ 1 2 3 ( Diestel 2005 , Värityspisteet )
↑ ( Brooks & Tutte 1941 )
↑ 1 2 ( Diestel 2005 , Väritys reunat )
↑ ( Nesetřil & Ossona de Mendez 2012 )
↑ ( de Bruijn, Erdős 1951 )
↑ ( Fawcett 1978 )
↑ ( Lawler 1976 )
↑ ( Beigel & Eppstein 2005 )
↑ ( Fomin, Gaspers & Saurabh 2007 )
↑ ( Sekine, Imai & Tani 1995 )
↑ ( Welsh & Powell 1967 )
↑ 1 2 ( Schneider 2010 )
↑ ( Cole & Vishkin 1986 ), katso myös ( Cormen, Leiserson & Rivest 1990 , jakso 30.5)
↑ 1 2 ( Linial 1992 )
↑ ( Goldberg, Plotkin & Shannon 1988 )
↑ ( Schneider 2008 )
↑ ( Panconesi & Rizzi 2001 )
↑ ( Leith & Clifford 2006 )
↑ ( Duffy, O'Connell & Sapožnikov 2008 )
↑ ( Garey, Johnson & Stockmeyer 1974 ); ( Garey & Johnson 1979 ).
↑ ( Dailey 1980 )
↑ ( Guruswami & Khanna 2000 )
↑ ( Khot 2001 )
↑ ( Goldberg & Jerrum 2008 )
↑ ( Marx 2004 )
↑ ( Qu & Potkonjak 1998 )
↑ 1 2 ( Zhu & Thomborson 2006 )
↑ ( Collberg, Thomborson & Townsend 2004 )
↑ ( Myles & Collberg 2003 )

Kirjallisuus

Donets, G. A. & Shor, N. Z. (1982), An Algebraic Approach to the Plane Graph Coloring Problem , Naukova Dumka, s. 5-7
Zykov, A. A. (1949), Joistakin lineaaristen kompleksien ominaisuuksista , Mat. la T. 24(66) (2): 163–188 , < http://mi.mathnet.ru/eng/msb5974 >
Beigel, R. & Eppstein, D. (2005), 3-väritys ajassa O(1,3289 n ) , Journal of Algorithms , osa 54 (2)): 168–204 , DOI 10.1016/j.jalgor.2004.06.008
Birkhoff, G.D. & Lewis, D.C. (1946), Chromatic Polynomials , Trans. amer. Matematiikka. soc. T. 60 : 355-451 , >
Brélaz, D. (1979), Uusia menetelmiä graafin kärkien värittämiseen , Communications of the ACM , osa 22 (4): 251–256 , DOI 10.1145/359094.359101
Brooks, R.L. & Tutte, WT (1941), Verkon solmujen värittämisestä , Proceedings of the Cambridge Philosophical Society, osa 37 (2): 194–197 , DOI 10.1017/S030500410002168X
N. G. de Bruijn, P. Erdős . Väriongelma äärettömille kaavioille ja ongelma relaatioteoriassa (englanniksi) // Nederl. Akad. Wetensch. Proc. Ser. A. - 1951. - T. 54 . - S. 371-373 . (= Indag. Matem. 13 )
Byskov, JM (2004), Riippumattomien enimmäisjoukkojen luettelointi graafin värityksen sovelluksilla , Operations Research Letters , osa 32 (6): 547–556 , DOI 10.1016/j.orl.2004.03.002
Cormen, T.H.; Leiserson, CE & Rivest, RL (1990), Introduction to Algorithms (1. painos), 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), Rekisterin allokointi ja levittäminen graafin värityksen kautta , 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), Deterministinen kolikonheitto sovelluksilla optimaaliseen rinnakkaisjärjestykseen
Dailey, D.P. (1980), Tasomaisten 4-säännöllisten graafien värittävyyden ainutlaatuisuus ja värittävyys ovat NP-täydellisiä , Discrete Mathematics, osa 30 (3): 289-293 , DOI 10.1016/0012-365X(80-80236)
Diestel, R. (2005), Graph theory , < http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf > Arkistoitu 25. marraskuuta 2014 Wayback Machinessa
Duffy, K.; O'Connell, N. & Sapozhnikov, A. (2008), Hajautetun graafin väritysalgoritmin kompleksisuusanalyysi , Information Processing Letters, osa 107: 60–63, doi : 10.1016/j.ipl.2008.01.002 , < http: //www.hamilton.ie/ken_duffy/Downloads/cfl.pdf >
Fawcett, BW (1978), On infinite full colorings of graphs, 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 , voi. 4598, Lecture Notes in Computer Science , Springer, s. 65-74, ISBN 978-3-540-73544-1
Garey, MR & Johnson, DS (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, ISBN 0-7167-1045-5
Goldberg, LA & Jerrum, M. (heinäkuu 2008), Tutte-polynomin inapproximability , Information and Computation vol. 206 (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 , osa 1 (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 , s. 188–197, ISBN 0-7695-0674-7 , DOI 10.1109/CCC.2000.856749
Jaeger, F.; Vertigan, DL & Welsh, DJA (1990), Jonesin ja Tutten polynomien laskennallinen monimutkaisuus , Mathematical Proceedings of the Cambridge Philosophical Society , osa 108: 35–53 , DOI 10.1017/S030506891360
Jensen, Tommy R. & Toft, Bjarne (1995), Graph Coloring Problems , John Wiley & Sons, ISBN 0-471-02865-7
Khot, S. (2001), MaxCliquen, kromaattisen luvun ja likimääräisen graafin värityksen , parannetut epäsuorat tulokset , Proc. 42nd Annual Symposium on Foundations of Computer Science , s. 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), Heikko graafin väritys: hajautetut algoritmit ja sovellukset , Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures , s. 138–144, ISBN 978-1-60558-606-9
Lawler, EL (1976), Huomautus kromaattisten lukujen ongelman monimutkaisuudesta , Information Processing Letters, osa 5 (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), Locality in distributed graph algorithms , SIAM Journal on Computing osa 21 (1): 193-201 , DOI 10.1137/0221015
van Lint, JH & Wilson, R.M. (2001), A Course in Combinatorics (2. painos), Cambridge University Press, ISBN 0-521-80340-3
Molloy, Michael & Reed, Bruce (2002), Graafin väritys ja todennäköisyysmenetelmä , Springer, ISBN 3-540-42139-4 , ISSN 0937-5511
Marx, Dániel (2004), Graafisten väritysongelmat ja niiden sovellukset ajoituksessa, Periodica Polytechnica, Electrical Engineering , voi. 48, s. 11–16, CiteSeerX: 10.1.1.95.4268
Mycielski, J. (1955), Sur le coloriage des graphes , Colloq. Matematiikka. Vol. 3: 161–162 , < http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf > .

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

Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Lause 3.13 , Sparity: Graphs, Structures, and Algorithms , voi. 28, Algorithms and Combinatorics, Heidelberg: Springer, s. 42, ISBN 978-3-642-27874-7 , DOI 10.1007/978-3-642-27875-4 .
Panconesi, Alessandro & Rizzi, Romeo (2001), Joitakin yksinkertaisia hajautettuja algoritmeja harvaan verkkoon , hajautettu tietotekniikka (Berlin, New York: Springer-Verlag ). — V. 14 (2): 97–100, ISSN 0178-2770 , DOI 10.1007/PL00008932
Panconesi, A. & Srinivasan, A. (1996), Hajautetun verkon hajoamisen monimutkaisuudesta, Journal of Algorithms , voi. kaksikymmentä
Qu, Gang & Potkonjak, Miodrag (1998), Vesileimaustekniikoiden analyysi graafin väritysongelmaan , ICCAD , s. 190-193 , DOI 10.1145/288548.288607
Schneider, J. (2010), Uusi tekniikka hajautetun symmetrian rikkomiseen , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf > Arkistoitu 30. heinäkuuta 2013 Wayback Machine
Schneider, J. (2008), A log-star hajoitettu maksimaalisen riippumattoman joukko-algoritmi kasvurajoitteisille kaavioille , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podc08SW. pdf > Arkistoitu 30. heinäkuuta 2013 Wayback Machinessa
Sekine, K.; Imai, H. & Tani, S. (1995), Computing the Tutte polynomial of a graph of medium size , Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995) , voi. 1004, Lecture Notes in Computer Science , Springer, s. 224–233, ISBN 3-540-60573-8 , DOI 10.1007/BFb0015427
Tutte, WT (1984), Graafiteoria , Matematiikan ja sovellusten tietosanakirja (Cambridge University Press). - Osa 21, ISBN 0-521-30241-2
Welsh, DJA & Powell, MB (1967), Kuvaajan kromaattisen luvun yläraja ja sen soveltaminen aikatauluongelmiin , The Computer Journal osa 10 (1): 85–86 , DOI 10.1093/comjnl/10.1.85
Wilf, H. S. (1986), Algorithms and Complexity , Prentice-Hall
Zhu, William & Thomborson, Clark (2006), Tunnistus ohjelmistojen vesileimauksessa , MCPS '06: 4. ACM:n sisällön suojaamista ja turvallisuutta käsittelevän kansainvälisen työpajan julkaisut , ACM, s. 29–36, ISBN 1-59593-499-5 , DOI 10.1145/1178766.1178776