Teljes színezés

A gráfelméletben a teljes színezés a harmonikus színezés ellentéte , mivel ez egy csúcsszínezés , amelyben minden színpár legalább egy pár szomszédos csúcson előfordul. Ennek megfelelően a teljes színezés minimális színezés, abban az értelemben, hogy két szín összevonásával nem alakítható át megfelelő színezéssé kevesebb színnel. A G gráf ψ(G) akromatikus száma a színek maximális száma a G gráf összes teljes színezése között.

Komplexitáselmélet

ψ(G) megtalálása optimalizálási probléma . A teljes színezés eldönthetőségi problémája a következőképpen fogalmazható meg:

ADOTT: Grafikon és pozitív egész szám KÉRDÉS: Létezik-e a csúcsok halmazának olyan partíciója vagy több nem metsző halmazra , hogy mindegyik független halmaz legyen , és olyan, hogy a különböző halmazok minden párja ne legyen független halmaz.

Az akromatikus szám definíciója NP-kemény . Annak meghatározása, hogy egy akromatikus szám nagyobb-e egy adott számnál, NP-teljes , amint azt Yannakakis és Gavril 1978-ban kimutatta a minimális legnagyobb illeszkedési probléma transzformációjával [1] .

Vegye figyelembe, hogy a grafikonok minimális számú színnel történő színezése teljes színezésnek kell lennie, így a teljes színezés színeinek minimalizálása egyszerűen a szabványos gráf színezési probléma újrafogalmazása .

Algoritmus

Az optimalizálási probléma garantált hatékonyságú közelítést tesz lehetővé [2] .

A grafikonok speciális esetei

Az akromatikus szám meghatározásának problémája néhány speciális gráfosztály esetében is NP-teljes marad: bipartit gráfok [3] , bipartit gráfok komplementerei (vagyis olyan gráfok, amelyeknek nincs kettőnél több csúcsú független halmaza) [1] , kográfok , intervallumgráfok [4 ] és még fák is [5] .

Fa komplementerek esetén az akromatikus szám polinomiális időben számítható ki [6] . Fák esetében a probléma egy állandó együtthatóval közelíthető [2] .

Ismeretes, hogy az n - dimenziós hiperkocka gráf akromatikus száma arányos -vel , de az arányosság pontos állandója nem ismert [7] .

Jegyzetek

  1. ↑ 12 Michael R. Garey és David S. Johnson . Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 . A1.1: GT5, p. 191.
  2. ↑ 1 2 Amitabh Chaudhary, Sundar Vishwanathan. Közelítő algoritmusok az akromatikus számhoz // Journal of Algorithms. - 2001. - T. 41 , sz. 2 . - S. 404-416 . - doi : 10.1006/jagm.2001.1192 . .
  3. ↑ M. Farber, G. Hahn, P. Hell, DJ Miller. A gráfok akromatikus számáról // 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. Az akromatikus szám NP-teljes a kográfokhoz és intervallumgráfokhoz // Inform. Proc. Lett .. - 1989. - T. 31 , sz. 3 . - S. 135-138 . - doi : 10.1016/0020-0190(89)90221-4 . .
  5. ↑ D. Manlove, C. McDiarmid. A fák harmonikus színezésének összetettsége // Discrete Applied Mathematics. - 1995. - T. 57 , sz. 2-3 . - S. 133-144 . - doi : 10.1016/0166-218X(94)00100-R . .
  6. ↑ M. Yanakakis, F. Gavril. Éldomináns halmazok gráfokban // SIAM Journal on Applied Mathematics. - T. 38 , sz. 3 . - S. 364-372 . - doi : 10.1137/0138030 . .
  7. ↑ Y. Roichman. A hiperkockák akromatikus számáról // Journal of Combinatorial Theory, Series B. - 2000. - Vol. 79 , no. 2 . - S. 177-182 . - doi : 10.1006/jctb.2000.1955 . .

Linkek