Graf doskonały
Graf doskonały to taki, w którym liczba chromatyczna każdego podgrafu indukowanego jest równa rozmiarowi największej kliki tego podgrafu. W grafach doskonałych ograniczenie to dotyczy nie tylko samego grafu, ale również wszystkich jego podgrafów. Przykładem grafu, który nie jest doskonały, jest cykl o długości 5, mający liczbę chromatyczną równą 3, podczas gdy największa klika wynosi 2.
Wiele istotnych klas grafów jest doskonałych, co prowadzi do prostszych rozwiązań dla trudnych problemów, takich jak kolorowanie grafów, problem kliki czy maksymalnego zbioru niezależnego. Problemy te można rozwiązać w czasie wielomianowym dla wszystkich grafów doskonałych.
Przykładowe klasy grafów doskonałych
- grafy dwudzielne
- grafy krawędziowe uzyskane z grafów dwudzielnych
- grafy przedziałowe
Charakterystyka grafów doskonałych
Silne twierdzenie o grafach doskonałych (Chudnovsky, Robertson, Seymour, Thomas, 2002) stwierdza, że graf jest doskonały wtedy i tylko wtedy, gdy jest grafem Berge, co oznacza, że nie zawiera ani nieparzystych dziur, ani nieparzystych antydziur. Dziury to podgrafy będące cyklami nieparzystej długości większej niż 4, natomiast antydziury to dopełnienia dziur.
Twierdzenie to pozwoliło na opracowanie algorytmu działającego w czasie wielomianowym, który rozstrzyga, czy dany graf jest doskonały, co klasyfikuje ten problem do klasy P.
