Zelené číslo - Grundy number

Tento článek je o chamtivém zbarvení grafů. Pro systém aritmetiky používaný v kombinatorické teorii her viz prudký. Hodnotu nestranné hry viz Sprague – Grundyho věta.
Optimální chamtivé zbarvení (vlevo) a zelené zbarvení (vpravo) a korunový graf. Čísla označují pořadí, ve kterém chamtivý algoritmus vybarví vrcholy.

v teorie grafů, Zelené číslo nebo Zelené chromatické číslo z neorientovaný graf je maximální počet barev, které může a. použít chamtivé zbarvení strategie, která bere v úvahu vrcholy grafu v pořadí a každému vrcholu přiřadí jeho první dostupné barva, s použitím pořadí vrcholů zvoleného tak, aby bylo použito co nejvíce barev. Zelená čísla jsou pojmenována po P. M. Grundy, který studoval analogický koncept pro řízené grafy v roce 1939.[1] Neřízenou verzi představil Christen & Selkow (1979).[2]

Příklad

Například pro a graf cesty se čtyřmi vrcholy, chromatické číslo je dva, ale Grundovo číslo je tři: pokud jsou dva koncové body cesty vybarveny jako první, chamtivý algoritmus vybarvení použije pro celý graf tři barvy.

Atomy

Zaker (2006) definuje sled volaných grafů t-atomys vlastností, že graf má alespoň Grundovo číslo t právě když obsahuje a t-atom t-atom je tvořen z nezávislá sada a a (t − 1)-atom, přidáním jedné hrany z každého vrcholu (t − 1)-atom k vrcholu nezávislé množiny takovým způsobem, že každý člen nezávislé množiny má k sobě alespoň jednu hranu. Zelené zbarvení t-atom lze získat vybarvením nezávislé množiny nejprve barvou s nejmenším číslem a následným vybarvením zbývající (t − 1)-atom s další t − 1 Například jediný 1-atom je jeden vrchol a jediný 2-atom je jeden okraj, ale existují dva možné 3-atomy: trojúhelník a cesta čtyř vrcholů.[3]

V řídkých grafech

Pro graf s n vrcholy a zvrhlost d, Zelené číslo je Ó(d log n). Zejména pro grafy omezené degenerace (např rovinné grafy ) nebo grafy, pro které chromatické číslo a degenerace jsou vzájemně ohraničeny stálými faktory (např chordální grafy ) Zelené a chromatické číslo jsou navzájem v logaritmickém faktoru.[4] Pro intervalové grafy, chromatické číslo a zelené číslo jsou navzájem v faktoru 8.[5]

Výpočetní složitost

Testování, zda je Grundovo číslo daného grafu alespoň k, pro pevnou konstantu k, lze provést v polynomiální čas, hledáním všeho možného k-atomy, které mohou být podgrafy daného grafu. Tento algoritmus však není fixovatelný parametr, protože exponent ve své době běhu závisí na k. Když k je vstupní proměnná, nikoli parametr, problém je NP-kompletní.[3] Grundyovo číslo je nanejvýš jedna plus maximální stupeň grafu a zůstává NP-úplné, aby se otestovalo, zda se rovná jedné plus maximálnímu stupni.[6] Existuje konstanta C > 1 taková, že je NP-tvrdé pod náhodným snížením na přibližný Grundyho číslo do uvnitř přibližný poměr lepší nežC.[7]

Existuje přesný exponenciální čas algoritmus pro Grundyho číslo, které běží v čase Ó(2.443n).[8]

Pro stromy, a grafy omezené šířky stromu, Zelené číslo může být neomezeně velké.[9] Grundyovo číslo lze nicméně u stromů vypočítat v polynomiálním čase a je fixovatelné, pokud je parametrizováno oběma šířka stromu a Grundyho číslo,[10] ačkoli (za předpokladu exponenciální časová hypotéza ) závislost na šířce stromu musí být větší než jednotlivě exponenciální.[8] Když je parametrizován samotným Grundyho číslem, lze jej vypočítat v pevně nastavitelném čase pro chordální grafy a grafy bez drápů,[8] a také (s použitím obecných výsledků na podgraf izomorfismus v řídké grafy pro hledání atomů) pro grafy ohraničená expanze.[8][11][12]

Dobře vybarvené grafy

Hlavní článek: Dobře vybarvený graf

Nazývá se graf dobře zbarvené pokud se jeho Zelené číslo rovná jeho chromatickému číslu. Testování, zda je graf dobře vybarvený, je coNP-complete.[3] The dědičně dobře vybarvené grafy (grafy, pro které každý indukovaný podgraf je dobře zbarvený) jsou přesně ty cographs, grafy, které nemají cestu čtyř vrcholů jako indukovaný podgraf.[2]

Reference

  1. ^ Grundy, P. M. (1939), „Matematika a hry“, Heuréka, 2: 6–8, archivováno od originál dne 2007-09-27. Jak uvádí Erdős, Paul; Hedetniemi, Stephen T .; Laskar, Renu C.; Prins, Geert C. E. (2003), „O rovnosti částečného zeleného a horního ochromatického počtu grafů“, Diskrétní matematika, 272 (1): 53–64, doi:10.1016 / S0012-365X (03) 00184-5, PAN  2019200.
  2. ^ A b Christen, Claude A .; Selkow, Stanley M. (1979), „Některé dokonalé barevné vlastnosti grafů“, Journal of Combinatorial Theory, Řada B, 27 (1): 49–59, doi:10.1016/0095-8956(79)90067-4, PAN  0539075.
  3. ^ A b C Zaker, Manouchehr (2006), „Výsledky na Grundyově chromatickém počtu grafů“, Diskrétní matematika, 306 (23): 3166–3173, doi:10.1016 / j.disc.2005.06.044, PAN  2273147.
  4. ^ Irani, Sandy (1994), „Coloring inductive graphs on-line“, Algorithmica, 11 (1): 53–72, doi:10.1007 / BF01294263, PAN  1247988.
  5. ^ Narayanaswamy, N. S .; Subhash Babu, R. (2008), „Note on first-fit colored of interval graphs“, Objednat, 25 (1): 49–53, doi:10.1007 / s11083-008-9076-6, PAN  2395157.
  6. ^ Havet, Frédéric; Sampaio, Leonardo (2010), „Na zeleném čísle grafu“, Parametrizovaný a přesný výpočet, Poznámky k přednášce ve Výpočtu. Sci., 6478, Springer, Berlín, str. 170–179, Bibcode:2010LNCS.6478..170H, doi:10.1007/978-3-642-17493-3_17, ISBN  978-3-642-17492-6, PAN  2770795.
  7. ^ Kortsarz, Guy (2007), „Dolní mez pro přibližné číslování podle Grundyho“, Diskrétní matematika a teoretická informatika, 9 (1).
  8. ^ A b C d Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015), „Složitost zeleného zbarvení a jeho varianty“, Výpočetní technika a kombinatorika, Poznámky k přednášce ve Výpočtu. Sci., 9198, Springer, Cham, str. 109–120, arXiv:1407.5336, doi:10.1007/978-3-319-21398-9_9, ISBN  978-3-319-21397-2, PAN  3447246.
  9. ^ Gyárfás, A .; Lehel, J. (1988), „On-line a first fit barvení grafů“, Journal of Graph Theory, 12 (2): 217–227, doi:10.1002 / jgt.3190120212, PAN  0940831.
  10. ^ Telle, Jan Arne; Proskurowski, Andrzej (1997), „Algoritmy pro problémy s dělením vrcholů na částečné k-stromy ", SIAM Journal on Discrete Mathematics, 10 (4): 529–550, CiteSeerX  10.1.1.25.152, doi:10.1137 / S0895480194275825, PAN  1477655.
  11. ^ Dvořák, Zdeněk; Kráľ, Daniel; Thomas, Robin (2010), „Rozhodování o vlastnostech prvního řádu pro řídké grafy“, Proc. 51. výroční sympozium IEEE o základech informatiky (FOCS 2010), IEEE Computer Soc., Los Alamitos, CA, s. 133–142, PAN  3024787.
  12. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), „18.3 Problém izomorfismu podgrafu a booleovské dotazy“, Sparsity: Graphs, Structures, and AlgorithmsAlgoritmy a kombinatorika, 28, Springer, str. 400–401, doi:10.1007/978-3-642-27875-4, hdl:10338.dmlcz / 143192, ISBN  978-3-642-27874-7, PAN  2920058.