Colorare completă

În teoria grafurilor, o colorare completă este opusul unei colorări armonice prin aceea că este o colorare a vârfurilor în care fiecare pereche de culori apare pe cel puțin o pereche de vârfuri adiacente. În mod echivalent, o colorare completă este o colorare minimală, în sensul că nu poate fi transformată într-o colorare propriu-zisă cu mai puține culori prin îmbinarea a două culori. Numărul acromatic ψ(G) al unui grafic G este numărul maxim de culori dintre toate colorările complete ale graficului G.

Teoria complexității

Găsirea ψ(G) este o problemă de optimizare . Problema decidabilitatii pentru o colorare completă poate fi formulată astfel:

DAT: Un grafic și un număr întreg pozitiv ÎNTREBARE: Există o partiție a mulțimii de vârfuri în sau mai multe mulțimi care nu se intersectează, astfel încât fiecare să fie o mulțime independentă și astfel încât pentru fiecare pereche de mulțimi diferite să nu fie o mulțime independentă.

Definiția unui număr acromatic este NP-hard . Determinarea dacă un număr acromatic este mai mare decât un număr dat este NP-complet , așa cum au arătat Yannakakis și Gavril în 1978 prin transformarea de la cea mai mare problemă de potrivire minimă [1] .

Rețineți că orice colorare a unui grafic cu un număr minim de culori trebuie să fie o colorare completă, astfel încât reducerea la minimum a numărului de culori a unei colorări complete este pur și simplu o reformulare a problemei standard de colorare a graficului .

Algoritm

Problema de optimizare admite o aproximare cu eficienta garantata [2] .

Cazuri speciale de grafice

Problema determinării numărului acromatic rămâne NP-complet și pentru unele clase speciale de grafuri: grafuri bipartite [3] , complemente de grafuri bipartite (adică grafuri care nu au o mulțime independentă cu mai mult de două vârfuri) [1] , cographs , interval graphs [4 ] și chiar arbori [5] .

Pentru complementele arborescente, numărul acromatic poate fi calculat în timp polinomial [6] . Pentru arbori, problema poate fi aproximată cu un coeficient constant [2] .

Se știe că numărul acromatic al graficului hipercub n - dimensional este proporțional cu , dar constanta exactă a proporționalității nu este cunoscută [7] .

Note

  1. ↑ 12 Michael R. Garey și David S. Johnson . Calculatoare și intractabilitate: un ghid pentru teoria NP-completeității . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A1.1: GT5, pag. 191.
  2. ↑ 1 2 Amitabh Chaudhary, Sundar Vishwanathan. Algoritmi de aproximare pentru numărul acromatic // Journal of Algorithms. - 2001. - T. 41 , nr. 2 . - S. 404-416 . - doi : 10.1006/jagm.2001.1192 . .
  3. ↑ M. Farber, G. Hahn, P. Hell, DJ Miller. Referitor la numărul acromatic al graficelor // Journal of Combinatorial Theory, Seria B. - 1986. - V. 40 , nr. 1 . - S. 21-39 . - doi : 10.1016/0095-8956(86)90062-6 . .
  4. ↑ H. Bodlaender. Numărul acromatic este NP-complet pentru cografe și grafice cu intervale // Informați. Proc. Lett .. - 1989. - T. 31 , nr. 3 . - S. 135-138 . - doi : 10.1016/0020-0190(89)90221-4 . .
  5. ↑ D. Manlove, C. McDiarmid. Complexitatea colorării armonioase pentru copaci // Matematică aplicată discretă. - 1995. - T. 57 , nr. 2-3 . - S. 133-144 . - doi : 10.1016/0166-218X(94)00100-R . .
  6. ↑ M. Yannakakis, F. Gavril. Seturi dominante în grafice // SIAM Journal on Applied Mathematics. - T. 38 , nr. 3 . - S. 364-372 . - doi : 10.1137/0138030 . .
  7. ↑ Y. Roichman. Despre numărul acromatic de hipercuburi // Journal of Combinatorial Theory, Seria B. - 2000. - Vol. 79 , nr. 2 . - S. 177-182 . - doi : 10.1006/jctb.2000.1955 . .

Link -uri