Täysi väritys

Graafiteoriassa täydellinen väritys on harmonisen värjäyksen vastakohta siinä mielessä , että se on kärkiväritys , jossa jokainen väripari esiintyy vähintään yhdessä vierekkäisten kärkien parissa. Vastaavasti täydellinen väritys on minimaalista värjäystä siinä mielessä, että sitä ei voida muuttaa oikeaksi värjäykseksi, jossa on vähemmän värejä yhdistämällä kaksi väriä. Kuvaajan G akromaattinen luku ψ(G) on värien enimmäismäärä graafin G kaikkien väritysten joukossa.

Monimutkaisuusteoria

ψ(G):n löytäminen on optimointiongelma . Täysvärjäyksen ratkaistavuusongelma voidaan muotoilla seuraavasti:

ANTA: Kaavio ja positiivinen kokonaisluku KYSYMYS: Onko kärkijoukko jaettu tai useampaan ei-leikkaavaan joukkoon siten , että jokainen on itsenäinen joukko ja sellainen, että jokainen eri joukkojen pari ei ole itsenäinen joukko.

Akromaattisen luvun määritelmä on NP-kova . Sen määrittäminen, onko akromaattinen luku suurempi kuin annettu luku, on NP-täydellinen , kuten Yanakakis ja Gavril vuonna 1978 osoittivat muuntamalla suurimmasta vähimmäisvastaavuusongelmasta [1] .

Huomaa, että minkä tahansa graafin värityksen, jossa on vähimmäismäärä värejä, on oltava täydellinen väritys, joten täydellisen värityksen värien määrän minimoiminen on yksinkertaisesti vakiokuvaajan väritysongelman uudelleenmuotoilua .

Algoritmi

Optimointiongelma sallii likiarvon taatulla tehokkuudella [2] .

Kaavioiden erikoistapaukset

Akromaattisen luvun määritysongelma säilyy NP-täydellisenä myös joissakin erityisissä graafiluokissa: kaksiosaiset graafit [3] , kaksiosaisten graafien komplementit (eli graafit, joilla ei ole itsenäistä joukkoa, jossa on enemmän kuin kaksi kärkeä) [1] , cographs , interval graphs [4 ] ja jopa puut [5] .

Puukomplementtien akromaattinen luku voidaan laskea polynomiajassa [6] . Puille ongelma voidaan approksimoida vakiokertoimella [2] .

Tiedetään, että n - ulotteisen hyperkuutiograafin akromaattinen luku on verrannollinen , mutta tarkkaa suhteellisuusvakiota ei tunneta [7] .

Muistiinpanot

  1. ↑ 12 Michael R. Garey ja David S. Johnson . Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A1.1: GT5, s. 191.
  2. ↑ 1 2 Amitabh Chaudhary, Sundar Vishwanathan. Approksimaatioalgoritmit akromaattiselle numerolle // 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. Mitä tulee graafien akromaattiseen lukumäärään // 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. Akromaattinen luku on NP-täydellinen kolografeille ja intervallikaavioille // Inform. Proc. Lett .. - 1989. - T. 31 , no. 3 . - S. 135-138 . - doi : 10.1016/0020-0190(89)90221-4 . .
  5. ↑ D. Manlove, C. McDiarmid. Puiden harmonisen värityksen monimutkaisuus // Discrete Applied Mathematics. - 1995. - T. 57 , no. 2-3 . - S. 133-144 . - doi : 10.1016/0166-218X(94)00100-R . .
  6. ↑ M. Yanakakis, F. Gavril. Reunaa hallitsevat joukot kaavioissa // SIAM Journal on Applied Mathematics. - T. 38 , no. 3 . - S. 364-372 . - doi : 10.1137/0138030 . .
  7. ↑ Y. Roichman. Hyperkuutioiden akromaattisesta määrästä // Journal of Combinatorial Theory, Series B. - 2000. - Vol. 79 , no. 2 . - S. 177-182 . - doi : 10.1006/jctb.2000.1955 . .

Linkit