Pełna kolorystyka - Complete coloring

Pełne kolorowanie wykresu Clebscha za pomocą 8 kolorów. Każda para kolorów pojawia się na co najmniej jednej krawędzi. Nie istnieje pełne kolorowanie z większą liczbą kolorów: w każdym 9-kolorowaniu jakiś kolor pojawiałby się tylko w jednym wierzchołku, a sąsiednich wierzchołków nie byłoby wystarczająco dużo, aby pokryć wszystkie pary zawierające ten kolor. Dlatego liczba achromatyczna wykresu Clebscha wynosi 8.

W teorii wykres , pełna barwiących jest przeciwieństwem harmonijny zabarwienia w tym sensie, że jest to wierzchołek barwienia , w którym na co najmniej jednej parze sąsiednich wierzchołków pojawia każda para kolorów. Równoważnie, pełne zabarwienie jest minimalne w tym sensie, że nie można go przekształcić w prawidłowe zabarwienie z mniejszą liczbą kolorów, łącząc pary klas kolorów. Liczba achromatyczna ψ(G) grafu G to maksymalna możliwa liczba kolorów w dowolnym pełnym zabarwieniu G.

Teoria złożoności

Znalezienie ψ(G) jest problemem optymalizacji . Problem decyzyjny dla pełnego wybarwienia można sformułować jako:

INSTANCJA: wykres i dodatnia liczba całkowita${\ Displaystyle G = (V, E)}$${\displaystyle k}$

P: nie istnieje w przegrodę z do lub więcej zbiorów rozłącznych tak, że każde JEST niezależny zestaw do i, że dla każdej pary różnych zestawów jest niezależny zestaw.${\ Displaystyle V}$${\displaystyle k}$ ${\displaystyle V_{1},V_{2},\ldots,V_{k}}$${\ Displaystyle V_ {i}}$${\ Displaystyle G}$${\ Displaystyle V_ {i}, V_ {j}, V_ {i} \ filiżanka V_ {j}}$

Wyznaczenie liczby achromatycznej jest NP-trudne ; określenie, czy jest większa niż podana liczba, jest NP-zupełne , jak wykazali Yannakakis i Gavril w 1978 r. poprzez przekształcenie z problemu minimalnego maksymalnego dopasowania.

Zauważ, że każde pokolorowanie wykresu z minimalną liczbą kolorów musi być całkowitym kolorowaniem, więc minimalizacja liczby kolorów w pełnym kolorowaniu jest tylko ponownym przedstawieniem standardowego problemu kolorowania wykresu .

Algorytmy

Dla dowolnego ustalonego k , można określić, czy liczba achromatyczna danego wykresu wynosi co najmniej k w czasie liniowym.

Problem optymalizacji pozwala na aproksymację i jest aproksymowany w stosunku aproksymacji . ${\ Displaystyle O \ lewo (| V | / {\ sqrt {\ log | V |}} \ prawej)}$

Specjalne klasy grafów

NP-kompletność achromatic Problem numer posiada również dla niektórych specjalnych klas grafów: graf dwudzielny , uzupełnień o graf dwudzielny (czyli wykresy nie posiadających niezależny zestaw więcej niż dwoma wierzchołkami), cographs i interwałowych wykresów , a nawet na drzewach .

Dla uzupełnień drzew liczbę achromatyczną można obliczyć w czasie wielomianowym. W przypadku drzew można ją przybliżyć do stałego współczynnika.

Wiadomo, że liczba achromatyczna n- wymiarowego grafu hipersześcianowego jest proporcjonalna do , ale stała proporcjonalności nie jest dokładnie znana. ${\ Displaystyle {\ sqrt {n2 ^ {n}}}}$

Bibliografia

Linki zewnętrzne

• Kompendium problemów optymalizacji NP
• Bibliografia Harmonijnych Kolorów i Liczb Achromatycznych autorstwa Keitha Edwardsa