Kompletní zbarvení - Complete coloring

Kompletní zbarvení Clebschův graf s 8 barvami. Každá dvojice barev se objevuje alespoň na jednom okraji. Neexistuje úplné zbarvení s více barvami: v jakémkoli 9barevném by se nějaká barva objevila pouze na jednom vrcholu a nebylo by dost sousedních vrcholů na pokrytí všech párů zahrnujících tuto barvu. Proto je achromatické číslo Clebschova grafu 8.

v teorie grafů, kompletní zbarvení je opakem harmonické zbarvení v tom smyslu, že se jedná o vrchol zbarvení ve kterém se každá dvojice barev objeví na alespoň jednom páru sousedních vrcholů. Ekvivalentně je úplné zbarvení minimální v tom smyslu, že ho nelze transformovat do správného zbarvení s méně barvami sloučením párů barevných tříd. The achromatické číslo ψ (G) grafu G je maximální možný počet barev při jakémkoli úplném zbarvení G.

Teorie složitosti

Hledání ψ (G) je optimalizační problém. The rozhodovací problém pro úplné zbarvení lze formulovat jako:

INSTANCE: graf a kladné celé číslo
OTÁZKA: existuje a rozdělit z do nebo více disjunktní sady takové, že každý je nezávislá sada pro a takové, že pro každou dvojici odlišných sad není nezávislá množina.

Určení achromatického čísla je NP-tvrdé; určení, zda je větší než dané číslo NP-kompletní, jak ukazují Yannakakis a Gavril v roce 1978 transformací z problému minimálního maximálního párování.[1]

Všimněte si, že jakékoli vybarvení grafu s minimálním počtem barev musí být úplné vybarvení, takže minimalizace počtu barev v úplném vybarvení je pouze přepracováním standardu zbarvení grafu problém.

Algoritmy

Pro všechny pevné k, je možné určit, zda je achromatické číslo daného grafu alespoň k, v lineárním čase.[2]

Problém s optimalizací umožňuje aproximaci a je přibližný v rámci a přibližný poměr.[3]

Speciální třídy grafů

NP-úplnost úlohy achromatického čísla platí i pro některé speciální třídy grafů:bipartitní grafy,[2]doplňuje z bipartitní grafy (tj. grafy, které nemají nezávislou sadu více než dvou vrcholů),[1] cographs a intervalové grafy,[4] a dokonce i pro stromy.[5]

U doplňků stromů lze achromatické číslo vypočítat v polynomiálním čase.[6] U stromů to lze odhadnout na konstantní faktor.[3]

Achromatické číslo an n-dimenzionální hyperkrychlový graf je známo, že je úměrný , ale konstanta proporcionality není přesně známa.[7]

Reference

  1. ^ A b Michael R. Garey a David S. Johnson (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN  978-0-7167-1045-5 A1.1: GT5, str.191.
  2. ^ A b Farber, M .; Hahn, G .; Sakra, P.; Miller, D. J. (1986), „Ohledně achromatického počtu grafů“, Journal of Combinatorial Theory, Series B, 40 (1): 21–39, doi:10.1016/0095-8956(86)90062-6.
  3. ^ A b Chaudhary, Amitabh; Vishwanathan, Sundar (2001), „Aproximační algoritmy pro achromatické číslo“, Journal of Algorithms, 41 (2): 404–416, CiteSeerX  10.1.1.1.5562, doi:10.1006 / jagm.2001.1192, S2CID  9817850.
  4. ^ Bodlaender, H. (1989), „Achromatic number is NP-complete for cographs and interval graphs“, Inf. Proces. Lett., 31 (3): 135–138, doi:10.1016/0020-0190(89)90221-4, hdl:1874/16576.
  5. ^ Manlove, D .; McDiarmid, C. (1995), „Složitost harmonického zbarvení stromů“, Diskrétní aplikovaná matematika, 57 (2–3): 133–144, doi:10.1016 / 0166-218X (94) 00100-R.
  6. ^ Yannakakis, M .; Gavril, F. (1980), „Okrajové sady v grafech“, SIAM Journal on Applied Mathematics, 38 (3): 364–372, doi:10.1137/0138030.
  7. ^ Roichman, Y. (2000), „O achromatickém počtu hyperkrychlí“, Journal of Combinatorial Theory, Series B, 79 (2): 177–182, doi:10.1006 / jctb.2000.1955.

externí odkazy