Pełna kolorystyka

Kompletne 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 dowolnym 9-kolorowaniu jakiś kolor pojawiłby się tylko w jednym wierzchołku i nie byłoby wystarczającej liczby sąsiednich wierzchołków, aby pokryć wszystkie pary zawierające ten kolor. Dlatego liczba achromatyczna wykresu Clebscha wynosi 8.

W teorii grafów kolorowanie pełne to kolorowanie wierzchołków , w którym każda para kolorów pojawia się na co najmniej jednej parze sąsiednich wierzchołków . Równoważnie, pełne zabarwienie jest minimalne w tym sensie, że nie można go przekształcić we właściwe zabarwienie z mniejszą liczbą kolorów przez połączenie par klas kolorów. Liczba achromatyczna $ψ(G)$ grafu $G$ to maksymalna liczba kolorów możliwych do dowolnego pełnego pokolorowania grafu $G$ .

Pełne kolorowanie jest przeciwieństwem harmonijnego kolorowania , które wymaga, aby każda para kolorów pojawiła się co najwyżej na jednej parze sąsiednich wierzchołków.

Teoria złożoności

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

PRZYKŁAD: wykres

G = (V, E)

i dodatnia liczba całkowita

k

PYTANIE: czy istnieje podział V na

k

lub więcej

V zbiorów

rozłącznych

V 1, V 2, \dots, V k

taki, że każdy

i

jest niezależnym zbiorem dla

G

i takie, że dla każdej pary odrębnych zbiorów

V i, V j, V i \cup V j

nie jest zbiorem niezależnym.

Określenie liczby achromatycznej jest NP-trudne ; określenie, czy jest większe niż podana liczba, jest NP-zupełne , jak wykazali Yannakakis i Gavril w 1978 r. przez transformację z problemu minimalnego maksymalnego dopasowania.

Zauważ, że każde kolorowanie wykresu z minimalną liczbą kolorów musi być pełnym kolorowaniem, więc minimalizowanie liczby kolorów w pełnym kolorowaniu jest tylko powtórzeniem standardowego problemu kolorowania wykresów .

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 aproksymowalny w stosunku aproksymacji ${\ Displaystyle O \ lewo (| V |/ {\ sqrt {\ log | V|}} \ prawej)}$ .

Specjalne klasy grafów

NP-zupełność problemu liczb achromatycznych dotyczy również niektórych specjalnych klas grafów: grafów dwudzielnych , dopełnień grafów dwudzielnych (to znaczy grafów nie mających niezależnego zbioru więcej niż dwóch wierzchołków), kografów i grafów przedziałowych , a nawet dla drzew .

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

$, że$ liczba achromatyczna n -wymiarowego wykresu hipersześcianu jest proporcjonalna do , ale stała proporcjonalności nie jest dokładnie

Linki zewnętrzne

Kompendium problemów optymalizacji NP
Bibliografia harmonijnych kolorów i liczb achromatycznych autorstwa Keitha Edwardsa