DSatur - DSatur

DSatur je zbarvení grafu algoritmus předložil Daniel Brélaz v roce 1979.[1] Podobně jako chamtivý barvicí algoritmus, DSatur vybarvuje vrcholy a graf jeden po druhém, v případě potřeby vyčerpání dříve nepoužité barvy. Jednou nový vrchol bylo vybarveno, algoritmus určí, který ze zbývajících neobarvených vrcholů má ve svém okolí nejvyšší počet barev a barvy tento vrchol dále. Brélaz definuje toto číslo jako stupeň nasycení daného vrcholu.[1] Snížení stupně nasycení tvoří název algoritmu.[2]:39 DSatur je heuristický algoritmus zbarvení grafu, přesto produkuje přesné výsledky pro bipartitu,[1] cyklu a grafy kol.[2] DSatur je v literatuře také označován jako saturační LF.[3]

Pseudo kód

Definujte stupeň nasycení vrcholu jako počet různých barev v jeho sousedství. Vzhledem k tomu, jednoduchý, neorientovaný graf G kompromitující sada vrcholů PROTI a okrajová sada E:[4]

  1. Vygenerovat stupeň řazení PROTI.
  2. Vyberte vrchol maximálního stupně a vybarvujte jej první barvou.
  3. Zvažte vrchol s nejvyšším stupněm nasycení. Přerušujte vazby tím, že vezmete v úvahu nejvyšší vrchol. Další vazby jsou náhodně přerušeny.
  4. Procházejte dosud vytvořenými třídami barev a vybarvujte vybraný vrchol první vhodnou barvou.
  5. Ledaže PROTI je celý barevný, vraťte se ke kroku 3

Výkon

Nejhorší složitost DSaturu je Ο(n2), v praxi však některé další výdaje vyplývají z potřeby udržovat stupeň nasycení nezbarvených vrcholů.[2] DSatur se ukázal jako přesný pro bipartitní grafy,[1] stejně jako pro cykly a grafy kol.[2] V empirickém srovnání provedeném Lewisem 2015 vytvořil DSatur výrazně lepší vrcholové barvy než chamtivý algoritmus na náhodných grafech s pravděpodobností hrany p = 0,5 při měnícím se počtu vrcholů, zatímco zase produkuje výrazně horší zabarvení než algoritmus Rekurzivní největší první.

Reference

  1. ^ A b C d Brélaz, Daniel (01.04.1979). Msgstr "Nové metody vybarvení vrcholů grafu". Komunikace ACM. 22 (4): 251–256. doi:10.1145/359094.359101. ISSN  0001-0782.
  2. ^ A b C d Lewis, R.M.R. (2016). Průvodce barvením grafů. Berlín: Springer. doi:10.1007/978-3-319-25730-3. ISBN  978-3-319-25728-0.
  3. ^ Kubale, ed. (2004). Barvení grafů (Vol.352). Providence: Americká matematická společnost. p. 13. ISBN  978-0-8218-3458-9.
  4. ^ Lewis, Rhyd (2019-01-19). "Konstruktivní algoritmy pro barvení grafů". youtube.com. Událost nastane v 3:49.