Plné zbarvení

V teorii grafů je úplné zbarvení opakem harmonického zbarvení v tom, že se jedná o zbarvení vrcholu , ve kterém se každý pár barev vyskytuje na alespoň jednom páru sousedních vrcholů. Ekvivalentně je úplné zbarvení minimálním zbarvením v tom smyslu, že jej nelze převést na správné zbarvení s menším počtem barev sloučením dvou barev. Achromatické číslo ψ(G) grafu G je maximální počet barev mezi všemi úplnými zabarveními grafu G.

Teorie složitosti

Hledání ψ(G) je optimalizační problém . Problém rozhoditelnosti pro plné vybarvení lze formulovat takto:

DANÝ: Graf a kladné celé číslo OTÁZKA: Existuje rozdělení množiny vrcholů do nebo více neprotínajících se množin tak, že každá je nezávislou množinou pro a taková, že pro každou dvojici různých množin není nezávislou množinou.

Definice achromatického čísla je NP-hard . Určování, zda je achromatické číslo větší než dané číslo, je NP-úplné , jak ukázali Yannakakis a Gavril v roce 1978 transformací z minimálního největšího problému shody [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 úplného vybarvení je jednoduše přeformulováním standardního problému s vybarvením grafu .

Algoritmus

Optimalizační problém připouští aproximaci s garantovanou účinností [2] .

Speciální případy grafů

Problém určení achromatického čísla zůstává NP-úplný i pro některé speciální třídy grafů: bipartitní grafy [3] , doplňky bipartitních grafů (tedy grafy, které nemají nezávislou množinu s více než dvěma vrcholy) [1] , kografy , intervalové grafy [4] a dokonce i stromy [5] .

U stromových doplňků lze achromatické číslo vypočítat v polynomiálním čase [6] . U stromů lze problém aproximovat konstantním koeficientem [2] .

Je známo, že achromatické číslo n - rozměrného grafu hyperkrychle je úměrné , ale přesná konstanta úměrnosti není známa [7] .

Poznámky

  1. ↑ 12 Michael R. Garey a David S. Johnson . Počítače a neovladatelnost: Průvodce teorií NP-úplnosti . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A1.1: GT5, str. 191.
  2. ↑ 1 2 Amitabh Chaudhary, Sundar Vishwanathan. Aproximační algoritmy pro achromatické číslo // Journal of Algorithms. - 2001. - T. 41 , no. 2 . - S. 404-416 . - doi : 10.1006/jagm.2001.1192 . .
  3. ↑ M. Farber, G. Hahn, P. Hell, DJ Miller. O achromatickém počtu grafů // Journal of Combinatorial Theory, Series B. - 1986. - V. 40 , no. 1 . - S. 21-39 . - doi : 10.1016/0095-8956(86)90062-6 . .
  4. ↑ H. Bodlaender. Achromatické číslo je NP-úplné pro kografy a intervalové grafy // Inform. Proč. Lett .. - 1989. - T. 31 , no. 3 . - S. 135-138 . - doi : 10.1016/0020-0190(89)90221-4 . .
  5. ↑ D. Manlove, C. McDiarmid. Složitost harmonického zbarvení stromů // Diskrétní aplikovaná matematika. - 1995. - T. 57 , no. 2-3 . - S. 133-144 . - doi : 10.1016/0166-218X(94)00100-R . .
  6. ↑ M. Yannakakis, F. Gavril. Hranové dominantní množiny v grafech // SIAM Journal on Applied Mathematics. - T. 38 , č.p. 3 . - S. 364-372 . - doi : 10.1137/0138030 . .
  7. ↑ Y. Roichman. O achromatickém počtu hyperkrychlí // Journal of Combinatorial Theory, Series B. - 2000. - Vol. 79 , no. 2 . - S. 177-182 . - doi : 10.1006/jctb.2000.1955 . .

Odkazy