Barevné grafy

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. června 2019; kontroly vyžadují 15 úprav .

Barvení grafu je grafově teoretická konstrukce ,speciální případ značení grafů . Při vybarvování jsou prvkům grafu přiřazeny štítky s určitými omezeními; tyto štítky jsou tradičně označovány jako "barvy". V nejjednodušším případě se takový způsob obarvení vrcholů grafu , kdy libovolné dva sousední vrcholy odpovídají různým barvám, nazývá zbarvení vrcholů . Podobně barvení hran přiřadí barvu každé hraně, takže jakékoli dvě sousední hrany mají různé barvy [1] . Nakonec zbarvení oblasti rovinného grafu přiřadí barvu každé oblasti, takže každé dvě oblasti, které sdílejí hranici, nemohou mít stejnou barvu.

Barvení vrcholů je hlavním problémem barvení grafů, všechny ostatní problémy v této oblasti lze redukovat na něj. Například obarvení okrajů grafu je obarvením vrcholů jeho spojnicového grafu a obarvení oblastí rovinného grafu je obarvením vrcholů jeho duálního grafu [1] . Jiné problémy s vybarvováním grafů jsou však často kladeny a řešeny v původním nastavení. Důvodem je částečně to, že poskytuje lepší představu o tom, co se děje a je více odhalující, a částečně to, že některé problémy je pohodlnější řešit tímto způsobem (například barvení hran).

Barvení grafů nachází uplatnění v mnoha praktických oblastech, a to nejen v teoretických problémech. Kromě klasických typů problémů lze na graf, na způsob přiřazování barev nebo na barvy samotné klást také různá omezení. Tato metoda se používá například v populárním sudoku . V této oblasti stále probíhá aktivní výzkum.

Historie

První výsledky byly získány pro rovinné grafy v problému barvení mapy. Ve snaze vybarvit mapu anglických hrabství Francis Guthrie formuloval čtyřbarevný problém a poznamenal, že čtyři barvy postačují k obarvení mapy tak, aby jakékoli dvě sousední oblasti měly různé barvy. Jeho bratr postoupil otázku svému učiteli matematiky Augustu de Morganovi , který se o ní zmínil ve svém dopise Williamu Hamiltonovi v roce 1852. Arthur Cayley nastolil tento problém na setkání London Mathematical Society v roce 1878. Ve stejném roce Tate navrhl první řešení tohoto problému. Zredukoval obarvení vrcholů původního grafu na obarvení hran duálního grafu a navrhl, že tento problém má vždy řešení [2] . V roce 1880 Alfred Kempe publikoval článek prohlašující, že se mu podařilo stanovit výsledek, a po desetiletí byl problém čtyř barev považován za vyřešený. Za tento úspěch byl Kempe zvolen členem Royal Society of London a později prezidentem London Mathematical Society [3] .

V roce 1890 Heawood našel chybu v Kempeho důkazu. Ve stejném článku dokázal větu o pěti barvách , ukazující, že jakákoli plochá mapa může být obarvena nejvýše pěti barvami. Přitom se opíral o myšlenky Kempeho. V příštím století bylo vyvinuto velké množství teorií ve snaze snížit minimální počet barev. Teorém čtyř barev byl nakonec prokázán v roce 1977 vědci Kenneth Appel a Wolfgang Haken pomocí počítačového výčtu. Myšlenka důkazu se silně opírala o myšlenky Heawooda a Kempeho a ignorovala většinu středně pokročilých studií [4] . Důkaz věty o čtyřech barvách je jedním z prvních důkazů, ve kterých byl použit počítač.

V roce 1912 navrhl George David Birkhoff použít chromatický polynom , důležitou součást algebraické teorie grafů, ke studiu problémů s barvením . Chromatický polynom následně zobecnil William Tutt ( Tuttův polynom ). Kempe v roce 1879 již upozornil na obecný případ, kdy graf nebyl rovinný [5] . Na počátku 20. století se objevilo mnoho výsledků zobecnění grafů barevných rovin na plochách vyšších řádů.

V roce 1960 formuloval Claude Burge dokonalou domněnku o grafu motivovanou pojmem z teorie informace , konkrétně nulovou chybou kapacity grafu [6] zavedenou Shannonem . Toto tvrzení zůstalo nepotvrzené po dobu 40 let, dokud jej v roce 2002 nepotvrdili jako slavná přísná věta o dokonalém grafu matematiky Chudnovskaya , Robertson , Seymour a Thomas .

Barvení grafu jako algoritmický problém bylo studováno od 70. let 20. století: určení chromatického čísla je jedním z 21 Karpových NP-úplných problémů (1972). A přibližně ve stejné době byly vyvinuty různé algoritmy založené na backtrackingu a Zykovově rekurzivním mazání a kontrakci [7] . Od roku 1981 se pro alokaci registrů v kompilátorech používá barvení grafů [8] .

Definice a terminologie

Barvení vrcholu

Když lidé mluví o vybarvování grafů, téměř vždy mají na mysli vybarvování jejich vrcholů, tedy přiřazování barevných štítků vrcholům grafu tak, aby libovolné dva vrcholy, které mají společnou hranu, měly různé barvy. Vzhledem k tomu , že smyčkové grafy nelze tímto způsobem vybarvit, nepřipadají v úvahu.

Terminologie, ve které se štítky nazývají barvy, pochází z kolorování politických map. Štítky jako červená nebo modrá se používají pouze v případě, že je počet barev malý, ale obvykle se předpokládá, že štítky jsou celá čísla . $\{1,2,3,...\}$

Barvení barvami se nazývá -coloring . Nejmenší počet barev potřebný k obarvení grafu se nazývá jeho chromatické číslo a často se zapisuje jako . Někdy se používá , protože označuje Eulerovu charakteristiku . Podmnožina vrcholů zvýrazněných jednou barvou se nazývá třída barev , každá taková třída tvoří nezávislou množinu . -coloring je tedy totéž jako dělení vrcholů na nezávislé množiny [1] . $k$ $k$ $G$ $\chi (G)$ $\gamma (G)$ $\chi (G)$ $k$ $k$

Chromatické číslo z hlediska vzdálenosti Gromov-Hausdorff

Dovolit být libovolný graf s vertex set . Zafixujeme dvě kladná reálná čísla a budeme je považovat za metrický prostor, ve kterém jsou vzdálenosti mezi sousedními vrcholy rovné , a všechny ostatní nenulové vzdálenosti se rovnají . Označme metrickým prostorem sestávajícím z bodů oddělených od sebe vzdáleností . Nakonec pro libovolné dva metrické prostory a označte Gromov -Hausdorffovu vzdálenost mezi a . Pak platí následující výsledek. $G$ $PROTI$ $a<b\leq 2a$ $PROTI$ $b$ $A$ ${\displaystyle a\Delta _{m))$ $m$ $A$ $X$ $Y$ $d_{GH}(X,Y)$ $X$ $Y$

Věta (A.O. Ivanov, A.A. Tuzhilin) [9] : Nechť je největší přirozené číslo, pro které (pokud taková přirozená čísla neexistují, nastavíme ). Pak .

m

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

m=0

\chi (G)=m+1

Komentář.

Chromatické číslo je , právě tehdy, když graf neobsahuje žádné hrany. V tomto případě rovnost neplatí pro žádné , tedy podle konvence, , což vede ke správné rovnosti . $\chi (G)$ $jeden$ $G$ $d_{GH}(V,a\Delta _{m})=b$ $m$ $m=0$ $\chi (G)=0+1=1$

Podle definice nepřesahuje počet prvků sady . Na druhou stranu je snadné ukázat, že pro každý , tedy a, tedy, . $\chi (G)$ $n$ $PROTI$ $d_{GH}(V,a\Delta _{p})\leq \max\{a,\,ba\}<b$ $p\geq n$ $m<n$ $\chi (G)=m+1\leq n$

Chromatický polynom

Chromatický polynom je funkce , která počítá počet t - zabarvení grafu . Z názvu vyplývá, že pro danou funkci je polynom závislý na t . $P(G,t)$ $G$ $G$

Tuto skutečnost objevili Birkhoff a Lewis, když se snažili dokázat čtyřbarevnou domněnku [10] .

Například graf na obrázku vpravo lze vybarvit 12 způsoby pomocí 3 barev. V zásadě nelze natírat dvěma barvami. Použitím 4 barev získáme 24+4*12 = 72 možností vybarvení: při použití všech 4 barev jsou 4! = 24 správných způsobů ( každé přiřazení 4 barev pro libovolný graf 4 vrcholů je správné); a na každé 3 barvy z těchto 4 existuje 12 způsobů, jak vybarvit. Pak pro graf v příkladu bude tabulka počtů správných barev začínat takto:

Dostupné množství barev	jeden	2	3	čtyři	…
Množství způsobů, jak vybarvit	0	0	12	72	…

Pro graf v příkladu a samozřejmě . $P(G,t)=t(t-1)^{2}(t-2)$ $P(G,4)=72$

Chromatický polynom obsahuje alespoň tolik informací o kolorizovatelnosti jako chromatické číslo. Ve skutečnosti je nejmenší kladné celé číslo, které není kořenem chromatického polynomu. $G$ $\chi$

\chi (G)=\min\{t\,\dvojtečka \,P(G,t)>0\}.

Chromatické polynomy pro některé grafy

Trojúhelníkový $K_{3}$	$t(t-1)(t-2)$
Kompletní graf $K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
strom s žebry $n$	$t(t-1)^{{n}}$
Cyklus $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
hrabě z Petersenu	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Barvení okrajů

Barvení hran grafu znamená přiřazování barev hranám tak, aby žádné dvě hrany stejné barvy nepatřily ke stejnému vrcholu. Tento problém je ekvivalentní rozdělení sady ploch na sady nezávislých ploch . Nejmenší počet barev potřebný pro obarvení hran grafu je jeho chromatický index neboli chromatické číslo hran . $G$ $\chi '(G)$

Celkové zbarvení

Celkové zbarvení je typ obarvení vrcholů a hran grafu. Myslí se tím takové přiřazení barev, že ani sousední vrcholy, ani sousední hrany, ani vrcholy a hrany, které je spojují, nemají stejnou barvu. Celkové chromatické číslo grafu je nejmenší počet barev potřebný k úplnému vybarvení. $\chi ''(G)$ $G$

Vlastnosti

Vlastnosti chromatického polynomu

Pokud je graf prázdný [11] , $G$

P(G,t)=1

Pokud je graf spojením disjunktních podgrafů a [11] , $G$ $H$ $K$

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

Pokud je v [11] smyčka , $G$

P(G,t)=0

Omezení chromatického čísla

Přiřazení různých barev všem vrcholům vždy dává správné vybarvení, takže

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

Jediným druhem grafů, které lze vybarvit jednou barvou, jsou nulové grafy .
Kompletní graf skládající se z vrcholů vyžaduje barvy. $K_n$ $n$ $\chi (K_{n})=n$
Při optimálním vybarvení musí být mezi každým dvěma barevnými třídami alespoň jedna hrana grafu, takže [12] $m$

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

Jestliže je spojení disjunktních podgrafů a , pak $G$ $H$ $K$

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

Pokud obsahuje kliky o velikosti k , pak je k vybarvení této kliky potřeba alespoň k barev, jinými slovy, chromatické číslo je větší nebo rovno číslu kliky : $G$

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

U intervalových grafů je toto omezení přesné.

Podle teorému o čtyřech barvách může být libovolný rovinný graf obarven čtyřmi barvami.
2-barevné grafy jsou bipartitní grafy , včetně stromů .

Graf je bipartitní právě tehdy, když neobsahuje cykly liché délky [11] .

G

Nenásytné zbarvení ukazuje, že každý graf může být obarven pomocí jedné barvy více, než je jeho maximální vrcholový stupeň [12] .

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

Kompletní grafy mají a , grafy cyklů mají a , takže pro ně je toto omezení nejlepší, ve všech ostatních případech lze omezení zlepšit: Brooksova věta [13] říká, že $\chi (G)=n$ $\Delta(G)=n-1$ $\chi (G) = 3$ $\Delta(G)=2$

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

pro souvislý jednoduchý graf if není ani úplný graf, ani graf cyklu.

G

G

Grafy s velkým chromatickým číslem

Grafy s velkými klikami mají velká chromatická čísla, ale opak není vždy pravdou. Grötzschův graf je příkladem čtyřbarevného grafu bez trojúhelníků a tento příklad lze zobecnit na Mycielského graf .

Mychelského věta (Alexander Zykov 1949, Jan Mychelski 1955): Existují grafy bez trojúhelníků s libovolně velkými chromatickými čísly.

Z Brooksovy věty vyplývá, že grafy s velkým chromatickým číslem musí mít vysoký maximální vrcholový stupeň. Další místní podmínkou, kvůli které může být chromatické číslo velké, je přítomnost velké kliky. Obarvitelnost grafu však nezávisí pouze na místních podmínkách: graf s velkým obvodem lokálně vypadá jako strom, takže všechny cykly jsou dlouhé, ale jeho chromatické číslo není rovno 2:

Erdősův teorém : Existují grafy s libovolně velkým obvodem a chromatickým číslem [12] .

Omezení chromatického indexu

Barvení hran je zbarvení vrcholů jeho spojnicového grafu . To znamená $G$ $L(G)$

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

Navíc [14 ]

Königova věta : , je-li bipartitní.

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

G

Obecně je spojení mnohem silnější než Brooksův teorém pro barvení vrcholů [14] dává :

Vizingův teorém: Graf s maximálním vrcholovým stupněm má hranové chromatické číslo nebo .

\Delta

\Delta

\Delta +1

Další vlastnosti

Graf je k - chromatický právě tehdy, když má acyklickou orientaci , pro kterou je délka nejdelší cesty k . To bylo prokázáno v Gallai-Hasse-Roy-Vitaverově větě [15] .
U rovinných grafů je zbarvení vrcholu ekvivalentní nulovému toku nikde .
Mnohem méně se ví o nekonečných grafech. Níže jsou uvedeny dva výsledky pro vybarvování nekonečných grafů.

Jestliže všechny konečné podgrafy nekonečného grafu jsou k -chromatické , pak je i k - chromatické (dokázáno za předpokladu axiomu výběru ). Toto je formulace de Bruijn-Erdősovy věty [16] . $G$ $G$
Pokud graf připouští úplné n -zabarvení pro libovolné , pak připouští nekonečné úplné zabarvení [17] . $n\geqslant n_{0}$

Otevřené otázky

Není známo chromatické číslo roviny, ve které sousedí dva body, pokud je mezi nimi jednotková vzdálenost. Může to být 5, 6 nebo 7. Mezi další otevřené otázky o chromatickém počtu grafů patří Hadwigerova domněnka , která říká, že každý graf s chromatickým číslem k má úplný graf k vrcholů jako svůj vedlejší , Erdős-Faber-Lovas domněnka , která omezuje chromatický počet úplných grafů, které mají přesně jeden společný vrchol pro každou dvojici grafů, a Albertsonova domněnka, že mezi k - chromatickými grafy jsou úplné ty s nejmenším počtem průniků .

Když Birkov a Lewis představili chromatický polynom ve svém pokusu vyřešit čtyřbarevnou větu, tvrdili, že pro rovinné grafy nemá polynom žádné nuly v oblasti . Ačkoli je známo, že takový chromatický polynom nemá nuly v oboru , a že , jejich tvrzení zůstává neprokázané. Otevřenou otázkou také zůstává, jak rozlišit grafy se stejným chromatickým polynomem a jak určit, že polynom je chromatický. $G$ $P(G,t)$ $[4,\infty )$ $[5,\infty )$ $P(G,4)\neq 0$

Algoritmy barvení

Polynomiální algoritmy

U bipartitního grafu je problém zbarvení vypočítán v lineárním čase pomocí prohledávání do šířky . V případě dokonalých grafů lze chromatické číslo a jeho odpovídající zabarvení nalézt v polynomiálním čase pomocí semidefinitního programování . Přesné vzorce pro nalezení chromatického čísla jsou známy pro mnoho tříd grafů (lesy, cykly , kola , akordické grafy ) a lze je vypočítat i v polynomiálním čase.

Přesné algoritmy

Vyčerpávající vyhledávací algoritmus pro případ k-barvení bere v úvahu všechny kombinace barevných uspořádání v grafu s n vrcholy a kontroluje jejich správnost. Pro výpočet chromatického čísla a chromatického polynomu tento algoritmus uvažuje každé k od 1 do n. V praxi lze takový algoritmus aplikovat pouze na malé grafy. $k^{n}$

Pomocí dynamického programování a odhadu velikosti největší nezávislé množiny lze v čase vyřešit možnost k-zabarvení v grafu [18] . Jsou známy rychlejší algoritmy pro 3 a 4 zbarvení, které běží v čase [19] a [20] . $O(2,445^{n})$ $O(1,3289^{n})$ $O(1,7272^{n})$

Kontrakce

Kontrakce vrcholu je operace, která vytvoří graf z grafu identifikací vrcholů a odstraněním hran, které je spojují, a jejich nahrazením jedním vrcholem , kde hrany dopadají na vrcholy a jsou přesměrovány . Tato operace hraje důležitou roli v analýze barevnosti grafu. $G$ $fotr$ $u$ $proti$ $w$ $u$ $proti$

Chromatické číslo splňuje rekurenci opakování

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

kde a jsou nesousedící vrcholy, je graf s přidanou hranou . Některé algoritmy jsou založeny na tomto poměru a ve výsledku vytvářejí strom, někdy nazývaný Zykovův strom. Doba provedení závisí na metodě výběru vrcholu a . $u$ $proti$ $G+uv$ $UV$ $u$ $proti$

Chromatický polynom splňuje rekurenci

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

kde a jsou sousední vrcholy, je graf s odstraněnou hranou . představuje počet možných správných zabarvení grafu, kdy vrcholy a mohou mít stejné nebo různé barvy. Pokud a mají různé barvy, pak můžeme uvažovat o grafu, kde a spolu sousedí. Pokud a mají stejné barvy, můžeme uvažovat o grafu, kde a jsou sloučeny. $u$ $proti$ $Fotr$ $UV$ $P(G-uv,t)$ $u$ $proti$ $u$ $proti$ $u$ $proti$ $u$ $proti$ $u$ $proti$

Výše uvedené výrazy vedou k rekurzivní proceduře nazývané algoritmus odstranění a kontraktace , který vytvořil základ pro mnoho algoritmů pro barvení grafů. Doba běhu splňuje stejný vztah opakování jako Fibonacciho čísla , takže v nejhorším případě algoritmus poběží v čase pro n vrcholů a m hran [21] . V praxi se metoda větvení a vazby a odmítnutí izomorfních grafů vyhnou některým rekurzivním voláním, doba běhu závisí na metodě výběru dvojice vrcholů. $((1+{\sqrt 5})/2)^{{n+m}}=O(1,6180^{{n+m}})$

Lakomé zbarvení

Nenásytný algoritmus seřadí vrcholy ,…, a postupně přiřadí vrcholu nejmenší dostupnou barvu, která nebyla použita k obarvení sousedů mezi ,…, nebo přidá novou. Kvalita výsledného zbarvení závisí na zvoleném pořadí. Vždy existuje objednávka, která přivede chamtivý algoritmus k optimálnímu počtu barev. Na druhou stranu, chamtivý algoritmus může být libovolně špatný; například koruna s n vrcholy může být obarvena 2 barvami, ale existuje pořadí vrcholů, které má za následek žravé zbarvení barev. $v_{1}$ $v_{n}$ $v_{i}$ $v_{i}$ $v_{1}$ $v_{{i-1}}$ $\chi (G)$ $n/2$

Pro akordický graf a pro jeho speciální případy (jako je intervalový graf ) lze použít algoritmus chamtivého zbarvení k nalezení optimálního zbarvení v polynomiálním čase výběrem pořadí vrcholů tak, aby bylo obrácené k dokonalému eliminačnímu řádu . Tento algoritmus lze aplikovat na širší třídu grafů ( zcela uspořádané grafy ), ale nalezení takového pořadí pro takové grafy je NP-těžký problém.

Pokud jsou vrcholy seřazeny podle jejich stupňů, použije algoritmus greedy coloring maximálně barev, což je maximálně o 1 více než (zde stupeň vrcholu ). Tento heuristický algoritmus se někdy nazývá Welsh-Powellův algoritmus [22] . Jiný algoritmus nastavuje pořadí dynamicky a vybírá další vrchol z toho s nejvíce sousedícími vrcholy různých barev. Mnoho dalších algoritmů pro vybarvování grafů je založeno na chamtivém vybarvování a používá statické nebo dynamické strategie řazení vrcholů. $max_{i}min\{d(v_{i})+1,i\}$ $\Delta$ $d(v_{i})$ $v_{i}$

Paralelní a distribuované algoritmy

Podobný problém nastává v oblasti distribuovaných algoritmů. Řekněme, že vrcholy grafu jsou počítače, které spolu mohou komunikovat, pokud jsou spojeny hranou. Cílem je, aby si každý počítač vybral "barvu" sám pro sebe, aby sousední počítače zvolily různé barvy. Tento problém úzce souvisí s problémem narušení symetrie . Nejrozvinutější pravděpodobnostní algoritmy jsou rychlejší než deterministické algoritmy pro grafy s dostatečně velkým maximálním stupněm vrcholů . Nejrychlejší pravděpodobnostní algoritmy využívají techniku více pokusů [23] . $\Delta$

V symetrických grafech nemohou deterministické distribuované algoritmy najít optimální zbarvení vrcholů. Aby se zabránilo symetrii, je potřeba více informací. Standardní předpoklad je, že zpočátku má každý vrchol jedinečný identifikátor, například z množiny . Jinými slovy, předpokládá se, že máme n - zabarvení. Úkolem je snížit počet barev z n například na . Čím více barev se použije (například místo ), tím méně výměn zpráv bude vyžadováno [23] . $\{1,2,...,N\}$ $(\Delta+1)$ $O(\Delta)$ $(\Delta+1)$

Jednoduchá verze distribuovaného greedy algoritmu pro -coloring vyžaduje v nejhorším případě komunikační kola – informace se možná budou muset přesunout z jednoho konce sítě na druhý. $(\Delta+1)$ $\Opalování)$

Nejjednodušší zajímavý případ je n -cyklus. Richard Cole a Uzi Vishkin [24] ukázali, že existuje distribuovaný algoritmus, který redukuje počet barev z n na , za použití pouze jednoho sousedského zasílání zpráv. Opakováním stejného postupu lze získat n -cyklové 3 zbarvení v kolech spojení (za předpokladu, že jsou uvedeny jedinečné identifikátory uzlů). $O(log(n))$ $O(log^{*}(n))$

Funkce , iterovaný logaritmus , je extrémně pomalu rostoucí funkce, „téměř konstanta“. Proto výsledky Colea a Vishkina vyvolávají otázku, zda existuje distribuovaný n-cyklový 3-barevný algoritmus, který běží v konstantním čase. Nathan Linial ukázal, že to není možné: jakýkoli deterministický distribuovaný algoritmus vyžaduje komunikační kola k redukci N -zabarvení na 3-zabarvení v n-cyklu [25] . $log^{*}$ $\Omega (log^{*}(n))$

Techniku Colea a Vishkina lze aplikovat i na libovolný graf s omezeným stupněm vrcholů, v takovém případě je doba běhu [26] . Tuto metodu zobecnili na jednotkový kruhový graf Schneider et al [27] . $P(\Delta )+O(log^{*}(n))$

Problém zbarvení okrajů byl také studován v distribuovaném modelu. Pansonezzi a Rizzi dosáhli v tomto modelu zabarvení pro [28] . Spodní mez pro distribuované zbarvení vertexů dosaženou Linialem je také použitelná pro problém distribuovaného zbarvení hran [25] . $(2\Delta -1)$ $O(\Delta +log^{*}(n))$

Decentralizované algoritmy

Decentralizované algoritmy se nazývají algoritmy, ve kterých není povoleno vnitřní předávání zpráv (na rozdíl od distribuovaných algoritmů , kde si procesy mezi sebou vyměňují data). Existují účinné decentralizované algoritmy, které se úspěšně vypořádají s úkolem vybarvování grafů. Tyto algoritmy pracují na předpokladu, že vrchol je schopen „cítit“, že kterýkoli z jeho sousedních vrcholů má stejnou barvu jako on. Jinými slovy, je možné definovat lokální konflikt. Taková podmínka je poměrně často splněna v reálných aplikacích — například při přenosu dat bezdrátovým kanálem má vysílající stanice zpravidla schopnost detekovat, že se jiná stanice pokouší vysílat současně na stejném kanálu. Schopnost získat takové informace je dostatečná pro algoritmy založené na učících automatech ke správnému vyřešení problému barvení grafu [29] [30] s pravděpodobností jedna .

Výpočetní složitost

Barvení grafu je výpočetně náročný úkol. Zjistit , zda lze graf pro dané k -obarvit, je NP-úplný problém, kromě případů k = 1 a k = 2. Zejména problém výpočtu chromatického čísla je NP-těžký [31] . Problém 3 zbarvení je NP-úplný i pro případ rovinného grafu stupně 4 [32] .

NP-těžký problém je také obarvit 3-barevný graf 4 barvami [33] a k -obarvitelný graf pro dostatečně velké hodnoty k [34] . $k^{{log(k)/25}}$

Počítání koeficientů chromatického polynomu je #P-těžký problém. Bylo prokázáno, že neexistuje žádný algoritmus FPRAS pro výpočet chromatického polynomu pro jakékoli jiné racionální číslo k ≥ 1,5 než k = 2, pokud NP = RP [35] .

Aplikace

Plánování

Barvení vertexů modeluje mnoho plánovacích problémů [36] . Ve svém nejjednodušším nastavení by daná sada úloh měla být rozložena v časových intervalech, každá taková úloha zabírá jeden segment. Mohou být provedeny v libovolném pořadí, ale tyto dvě úlohy mohou být v konfliktu v tom smyslu, že je nelze provést současně, protože například využívají sdílené zdroje. Odpovídající graf obsahuje vrchol pro každou úlohu a hranu pro každý konfliktní pár. Barevné číslo vytvořeného grafu je minimální doba pro dokončení všech úloh bez konfliktů.

Podrobnosti problému plánování určují strukturu grafu. Například, když dojde k rozdělení letadel na lety, výsledný konfliktní graf je intervalový graf , takže problém zbarvení lze efektivně vyřešit. Při distribuci rádiových frekvencí se získá graf jednotkových konfliktních kruhů a pro takový problém existuje 3-aproximační algoritmus .

Registrovat přidělení

Kompilátor je počítačový program , který překládá jeden počítačový jazyk do druhého. Pro zlepšení doby provádění výsledného kódu je jednou z technik optimalizace kompilátoru alokace registrů , ve které jsou nejčastěji používané proměnné kompilovaného programu uloženy v registrech vysokorychlostního procesoru . V ideálním případě jsou proměnné uloženy v registrech tak, aby byly všechny v registrech v době, kdy se používají.

Standardní přístup k tomuto problému je redukovat jej na problém vybarvování grafu [8] . Kompilátor sestaví interferenční graf , kde vrcholy odpovídají proměnným a hrana spojuje dva z nich, pokud jsou potřeba současně. Pokud je tento graf k -chromatický, pak lze proměnné uložit do k registrů.

Digitální vodoznaky

Technologie digitálních vodoznaků ( angl. digital watermarking ) umožňuje přenášet spolu s daty i nějakou skrytou zprávu (ať už jde o mediální soubory , spustitelné soubory a další) („ vodoznak “, vodoznak ). Taková skrytá zpráva může být použita v ochraně autorských práv k identifikaci vlastníka dat.

To je důležité například pro zjištění zdroje jejich nelegální distribuce. Nebo pro potvrzení práv k datům, například - softwarové systémy na čipu ( system-on-chip ).

Zpráva může být také zakódována způsobem alokace registrů. Jednu takovou techniku navrhli Qu a Potkonjak [37] (proto se jí někdy říká QP algoritmus).

Skládá se z následujícího: nechť je graf nekompatibility (graf rušení) rozložení registrů procesoru, který byl zmíněn výše. V programu je použito jeho zbarvení - navíc je použito tak, že je přípustné měnit obsah grafu s mírným zvýšením jeho chromatického čísla . Ukazuje se, že je možné zakódovat zprávu v softwarovém produktu pomocí vybarvování grafů , tedy distribuce registrů. $G$ $G$

Tuto zprávu můžete extrahovat porovnáním distribuce registrů s původním zbarvením; [38] existují také způsoby, jak ověřit, zda byla zpráva v programu zakódována bez použití té původní.

Následně různí autoři rozvíjeli a zdokonalovali myšlenky Qu a Potkonjaka [39] . [38] [40]

Další použití

Problém zbarvení grafu se objevil v mnoha dalších aplikacích, včetně porovnávání vzorů .

Řešení sudoku si lze představit jako dokončení 9barevného vybarvení daného grafu o 81 vrcholech.

Poznámky

↑ 1 2 3 ( Molloy & Reed 2002 , Základní definice )
↑ ( Donets & Shor 1982 , Historický odkaz )
↑ ( Kubale 2004 , Historie vybarvování grafů )
↑ ( van Lint & Wilson 2001 , kap. 33)
↑ ( Jensen & Toft 1995 , s. 2)
↑ CE Shannon, "Kapacita hlučného kanálu s nulovou chybou," IEEE Trans. Teorie informace , str. 8-19, 1956.
↑ ( 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 > Archivováno 29. července 2019 na Wayback Machine
↑ ( Birkhoff & Lewis 1946 )
↑ 1 2 3 4 ( Tutte 1984 , Chromatický polynom )
↑ 1 2 3 ( Diestel 2005 , Barvení vrcholů )
↑ ( Brooks & Tutte 1941 )
↑ 1 2 ( Diestel 2005 , Barvení hran )
↑ ( 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 ), viz také ( Cormen, Leiserson & Rivest 1990 , oddíl 30.5)
↑ 1 2 ( Linial 1992 )
↑ ( Goldberg, Plotkin & Shannon 1988 )
↑ ( Schneider 2008 )
↑ ( Panconesi & Rizzi 2001 )
↑ ( Leith & Clifford 2006 )
↑ ( Duffy, O'Connell & Sapozhnikov 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 )

Literatura

Donets, G. A. & Shor, N. Z. (1982), An Algebraic Approach to the Plane Graph Coloring Problem , Naukova Dumka, str. 5-7
Zykov, A. A. (1949), O některých vlastnostech lineárních komplexů , Mat. So. 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 vol . 54 (2)): 168–204 , DOI 10.1016/j.jalgor.2004.06.008
Birkhoff, G. D. & Lewis, D. C. (1946), Chromatic Polynomials , Trans. amer. Matematika. soc. T. 60 : 355-451 , >
Brélaz, D. (1979), Nové metody obarvování vrcholů grafu , Communications of the ACM , sv. 22 (4): 251–256 , DOI 10.1145/359094.359101
Brooks, R. L. & Tutte, WT (1941), On coloring the nodes of a network , Proceedings of the Cambridge Philosophical Society, svazek 37 (2): 194–197 , DOI 10.1017/S030500410002168X
N. G. de Bruijn, P. Erdős . Barevný problém pro nekonečné grafy a problém v teorii relací (anglicky) // Nederl. Akad. Wetensch. Proč. Ser. A. - 1951. - T. 54 . - S. 371-373 . (= Indag. Math. 13 )
Byskov, JM (2004), Výčet maximálních nezávislých množin s aplikacemi pro barvení grafů , Operations Research Letters vol. 32 (6): 547–556 , DOI 10.1016/j.orl.2004.03.002
Cormen, T. H.; Leiserson, CE & Rivest, RL (1990), Introduction to Algorithms (1. ed.), The MIT Press
Collberg, křesťan; Thomborson, Clark & Townsend, Gregg M. (2004), Dynamický grafový software Watermarking , < ftp://ftp.cs.arizona.edu/reports/2004/TR04-08.pdf >
Chaitin , GJ (1982), Přidělování registrů a přelévání pomocí vybarvování grafů , Proc. 1982 SIGPLAN Symposium on Compiler Construction , str. 98–105, ISBN 0-89791-074-5 , DOI 10.1145/800230.806984
Cole, R. & Vishkin, U. (1986), Deterministické házení mincí s aplikacemi pro optimální hodnocení paralelních seznamů , Information and Control , svazek 70 (1): 32–53 , DOI 10.1016/S0019-9958(86)80023-7
Dailey, D.P. (1980), Jedinečnost obarvitelnosti a vybarvitelnosti planárních 4-pravidelných grafů jsou NP-kompletní , Discrete Mathematics sv . 30 (3): 289–293 , DOI 10.1016/0012-365X(80-802)
Diestel, R. (2005), Graph theory , < http://www.math.ubc.ca/~solymosi/2007/443/GraphTheoryIII.pdf > Archivováno 25. listopadu 2014 na Wayback Machine
Duffy, K.; O'Connell, N. & Sapozhnikov, A. (2008), Analýza složitosti algoritmu zbarvení decentralizovaného grafu , Information Processing Letters vol . 107: 60–63, doi : 10.1016/j.ipl.2008.01.002 , < http: //www.hamilton.ie/ken_duffy/Downloads/cfl.pdf >
Fawcett, BW (1978), O nekonečných plných vybarveních grafů, Can. J Math. T. XXX: 455–457
Fomin, FV; Gaspers, S. & Saurabh, S. (2007), Improved Exact Algorithms for Counting 3- and 4-Colorings , Proc. 13. výroční mezinárodní konference, COCOON 2007 , sv. 4598, Poznámky k přednáškám z informatiky , Springer, s. 65-74, ISBN 978-3-540-73544-1
Garey, MR & Johnson, DS (1979), Počítače a nepoddajnost: Průvodce teorií NP-úplnosti , W. H. Freeman, ISBN 0-7167-1045-5
Goldberg, LA & Jerrum, M. (červenec 2008), Inapproximability of the Tutte polynomial , 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 symetry-breaking in spase graphs , SIAM Journal on Discrete Mathematics vol . 1 (4): 434–446 , DOI 10.1137/0401044
Guruswami, V. & Khanna, S. (2000), O tvrdosti 4 zbarvení a 3 obarvitelného grafu , Sborník z 15. výroční konference IEEE o výpočetní složitosti , str. 188–197, ISBN 0-7695-0674-7 , DOI 10.1109/CCC.2000.856749
Jaeger, F.; Vertigan, DL & Welsh, DJA (1990), On the computational complexity of the Jones and Tutte polynomials , Mathematical Proceedings of the Cambridge Philosophical Society vol. 108: 35–53 , DOI 10.1017/S0305004136006
Jensen, Tommy R. & Toft, Bjarne (1995), Problémy s vybarvováním grafů , John Wiley & Sons, ISBN 0-471-02865-7
Khot, S. (2001), Vylepšené výsledky nepřiblížení pro MaxClique, chromatické číslo a přibližné zbarvení grafu , Proc. 42. výroční sympozium o základech informatiky , str. 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), Slabá zbarvení grafů: distribuované algoritmy a aplikace , Sborník příspěvků z 21. sympozia o paralelismu v algoritmech a architekturách , str. 138–144, ISBN 978-1-60558-606-9
Lawler, EL (1976), Poznámka ke složitosti problému chromatických čísel , Information Processing Letters vol . 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), Lokalita v algoritmech distribuovaných grafů , SIAM Journal on Computing vol. 21 (1): 193–201 , DOI 10.1137/0221015
van Lint, JH & Wilson, R. M. (2001), A Course in Combinatorics (2. ed.), Cambridge University Press, ISBN 0-521-80340-3
Molloy, Michael & Reed, Bruce (2002), Barvení grafů a pravděpodobnostní metoda , Springer, ISBN 3-540-42139-4 , ISSN 0937-5511
Marx, Dániel (2004), Problémy s barvením grafů a jejich aplikace v plánování, Periodica Polytechnica, Electrical Engineering , sv. 48, str. 11–16, CiteSeerX:10.1.1.95.4268
Mycielski, J. (1955), Sur le coloriage des graphes , Colloq. Matematika. 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 , str. 274-293 , DOI 10.1007/b96249

Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), Theorem 3.13 , Sparsity: Graphs, Structures, and Algorithms , sv. 28, Algorithms and Combinatorics, Heidelberg: Springer, str. 28. 42, ISBN 978-3-642-27874-7 , DOI 10.1007/978-3-642-27875-4 .
Panconesi, Alessandro & Rizzi, Romeo (2001), Některé jednoduché distribuované algoritmy pro řídké sítě , Distributed Computing (Berlín, New York: Springer-Verlag ). — V. 14 (2): 97–100, ISSN 0178-2770 , DOI 10.1007/PL00008932
Panconesi, A. & Srinivasan, A. (1996), O složitosti dekompozice distribuované sítě, Journal of Algorithms , sv. dvacet
Qu, Gang & Potkonjak, Miodrag (1998), Analýza technik vodoznaku pro problém barvení grafů , ICCAD , str. 190-193 , DOI 10.1145/288548.288607
Schneider, J. (2010), Nová technika pro narušení distribuované symetrie , Sborník příspěvků ze sympozia o principech distribuovaného počítání , < http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf > Archivováno 30. července 2013 Wayback Machine
Schneider, J. (2008), Log-star distribuovaný maximální nezávislý množinový algoritmus pro grafy ohraničené růstem , Proceedings of the Symposium on Principles of Distributed Computing , < http://www.dcg.ethz.ch/publications/podc08SW. pdf > Archivováno 30. července 2013 na Wayback Machine
Sekine, K.; Imai, H. & Tani, S. (1995), Computing the Tutte polynomial of a graph of a medium size , Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995) , sv. 1004, Poznámky k přednáškám z informatiky , Springer, s. 224–233, ISBN 3-540-60573-8 , DOI 10.1007/BFb0015427
Tutte, WT (1984), Teorie grafů, Encyklopedie matematiky a aplikací (Cambridge University Press) . - svazek 21, ISBN 0-521-30241-2
Welsh, DJA & Powell, MB (1967), Horní hranice pro chromatické číslo grafu a jeho aplikace na problémy s rozvrhováním , The Computer Journal vol . 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), Rozpoznávání v softwarovém vodoznaku , MCPS '06: Sborník ze 4. mezinárodního semináře ACM o ochraně a zabezpečení obsahu , ACM, str. 29–36, ISBN 1-59593-499-5 , DOI 10.1145/1178766.1178776