Barvení grafu - Graph coloring

v teorie grafů, zbarvení grafu je zvláštní případ označení grafu; jedná se o přiřazení štítků tradičně nazývaných „barvy“ k prvkům a graf podléhá určitým omezením. V nejjednodušší podobě jde o způsob vybarvení vrcholy grafu tak, že žádné dva sousední vrcholy nejsou stejné barvy; tomu se říká a vrchol zbarvení. Podobně an zbarvení hran přiřadí barvu každému okraji tak, aby žádné dva sousední okraje neměly stejnou barvu, a zbarvení obličeje a rovinný graf přiřadí barvu každé ploše nebo oblasti tak, aby žádné dvě tváře, které sdílejí hranici, neměly stejnou barvu.
Barvení vrcholů se obvykle používá k zavedení problémů s barvením grafů, protože jiné problémy s barvením lze transformovat na instanci zbarvení vrcholu. Například zbarvení hran grafu je pouze jeho vrcholovým vybarvením hranový graf a zbarvení plochy rovinného grafu je pouze jeho vrcholovým vybarvením dvojí. Problémy s barvením nevertexů jsou však často uváděny a studovány tak, jak jsou. To je částečně pedagogický, a částečně proto, že některé problémy je nejlépe studovat v jejich nevertexové formě, jako v případě zbarvení hran.
Konvence používání barev pochází z vybarvení zemí a mapa, kde je každá tvář doslova barevná. To bylo zobecněno na zbarvení tváří grafu vložený v letadle. Rovinnou dualitou se zbarvilo vrcholy a v této podobě se zobecňuje na všechny grafy. V matematických a počítačových reprezentacích je typické použít prvních několik kladných nebo nezáporných celých čísel jako „barvy“. Obecně lze použít jakýkoli konečná množina jako „barevná sada“. Povaha problému s barvením závisí na počtu barev, ale ne na tom, jaké jsou.
Barvení grafů se těší mnoha praktickým aplikacím i teoretickým výzvám. Kromě klasických typů problémů lze na grafu nebo způsobu přiřazení barvy nebo dokonce na barvu samotnou nastavit různá omezení. Dosáhla dokonce popularity u široké veřejnosti v podobě populární skládačky čísel Sudoku. Barvení grafů je stále velmi aktivní oblastí výzkumu.
Poznámka: Mnoho pojmů použitých v tomto článku je definováno v Glosář teorie grafů.
Dějiny
První výsledky zabarvení grafů se zabývají téměř výlučně rovinné grafy ve formě zbarvení mapyPři pokusu o vybarvení mapy krajů Anglie Francis Guthrie postuloval čtyřbarevná domněnka s tím, že k vybarvení mapy stačily čtyři barvy, takže žádné oblasti sdílející společnou hranici nedostaly stejnou barvu. Guthrieho bratr předal otázku svému učiteli matematiky Augustus de Morgan na University College, který se o tom zmínil v dopise William Hamilton v roce 1852. Arthur Cayley vznesl problém na schůzi London Mathematical Society v roce 1879. Ve stejném roce Alfred Kempe zveřejnil dokument, který tvrdil, že stanoví výsledek, a po desetiletí byl problém se čtyřmi barvami považován za vyřešený. Za svůj úspěch byl Kempe zvolen za člena královská společnost a později prezident London Mathematical Society.[1]
V roce 1890 Heawood poukázal na to, že Kempeho argument byl špatný. V tomto článku však prokázal pět barevná věta s tím, že každá rovinná mapa může být vybarvena maximálně Pět barvy, s využitím myšlenek Kempe. V následujícím století bylo vyvinuto obrovské množství práce a teorií ke snížení počtu barev na čtyři, dokud teorém o čtyřech barvách nebyl v roce 1976 konečně prokázán Kenneth Appel a Wolfgang Haken. Důkaz se vrátil k myšlenkám Heawooda a Kempeho a do značné míry nezohlednil intervenující vývoj.[2] Důkaz čtyřbarevné věty je také pozoruhodný tím, že je prvním významným důkazem podporovaným počítačem.
V roce 1912 George David Birkhoff představil chromatický polynom studovat problémy s barvením, které byly zobecněny na Tutteův polynom podle Tutte, důležité struktury v algebraická teorie grafů. Kempe již upozornil na obecný, nerovinný případ v roce 1879,[3] a na počátku 20. století následovalo mnoho výsledků zevšeobecňování zbarvení planárního grafu na povrchy vyššího řádu.
V roce 1960 Claude Berge formuloval další domněnku o zbarvení grafu, silná dokonalá domněnka grafu, původně motivováno an informační teoretik koncept zvaný kapacita nulové chyby grafu zavedeného Shannon. Domněnka zůstala nevyřešena po dobu 40 let, dokud nebyla ustanovena jako slavná silná dokonalá věta o grafu podle Chudnovský, Robertson, Seymour, a Thomas v roce 2002.
Barvení grafů bylo studováno jako algoritmický problém od začátku 70. let: problém chromatického čísla je jedním z Karpových 21 NP-úplných problémů z roku 1972 a přibližně ve stejnou dobu byly vyvinuty různé algoritmy exponenciálního času založené na zpětném sledování a opakování deleční-kontrakce Zykov (1949). Jednou z hlavních aplikací barvení grafů, přidělení registru v kompilátorech, byl představen v roce 1981.
Definice a terminologie

Vrchol zbarvení
Při použití bez jakékoli kvalifikace, a zbarvení grafu je téměř vždy a správné zbarvení vrcholů, jmenovitě označení vrcholů grafu takovými barvami, že žádné dva vrcholy nesdílejí stejné okraj mít stejnou barvu. Protože vrchol s a smyčka (tj. spojení přímo zpět k sobě samému) by nikdy nemohlo být správně vybarveno, rozumí se, že grafy v tomto kontextu jsou bezbrankové.
Terminologie používání barvy pro vrcholové štítky se vrací k zbarvení mapy. Štítky jako Červené a modrý se používají pouze v případě, že je počet barev malý a obvykle se rozumí, že popisky jsou kresleny z celých čísel {1, 2, 3, ...}.
Barvení nanejvýš k barvy se nazývá (správné) k-zbarveníNejmenší počet barev potřebných k vybarvení grafu G se nazývá jeho chromatické číslo, a často se označuje χ (G). Někdy γ (G) se používá, protože χ (G) se také používá k označení Eulerova charakteristika grafu, kterému lze přiřadit (vlastní) k-barvení je k-barevné, a to je k-chromatický pokud je jeho chromatické číslo přesně kPodmnožina vrcholů přiřazených stejné barvě se nazývá a barevná třída, každá taková třída tvoří nezávislá sada. Tak, a k-barvení je stejné jako oddíl vrcholu nastavený do k nezávislé množiny a podmínky k-partite a k-barevný mají stejný význam.
Chromatický polynom

The chromatický polynom spočítá počet způsobů, jak lze graf obarvit pomocí maximálně daného počtu barev. Například pomocí tří barev lze graf v sousedním obrázku obarvit 12 způsoby. S pouhými dvěma barvami jej nelze vůbec obarvit. Se čtyřmi barvami lze barvit 24 + 4 +12 = 72 způsoby: při použití všech čtyř barev jsou 4! = 24 platných barviv (každý přiřazení čtyř barev k žádný 4-vrcholný graf je správné zbarvení); a pro každou volbu ze tří ze čtyř barev existuje 12 platných 3 barev. Takže pro graf v příkladu by tabulka počtu platných barviv začala takto:
Dostupné barvy | 1 | 2 | 3 | 4 | … |
Počet barviv | 0 | 0 | 12 | 72 | … |
Chromatický polynom je funkce P(G, t), který počítá počet t-barvyG. Jak název napovídá, pro daný G funkce je skutečně a polynomiální vt. U ukázkového grafu P(G, t) = t(t − 1)2(t - 2), a opravduP(G, 4) = 72.
Chromatický polynom obsahuje přinejmenším tolik informací o barevnosti G stejně jako chromatické číslo. Ve skutečnosti je χ nejmenší kladné celé číslo, které není kořenem chromatického polynomu
Trojúhelník K.3 | |
Kompletní graf K.n | |
Strom s n vrcholy | |
Cyklus Cn | |
Petersenův graf |
Barvení hran
An zbarvení hran grafu je správné vybarvení hrany, což znamená přiřazení barev hranám tak, aby žádný vrchol nenarazil na dva okraje stejné barvy. Barvení hran s k barvy se nazývá a k-edge-colored a je ekvivalentní problému rozdělení hrany do k párování. Nejmenší počet barev potřebných pro vybarvení hran grafu G je chromatický indexnebo hranové chromatické číslo, χ′(G). A Tait zbarvení je tříbarevné zbarvení a kubický graf. The čtyřbarevná věta je ekvivalentní tvrzení, že každý rovinný kubický bez můstku graf připouští zbarvení Tait.
Celkové zbarvení
Celkové zbarvení je typ zbarvení na vrcholech a okraje grafu. Pokud se použije bez jakékoli kvalifikace, předpokládá se, že celkové zbarvení je správné v tom smyslu, že žádné sousední vrcholy, žádné sousední hrany a žádný okraj a jeho koncové vrcholy nemají stejnou barvu. Celkový chromatický počet χ ″ (G) grafu G je nejméně barev potřebných k celkovému zbarvení G.
Neoznačené zbarvení
An neoznačené zbarvení grafu je obíhat barvení působením automorfická skupina grafu. Pokud interpretujeme zbarvení grafu na vrcholy jako vektor v , akce automorfismu je a permutace koeficientů zbarvení. Existují analogie chromatické polynomy které počítají počet neoznačených barvení grafu z dané konečné sady barev.
Vlastnosti
Horní hranice chromatického čísla
Přiřazení odlišných barev různým vrcholům vždy přináší správné zbarvení, takže
Jediné grafy, které mohou být jednobarevné, jsou bez okrajů grafy. A kompletní graf z n vrcholy vyžadují barvy. V optimálním zbarvení musí být alespoň jeden z grafů m hrany mezi každou dvojicí barevných tříd, takže
Li G obsahuje a klika velikosti k, tedy alespoň k k vybarvení této kliky jsou potřeba barvy; jinými slovy, chromatické číslo je alespoň číslo kliky:
Pro perfektní grafy tato vazba je pevná. Hledání klik je známé jako klika problém.
Dvoubarevné grafy jsou přesně ty bipartitní grafy, počítaje v to stromy Čtyřbarevnou větou může být každý rovinný graf čtyřbarevný.
A chamtivé zbarvení ukazuje, že každý graf může být obarven jednou další barvou, než je maximální vrchol stupeň,
Kompletní grafy mají a , a liché cykly mít a , takže pro tyto grafy je tato vazba nejlepší možná. Ve všech ostatních případech lze vázanou mírně vylepšit; Brooksova věta[4] tvrdí, že
- Brooksova věta: pro propojený, jednoduchý graf G, pokud G je kompletní graf nebo lichý cyklus.
Dolní hranice chromatického čísla
V průběhu let bylo objeveno několik dolních hranic pro chromatické hranice:
Hoffman je vázán: Nechat být skutečná symetrická matice taková kdykoli není hrana . Definovat , kde jsou největší a nejmenší vlastní čísla . Definovat , s jak je uvedeno výše. Pak:
- .
Vektorové chromatické číslo: Nechat být pozitivní semitečnou maticí takovou kdykoli je hrana v . Definovat být nejméně k, pro které taková matice existuje. Pak
Lovászovo číslo: Lovászovo číslo doplňkového grafu je také spodní hranicí chromatického čísla:
Frakční chromatické číslo: Frakční chromatické číslo grafu je také spodní hranicí chromatického čísla:
Tyto hranice jsou seřazeny takto:
Grafy s vysokým chromatickým číslem
Grafy s velkými klikami mají vysoké chromatické číslo, ale opak není pravdou. The Grötzschův graf je příklad 4-chromatického grafu bez trojúhelníku a příklad lze zobecnit na Mycielskians.
- Mycielskiho věta (Alexander Zykov 1949, Jan Mycielski 1955 ): Existují grafy bez trojúhelníků s libovolně vysokým chromatickým číslem.
Z Brooksovy věty musí mít grafy s vysokým chromatickým číslem vysoký maximální stupeň. Další místní vlastností, která vede k vysokému chromatickému číslu, je přítomnost velké kliky. Barevnost však není zcela lokálním jevem: graf s vysokým obvod vypadá místně jako strom, protože všechny cykly jsou dlouhé, ale jeho chromatické číslo nemusí být 2:
- Teorém (Erdős): Existují grafy libovolně vysokého obvodu a chromatického čísla.[5]
Hranice na chromatickém indexu
Barvení hran z G je vrcholné zbarvení jeho hranový graf a naopak. Tím pádem,
Mezi barevností hran a maximálním stupněm grafu existuje silný vztah . Protože všechny hrany dopadající na stejný vrchol potřebují svou vlastní barvu, máme
Navíc,
- Kőnigova věta: -li G je bipartitní.
Obecně je vztah ještě silnější, než jaký dává Brooksova věta pro obarvení vrcholů:
- Vizingova věta: Graf maximálního stupně má hranové chromatické číslo nebo .
Další vlastnosti
Graf má a k-barvení, pokud a pouze pokud má acyklická orientace pro které nejdelší cesta má délku maximálně k; to je Věta Gallai – Hasse – Roy – Vitaver (Nešetřil & Ossona de Mendez 2012 ).
U rovinných grafů je zbarvení vrcholů v zásadě duální nikde nula teče.
O nekonečných grafech je toho známo mnohem méně. Níže jsou uvedeny dva z mála výsledků o zbarvení nekonečných grafů:
- Pokud jsou všechny konečné podgrafy nekonečný graf G jsou k-barevné, pak také G, za předpokladu, že axiom volby. To je de Bruijn – Erdősova věta z de Bruijn a Erdős (1951).
- Pokud graf připouští plný n-barvení pro každého n ≥ n0, připouští nekonečné plné zbarvení (Fawcett 1978 ).
Otevřené problémy
Jak je uvedeno výše, Domněnka Reeda z roku 1998 je, že hodnota je v podstatě blíže spodní hranici,
The chromatické číslo roviny, kde dva body sousedí, pokud mají jednotkovou vzdálenost, není znám, i když je to jeden z 5, 6 nebo 7. Ostatní otevřené problémy týkající se chromatického počtu grafů patří Hadwigerův dohad s uvedením, že každý graf s chromatickým číslem k má kompletní graf na k vrcholy jako a Méně důležitý, Erdős – Faber – Lovász dohad ohraničující chromatický počet spojů úplných grafů, které mají pro každou dvojici nanejvýš jeden společný vrchol, a Albertsonova domněnka že mezi k-chromatické grafy, úplné grafy jsou ty s nejmenšími číslo křížení.
Když Birkhoff a Lewis představili chromatický polynom při svém útoku na čtyřbarevnou větu, domnívali se, že pro rovinné grafy G, polynom nemá v regionu žádné nuly . I když je známo, že takový chromatický polynom nemá v této oblasti nuly a to , jejich domněnka je stále nevyřešená. Zůstává také nevyřešeným problémem charakterizovat grafy, které mají stejný chromatický polynom, a určit, které polynomy jsou chromatické.
Algoritmy
Barvení grafu | |
---|---|
![]() | |
Rozhodnutí | |
název | Zbarvení grafu, zbarvení vrcholů, k-zbarvení |
Vstup | Graf G s n vrcholy. Celé číslo k |
Výstup | Ano G připustit správné zbarvení vrcholů pomocí k barvy? |
Provozní doba | O (2 nn)[6] |
Složitost | NP-kompletní |
Snížení z | 3 - Splnitelnost |
Garey – Johnson | GT4 |
Optimalizace | |
název | Chromatické číslo |
Vstup | Graf G s n vrcholy. |
Výstup | χ (G) |
Složitost | NP-tvrdé |
Přibližnost | Ó(n (log n)−3(log log n)2) |
Nepřibližnost | Ó(n1 − ε) pokud P = NP |
Počítání problém | |
název | Chromatický polynom |
Vstup | Graf G s n vrcholy. Celé číslo k |
Výstup | Číslo P (G,k) řádného k-barvy G |
Provozní doba | O (2 nn) |
Složitost | # P-kompletní |
Přibližnost | FPRAS pro omezené případy |
Nepřibližnost | Ne PTAS pokud P = NP |
Polynomiální čas
Určení, zda lze graf obarvit dvěma barvami, je ekvivalentní k určení, zda graf je nebo není bipartitní, a tedy vypočítatelný v lineární čas použitím vyhledávání na šířku nebo hloubkové vyhledávání. Obecněji platí, že chromatické číslo a odpovídající zbarvení perfektní grafy lze vypočítat v polynomiální čas použitím semidefinitní programování. Uzavřené vzorce pro chromatické polynomy jsou známy pro mnoho tříd grafů, jako jsou lesy, chordální grafy, cykly, kola a žebříky, takže je lze vyhodnotit v polynomiálním čase.
Pokud je graf rovinný a má malou šířku větve (nebo je neplanární, ale se známým rozkladem větve), lze jej vyřešit v polynomiálním čase pomocí dynamického programování. Obecně je požadovaný čas polynomický ve velikosti grafu, ale exponenciální ve šířce větve.
Přesné algoritmy
Hledání hrubou silou pro k- vybarvení bere v úvahu každý z úkoly k barvy do n vrcholy a kontroluje, zda je to legální. Pro výpočet chromatického čísla a chromatického polynomu se tento postup používá pro všechny , nepraktické pro všechny kromě nejmenších vstupních grafů.
Použitím dynamické programování a vázaný na počet maximální nezávislé množiny, k-barevnost lze rozhodnout v čase a prostoru .[7] Pomocí principu začlenění – vyloučení a Yates Algoritmus pro rychlou transformaci zeta,k-barevnost lze rozhodnout včas [6] pro všechny k. Rychlejší algoritmy jsou známé pro 3- a 4barevnost, o které lze rozhodnout včas [8] a ,[9] resp.
Kontrakce
The kontrakce grafu G je graf získaný identifikací vrcholů u a protia odstranění hran mezi nimi. Zbývající hrany původně dopadly na u nebo proti nyní naráží na svou identifikaci. Tato operace hraje hlavní roli v analýze zbarvení grafu.
Chromatické číslo splňuje relace opakování:
kvůli Zykov (1949),kde u a proti jsou nesousedící vrcholy a je graf s hranou uv přidané. Na vyhodnocení tohoto opakování je založeno několik algoritmů a výsledný výpočetní strom se někdy nazývá strom Zykov. Doba provozu je založena na heuristice pro výběr vrcholů u a proti.
Chromatický polynom splňuje následující relaci opakování
kde u a proti jsou sousední vrcholy a je graf s hranou uv odstraněn. představuje počet možných správných zabarvení grafu, kde vrcholy mohou mít stejné nebo různé barvy. Správné zabarvení pak vychází ze dvou různých grafů. Vysvětlit, pokud vrcholy u a proti mít různé barvy, pak bychom také mohli zvážit graf, kde u a proti sousedí. Li u a proti mít stejné barvy, můžeme také uvažovat o grafu, kde u a proti jsou smluvně. Tutte Zvědavost, které další vlastnosti grafu uspokojily toto opakování, ho vedla k objevu dvojrozměrného zobecnění chromatického polynomu, Tutteův polynom.
Tyto výrazy vedou k rekurzivní proceduře zvané algoritmus delece – kontrakce, který tvoří základ mnoha algoritmů pro barvení grafů. Doba provozu vyhovuje stejnému relaci opakování jako Fibonacciho čísla, takže v nejhorším případě algoritmus běží v čase v rámci polynomiálního faktoru pro n vrcholy a m hrany.[10] Analýza může být vylepšena v rámci polynomiálního faktoru čísla z klenout se nad stromy vstupního grafu.[11]V praxi, větev a svázaný strategie a izomorfismus grafu odmítnutí se používá, aby se zabránilo některým rekurzivním hovorům. Délka chodu závisí na heuristice použité k výběru dvojice vrcholů.
Chamtivé zbarvení

The chamtivý algoritmus uvažuje vrcholy v určitém pořadí ,…, a přiřadí nejmenší dostupná barva, kterou nepoužívá Sousedé mezi ,…,, v případě potřeby přidejte novou barvu. Kvalita výsledného zbarvení závisí na zvoleném pořadí. Existuje uspořádání, které vede k chamtivému zbarvení s optimálním počtem barvy. Na druhé straně může být chamtivé zbarvení libovolně špatné; například korunový graf na n vrcholy mohou být dvoubarevné, ale má uspořádání, které vede k chamtivému zbarvení barvy.
Pro chordální grafy, a pro speciální případy akordových grafů, jako je intervalové grafy a indiferenční grafy, chamtivý algoritmus zbarvení lze použít k nalezení optimálního zabarvení v polynomiálním čase výběrem pořadí vrcholů, které bude opakem perfektní objednávka eliminace pro graf. The dokonale uspořádatelné grafy zobecnit tuto vlastnost, ale je těžké najít dokonalé uspořádání těchto grafů.
Pokud jsou vrcholy seřazeny podle jejich stupňů, výsledné chamtivé zbarvení se používá maximálně barev, maximálně o jednu více, než je maximální stupeň grafu. Tato heuristika se někdy nazývá velšský-Powellův algoritmus.[12] Další heuristika kvůli Brélaz ustavuje řazení dynamicky, zatímco algoritmus postupuje, volí další vrchol sousedící s největším počtem různých barev.[13] Mnoho dalších heuristik barvení grafů je podobně založeno na chamtivém zbarvení pro konkrétní statickou nebo dynamickou strategii uspořádání vrcholů, tyto algoritmy se někdy nazývají postupné zbarvení algoritmy.
Maximální (nejhorší) počet barev, které lze získat chamtivým algoritmem pomocí pořadí vrcholů zvoleného pro maximalizaci tohoto počtu, se nazývá Zelené číslo grafu.
Paralelní a distribuované algoritmy
V oblasti distribuované algoritmy, zbarvení grafu úzce souvisí s problémem lámání symetrie. Současné nejmodernější randomizované algoritmy jsou rychlejší pro dostatečně velký maximální stupeň Δ než deterministické algoritmy. Nejrychlejší randomizované algoritmy využívají technika více pokusů Schneider a kol.[14]
V symetrický graf, a deterministický distribuovaný algoritmus nemůže najít správné zbarvení vrcholů. K narušení symetrie jsou potřebné některé pomocné informace. Standardní předpoklad je, že zpočátku má každý uzel a unikátní identifikátor, například z množiny {1, 2, ..., n}. Jinak řečeno, předpokládáme, že jsme dostali n-zbarvení. Úkolem je snížit počet barev od n např. Δ + 1. Čím více barev je použito, např. O (Δ) namísto Δ + 1 je zapotřebí méně komunikačních kol.[14]
Přímočará distribuovaná verze chamtivého algoritmu pro barvení (Δ + 1) vyžaduje Θ (n) komunikační kola v nejhorším případě - může být nutné šířit informace z jedné strany sítě na druhou stranu.
Nejjednodušší zajímavý případ je n-cyklus. Richard Cole a Uzi Vishkin[15] ukázat, že existuje distribuovaný algoritmus, který snižuje počet barev od n na Ó(logn) v jednom kroku synchronní komunikace. Opakováním stejného postupu je možné získat 3barvení an n-zapojit Ó(log* n) komunikační kroky (za předpokladu, že máme jedinečné identifikátory uzlů).
Funkce log*, iterovaný logaritmus, je extrémně pomalu rostoucí funkce, „téměř konstantní“. Výsledek Coleho a Vishkina proto vznesl otázku, zda existuje konstantní čas distribuovaný algoritmus pro 3-barvení a n-cyklus. Linial (1992) ukázal, že to není možné: jakýkoli deterministický distribuovaný algoritmus vyžaduje Ω (log* n) komunikační kroky ke snížení n-barvení na 3-barvení v n-cyklus.
Technika od Colea a Vishkina může být použita také v libovolných grafech s omezeným stupněm; doba provozu je poly (Δ) + Ó(log* n).[16] Technika byla rozšířena na jednotkové diskové grafy Schneider a kol.[17] Nejrychlejší deterministické algoritmy pro barvení (Δ + 1) pro malé Δ jsou způsobeny Leonidem Barenboimem, Michaelem Elkinem a Fabianem Kuhnem.[18] Algoritmus Barenboima et al. běží v čase Ó(Δ) +log* (n) / 2, což je optimální z hlediska n protože konstantní faktor 1/2 nelze zlepšit kvůli spodní hranici Liniala. Panconesi a Srinivasan (1996) pomocí síťových rozkladů vypočítat Δ + 1 zbarvení v čase .
Problém zbarvení hran byl také studován v distribuovaném modelu. Panconesi & Rizzi (2001) dosáhnout (2Δ - 1) vybarvení v Ó(Δ +log* n) čas v tomto modelu. Dolní mez pro distribuované zbarvení vrcholů kvůli Linial (1992) platí také pro problém distribuovaného zbarvení hran.
Decentralizované algoritmy
Decentralizované algoritmy jsou takové, kde není povoleno předávání zpráv (na rozdíl od distribuovaných algoritmů, kde dochází k předávání místních zpráv), a existují účinné decentralizované algoritmy, které zabarvují graf, pokud existuje správné zbarvení. Předpokládají, že vrchol je schopen vycítit, zda některý z jeho sousedů používá stejnou barvu jako vrchol, tj. Zda existuje místní konflikt. Toto je mírný předpoklad v mnoha aplikacích, např. při přidělování bezdrátových kanálů je obvykle rozumné předpokládat, že stanice bude schopna detekovat, zda jiné rušivé vysílače používají stejný kanál (např. měřením SINR). Tato snímací informace je dostatečná, aby umožnila algoritmům založeným na automatech učení najít správné zbarvení grafu s pravděpodobností.[19]
Výpočetní složitost
Vybarvení grafu je výpočetně náročné. to je NP-kompletní rozhodnout, zda daný graf připouští a k-barvení pro daný k kromě případů k 0,1 {0,1,2}. Zejména je NP těžké vypočítat chromatické číslo.[20]Problém se 3 barvami zůstává NP-kompletní i na 4-pravidelných rovinné grafy.[21] Nicméně pro každého k > 3, a k-barvení rovinného grafu existuje čtyřbarevná věta a je možné najít takové zbarvení v polynomiálním čase.
Nejznámější aproximační algoritmus vypočítá zbarvení velikosti maximálně v rámci faktoru O (n(log logn)2(log n)−3) chromatického čísla.[22] Pro všechny ε > 0, přibližné barevné číslo uvnitř n1−ε je NP-tvrdé.[23]
Je také NP těžké obarvit 3barevný graf se 4 barvami[24] a a k-barevný graf s k(log k ) / 25 barvy pro dostatečně velkou konstantu k.[25]
Výpočet koeficientů chromatického polynomu je # P-tvrdé. Ve skutečnosti dokonce výpočet hodnoty je v každém případě # P-hard racionální bod k až na k = 1 a k = 2.[26] Tady není žádný FPRAS pro vyhodnocení chromatického polynomu v jakémkoli racionálním bodě k ≥ 1,5 kromě k = 2, pokud NP = RP.[27]
Pro vybarvení hran poskytuje důkaz výsledku Vizinga algoritmus, který používá maximálně Δ + 1 barev. Rozhodování mezi dvěma kandidátskými hodnotami pro hranové chromatické číslo je však NP-úplné.[28] Pokud jde o aproximační algoritmy, Vizingův algoritmus ukazuje, že okrajové chromatické číslo lze přiblížit na 4/3 a výsledek tvrdosti ukazuje, že žádný (4/3 -ε ) -algoritmus existuje pro všechny ε> 0 ledaže P = NP. Patří mezi nejstarší výsledky v literatuře o aproximačních algoritmech, i když ani jeden z nich tuto představu výslovně nepoužívá.[29]
Aplikace
Plánování
Vertexové modely zbarvení na řadu problémy s plánováním.[30] V nejčistší formě je třeba daným souborům úloh přiřadit časové úseky, každá úloha vyžaduje jeden takový úlovek. Úlohy lze naplánovat v libovolném pořadí, ale mohou být i dvojice úloh konflikt v tom smyslu, že jim nemusí být přiřazen stejný časový úsek, například protože oba spoléhají na sdílený prostředek. Odpovídající graf obsahuje vrchol pro každou úlohu a okraj pro každou konfliktní dvojici úloh. Chromatické číslo grafu je přesně minimum makespan, optimální čas na dokončení všech úloh bez konfliktů.
Strukturu grafu definují podrobnosti problému s plánováním. Například při přiřazování letadel letům je výsledný konfliktní graf intervalový graf, takže problém s barvením lze efektivně vyřešit. v přidělení šířky pásma rozhlasovým stanicím, výsledný konfliktní graf je a graf jednotkového disku, takže problém zbarvení je 3-přibližný.
Registrace přidělení
A překladač je počítačový program který překládá jeden počítačový jazyk do jiného. Chcete-li zlepšit čas provádění výsledného kódu, použijte jednu z technik optimalizace kompilátoru je přidělení registru, kde jsou nejčastěji používané hodnoty zkompilovaného programu uchovávány rychle registry procesorů. V ideálním případě jsou hodnoty přiřazeny registrům, aby se při jejich použití mohly všechny nacházet v registrech.
Učebnicovým přístupem k tomuto problému je modelovat jej jako problém s barvením grafů.[31] Kompilátor vytvoří interferenční graf, kde vrcholy jsou proměnné a hrana spojuje dva vrcholy, pokud jsou potřeba současně. Pokud lze graf obarvit pomocí k barvy pak lze uložit maximálně libovolnou sadu proměnných současně k registry.
Další aplikace
Problém zbarvení grafu nastává v mnoha praktických oblastech, jako je porovnávání vzorů, sportovní rozvrhy, navrhování plánů sezení, rozvrhování zkoušek, plánování taxíků a řešení Sudoku hádanky.[32]
Ostatní barviva
Ramseyova teorie
Důležitá třída nevhodný barvení problémy je studována v Ramseyova teorie, kde jsou hrany grafu přiřazeny k barvám a barvy dopadajících hran nejsou nijak omezeny. Jednoduchým příkladem je věta o přátelství, který uvádí, že při jakémkoli zbarvení okrajů , kompletní graf šesti vrcholů, bude monochromatický trojúhelník; často ilustrovaný tím, že každá skupina šesti lidí má buď tři společné cizí lidi, nebo tři společné známé. Ramseyova teorie se zabývá zevšeobecněním této myšlenky hledat pravidelnost uprostřed poruchy a hledat obecné podmínky pro existenci monochromatických podgrafů s danou strukturou.
Ostatní barviva
|
|
O zbarvení lze také uvažovat podepsané grafy a získat grafy.
Viz také
- Barvení hran
- Kruhové zbarvení
- Kritický graf
- Homomorfismus grafů
- Hajósova konstrukce
- Matematika sudoku
- Vícedílný graf
- Jedinečně barevný graf
- Graf zbarvení hra
- Interval zbarvení hran
Poznámky
- ^ M. Kubale, Historie barvení grafů, v Kubale (2004)
- ^ van Lint & Wilson (2001, Kap. 33)
- ^ Jensen & Toft (1995), str. 2
- ^ Brooks (1941)
- ^ Erdős, Paul (1959), „Teorie grafů a pravděpodobnost“, Kanadský žurnál matematiky, 11: 34–38, doi:10.4153 / CJM-1959-003-9.
- ^ A b Björklund, Husfeldt & Koivisto (2009)
- ^ Lawler (1976)
- ^ Beigel & Eppstein (2005)
- ^ Fomin, Gaspers & Saurabh (2007)
- ^ Wilf (1986)
- ^ Sekine, Imai & Tani (1995)
- ^ Welsh & Powell (1967)
- ^ Brélaz (1979)
- ^ A b Schneider (2010)
- ^ Cole a Vishkin (1986), viz také Cormen, Leiserson a Rivest (1990, Oddíl 30.5)
- ^ Goldberg, Plotkin & Shannon (1988)
- ^ Schneider (2008)
- ^ Barenboim & Elkin (2009); Kuhn (2009)
- ^ Např. vidět Leith & Clifford (2006) a Duffy, O'Connell a Sapozhnikov (2008).
- ^ Garey, Johnson & Stockmeyer (1974); Garey & Johnson (1979).
- ^ Dailey (1980)
- ^ Halldórsson (1993)
- ^ Zuckerman (2007)
- ^ Guruswami & Khanna (2000)
- ^ Khot (2001)
- ^ Jaeger, Vertigan a Welsh (1990)
- ^ Goldberg & Jerrum (2008)
- ^ Holyer (1981)
- ^ Crescenzi & Kann (1998)
- ^ Marx (2004)
- ^ Chaitin (1982)
- ^ Lewis, R. Průvodce barvením grafů: Algoritmy a aplikace. Springer International Publishers, 2015.
Reference
- Barenboim, L .; Elkin, M. (2009), „Distribuované (Δ + 1) barvení v lineárním (v Δ) čase“, Sborník ze 41 Symposium on Theory of Computing, str. 111–120, arXiv:0812.1379, doi:10.1145/1536414.1536432, ISBN 978-1-60558-506-2, S2CID 13446345
- Beigel, R .; Eppstein, D. (2005), „3-zbarvení v čase O (1,3289n)", Journal of Algorithms, 54 (2)): 168–204, arXiv:cs / 0006046, doi:10.1016 / j.jalgor.2004.06.008, S2CID 1209067
- Björklund, A .; Husfeldt, T .; Koivisto, M. (2009), „Nastavit rozdělení pomocí začlenění – vyloučení“, SIAM Journal on Computing, 39 (2): 546–563, doi:10.1137/070683933
- Brélaz, D. (1979), „New methods to color the vertices of a graph“, Komunikace ACM, 22 (4): 251–256, doi:10.1145/359094.359101, S2CID 14838769
- Brooks, R. L. (1941), "O vybarvení uzlů sítě", Sborník Cambridge Philosophical Society, 37 (2): 194–197, Bibcode:1941PCPS ... 37..194B, doi:10.1017 / S030500410002168X
- de Bruijn, N. G.; Erdős, P. (1951), „Barevný problém pro nekonečné grafy a problém v teorii vztahů“ (PDF), Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373, doi:10.1016 / S1385-7258 (51) 50053-7, archivovány z originál (PDF) dne 10.03.2016, vyvoláno 2009-05-16 (= Indag. Matematika. 13)
- Byskov, J. M. (2004), „Enumerating maximal independent sets with applications to graph colored“, Dopisy o operačním výzkumu, 32 (6): 547–556, doi:10.1016 / j.orl.2004.03.002
- Chaitin, G. J. (1982), „Alokace registru a rozlití pomocí zbarvení grafu“, Proc. 1982 SIGPLAN Symposium on Compiler Construction, str. 98–105, doi:10.1145/800230.806984, ISBN 0-89791-074-5, S2CID 16872867
- Cole, R .; Vishkin, U. (1986), „Deterministické házení mincí s aplikacemi pro optimální hodnocení paralelního seznamu“, Informace a kontrola, 70 (1): 32–53, doi:10.1016 / S0019-9958 (86) 80023-7
- Cormen, T. H .; Leiserson, C.E .; Rivest, R. L. (1990), Úvod do algoritmů (1. vyd.), The MIT Press
- Crescenzi, P .; Kann, V. (prosinec 1998), „Jak najít nejlepší výsledky aproximace - v návaznosti na Gareyho a Johnsona“, Novinky ACM SIGACT, 29 (4): 90, doi:10.1145/306198.306210, S2CID 15748200
- Dailey, D. P. (1980), „Jedinečnost barevnosti a barevnosti rovinných 4 pravidelných grafů je NP úplná“, Diskrétní matematika, 30 (3): 289–293, doi:10.1016 / 0012-365X (80) 90236-8
- Duffy, K .; O'Connell, N .; Sapozhnikov, A. (2008), „Analýza složitosti decentralizovaného algoritmu vybarvení grafu“ (PDF), Dopisy o zpracování informací, 107 (2): 60–63, doi:10.1016 / j.ipl.2008.01.002
- Fawcett, B. W. (1978), „On the infinite full colorings of graphs“, Umět. J. Math., 30 (3): 455–457, doi:10.4153 / cjm-1978-039-8
- Fomin, F.V.; Gaspers, S .; Saurabh, S. (2007), „Vylepšené přesné algoritmy pro počítání 3 a 4 barev“, Proc. 13. výroční mezinárodní konference, COCOON 2007, Přednášky z informatiky, 4598, Springer, str. 65–74, doi:10.1007/978-3-540-73545-8_9, ISBN 978-3-540-73544-1
- Garey, M. R.; Johnson, D. S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN 0-7167-1045-5
- Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), „Některé zjednodušené NP-úplné problémy“, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, str. 47–63, doi:10.1145/800119.803884, S2CID 207693360
- Goldberg, L. A.; Jerrum, M. (Červenec 2008), „Nepřibližitelnost Tuttova polynomu“, Informace a výpočet, 206 (7): 908–929, arXiv:cs / 0605140, doi:10.1016 / j.ic.2008.04.003, S2CID 53304001
- Goldberg, A. V.; Plotkin, S. A .; Shannon, G. E. (1988), "Paralelní rozbití symetrie v řídkých grafech", SIAM Journal on Discrete Mathematics, 1 (4): 434–446, doi:10.1137/0401044
- Guruswami, V .; Khanna, S. (2000), „O tvrdosti 4barevného 3barevného grafu“, Sborník příspěvků z 15. výroční konference IEEE o výpočetní složitosti, s. 188–197, doi:10.1109 / CCC.2000.856749, ISBN 0-7695-0674-7, S2CID 47551585
- Halldórsson, M. M. (1993), „Ještě lepší záruka výkonu pro přibližné vybarvení grafu“, Dopisy o zpracování informací, 45: 19–23, doi:10.1016/0020-0190(93)90246-6
- Holyer, I. (1981), „NP-úplnost zbarvení hran“, SIAM Journal on Computing, 10 (4): 718–720, doi:10.1137/0210055
- Jaeger, F .; Vertigan, D. L .; Welsh, D. J. A. (1990), „O výpočetní složitosti Jonesových a Tuttových polynomů“, Mathematical Proceedings of the Cambridge Philosophical Society, 108 (1): 35–53, Bibcode:1990MPCPS.108 ... 35J, doi:10.1017 / S0305004100068936
- Jensen, T. R .; Toft, B. (1995), Problémy s barvením grafů, Wiley-Interscience, New York, ISBN 0-471-02865-7
- Khot, S. (2001), „Vylepšené výsledky přibližnosti pro MaxClique, chromatické číslo a přibližné vybarvení grafu“, Proc. 42. výroční Symposium on Foundations of Computer Science, str. 600–609, doi:10.1109 / SFCS.2001.959936, ISBN 0-7695-1116-3, S2CID 11987483
- Kubale, M. (2004), Barvení grafůAmerická matematická společnost, ISBN 0-8218-3458-4
- Kuhn, F. (2009), „Slabé barvy grafů: distribuované algoritmy a aplikace“, Sborník z 21. dne Sympózium o paralelismu v algoritmech a architekturách, str. 138–144, doi:10.1145/1583991.1584032, ISBN 978-1-60558-606-9, S2CID 8857534
- Lawler, E.L. (1976), „Poznámka ke složitosti problému chromatických čísel“, Dopisy o zpracování informací, 5 (3): 66–67, doi:10.1016 / 0020-0190 (76) 90065-X
- Leith, D.J .; Clifford, P. (2006), „Self-Managed Distributed Channel Selection Algorithm for WLAN“, Proc. RAWNET 2006, Boston, MA (PDF), vyvoláno 2016-03-03
- Lewis, R.M.R. (2016), Průvodce barvením grafů: Algoritmy a aplikace Springer International Publishing, ISBN 978-3-319-25728-0
- Linial, N. (1992), "Lokalita v algoritmech distribuovaného grafu", SIAM Journal on Computing, 21 (1): 193–201, CiteSeerX 10.1.1.471.6378, doi:10.1137/0221015
- van Lint, J. H .; Wilson, R. M. (2001), Kurz kombinatoriky (2. vyd.), Cambridge University Press, ISBN 0-521-80340-3
- Marx, Dániel (2004), „Problémy s barvením grafů a jejich aplikace při plánování“, Periodica Polytechnica, elektrotechnika, 48, s. 11–16, CiteSeerX 10.1.1.95.4268
- Mycielski, J. (1955), „Sur le coloriage des graphes“ (PDF), Colloq. Matematika., 3 (2): 161–162, doi:10,4064 / cm-3-2-161-162.
- Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), „Theorem 3.13“, Sparsity: Graphs, Structures, and AlgorithmsAlgoritmy a kombinatorika, 28, Heidelberg: Springer, str. 42, doi:10.1007/978-3-642-27875-4, hdl:10338.dmlcz / 143192, ISBN 978-3-642-27874-7, PAN 2920058.
- Panconesi, Alessandro; Rizzi, Romeo (2001), „Některé jednoduché distribuované algoritmy pro řídké sítě“ (PDF), Distribuované výpočty, Berlín, New York: Springer-Verlag, 14 (2): 97–100, doi:10.1007 / PL00008932, ISSN 0178-2770, S2CID 17661948
- Panconesi, A .; Srinivasan, A. (1996), „O složitosti rozkladu distribuované sítě“, Journal of Algorithms, 20
- Sekine, K .; Imai, H .; Tani, S. (1995), "Výpočet Tutteova polynomu grafu střední velikosti", Proc. 6. mezinárodní symposium o algoritmech a výpočtech (ISAAC 1995), Přednášky z informatiky, 1004, Springer, str. 224–233, doi:10.1007 / BFb0015427, ISBN 3-540-60573-8
- Schneider, J. (2010), „Nová technika pro rozdělení distribuované symetrie“ (PDF), Sborník řízení Symposium on Principles of Distributed Computing
- Schneider, J. (2008), „Log-star distribuovaný maximální nezávislý množinový algoritmus pro grafy ohraničené růstem“ (PDF), Sborník řízení Symposium on Principles of Distributed Computing
- Welsh, D. J. A .; Powell, M. B. (1967), „Horní hranice pro chromatické číslo grafu a jeho použití na problémy s rozvrhováním času“, Počítačový deník, 10 (1): 85–86, doi:10.1093 / comjnl / 10.1.85
- West, D. B. (1996), Úvod do teorie grafů, Prentice-Hall, ISBN 0-13-227828-6
- Wilf, H. S. (1986), Algoritmy a složitost, Prentice – Hall
- Zuckerman, D. (2007), „Lineární extraktory stupňů a nepřístupnost Max Clique a Chromatic Number“, Teorie výpočtu, 3: 103–128, doi:10.4086 / toc.2007.v003a006
- Zykov, A. A. (1949), „О некоторых свойствах линейных комплексов“ [O některých vlastnostech lineárních komplexů], Rohož. Sbornik N.S. (v Rusku), 24 (66): 163–188, PAN 0035428. Přeloženo do angličtiny v angličtině Amer. Matematika. Soc. Překlad, 1952, PAN0051516.
externí odkazy
- Vysoce výkonné algoritmy pro barvení grafů Sada 8 různých algoritmů (implementovaných v C ++) použitých v knize Průvodce barvením grafů: Algoritmy a aplikace (Springer International Publishers, 2015).
- Stránka zbarvení grafu autor Joseph Culberson (programy barvení grafů)
- KOLORACE Jim Andrews a Mike Fellows je logická logická hádanka
- Odkazy na zdrojové kódy barvení grafů
- Kód pro efektivní výpočet Tutte, Chromatic a Flow Polynomials Gary Haggard, David J. Pearce a Gordon Royle
- Grafická webová aplikace autor: Jose Antonio Martin H.