Teljes színezés

A Clebsch-gráf teljes színezése 8 színnel. Minden színpár legalább egy élen megjelenik. Több színnel nem lehetséges teljes színezés: bármely 9-színezésben lenne olyan szín, ami csak egy csúcson jelenik meg, és nem lenne elég szomszédos csúcs a csúcson lévő színhez tartozó összes párosítás kimerítéséhez. Ezért a Clebsch-gráf akromatikus száma 8.

A matematika, azon belül a gráfelmélet területén a teljes színezés (complete coloring) a harmonikus színezés ellentéte, abban az értelemben, hogy olyan jó csúcsszínezés, melyben minden színpár előfordul legalább egy szomszédos csúcspáron. A teljes színezés abban az értelemben minimális, hogy színosztály-párok összeolvasztásával nem alakítható át kevesebb színnel történő jó színezéssé. A G gráf akromatikus száma, ψ(G) a maximális színek száma, mellyel elvégezhető G teljes színezése.

Bonyolultságelmélet

A ψ(G) értékének megállapítása egy optimalizálási probléma. A teljes színezés döntési problémája a következőképpen mondható ki:

BEMENET: egy G = ( V , E ) {\displaystyle G=(V,E)} gráf és a k {\displaystyle k} pozitív egész
KÉRDÉS: létezik-e V {\displaystyle V} -nek k {\displaystyle k} vagy több diszjunkt V 1 , V 2 , … , V k {\displaystyle V_{1},V_{2},\ldots ,V_{k}} halmazokra való particionálása úgy, hogy minden V i {\displaystyle V_{i}} a G {\displaystyle G} -nek egy független csúcshalmaza és egyik V i , V j , V i ∪ V j {\displaystyle V_{i},V_{j},V_{i}\cup V_{j}} halmazpár sem alkot független csúcshalmazt.

Az akromatikus szám meghatározása NP-nehéz; annak meghatározása, hogy adott számnál nagyobb-e, NP-teljes, ahogy azt Yannakakis és Gavril 1978-ban megmutatták a minimális értékű maximális párosítás problémájából való transzformációval.[1]

Egy gráf minimális számú színnel való színezése mindenképpen teljes színezés, így egy teljes színezés színeinek minimalizálása csak a szokásos gráfszínezési probléma újrafogalmazása.

Algoritmusok

Rögzített k-ra lineáris időben megállapítható, hogy adott gráf akromatikus száma legalább k-e.[2]

Az optimalizálási probléma lehetővé teszi a közelítést, és O ( | V | / log ⁡ | V | ) {\displaystyle O\left(|V|/{\sqrt {\log |V|}}\right)} approximációs aránnyal közelíthető.[3]

Speciális gráfosztályok

Az akromatikus szám problémájának NP-teljessége még néhány speciális gráfosztályra igaz, ezek közé tartoznak: a páros gráfok,[2] a páros gráfok komplementerei (tehát a két csúcsnál nagyobb független halmazzal nem rendelkező gráfok),[1] a kográfok és az intervallumgráfok,[4] és még a fák is.[5]

Fák komplementereinek akromatikus száma polinom időben kiszámítható.[6] Fák esetében konstans faktorral approximálható.[3]

Ismert, hogy az n dimenziós hiperkockagráf akromatikus száma n 2 n {\displaystyle {\sqrt {n2^{n}}}} -nel arányos, de az arány konstans tagja precízen nem ismert.[7]

Fordítás

  • Ez a szócikk részben vagy egészben a Complete coloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. ↑ a b Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.1: GT5, pg.191.
  2. ↑ a b Farber, M.; Hahn, G. & Hell, P. et al. (1986), "Concerning the achromatic number of graphs", 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), "Approximation algorithms for the achromatic number", Journal of Algorithms 41 (2): 404–416, DOI 10.1006/jagm.2001.1192.
  4. ↑ Bodlaender, H. (1989), "Achromatic number is NP-complete for cographs and interval graphs", Inform. Proc. Lett. 31 (3): 135–138, DOI 10.1016/0020-0190(89)90221-4.
  5. ↑ Manlove, D. & McDiarmid, C. (1995), "The complexity of harmonious coloring for trees", Discrete Applied Mathematics 57 (2-3): 133–144, DOI 10.1016/0166-218X(94)00100-R.
  6. ↑ Yannakakis, M. & Gavril, F. (1980), "Edge dominating sets in graphs", SIAM Journal on Applied Mathematics 38 (3): 364–372, DOI 10.1137/0138030.
  7. ↑ Roichman, Y. (2000), "On the Achromatic Number of Hypercubes", Journal of Combinatorial Theory, Series B 79 (2): 177–182, DOI 10.1006/jctb.2000.1955.

További információk

  • A compendium of NP optimization problems
  • A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards