Graf doskonały
Z Wikipedii
Graf doskonały (ang. perfect graph) to graf w którym liczba chromatyczna każdego podgrafu jest równa rozmiarowi największej kliki tego podgrafu.
W każdym grafie rozmiar kliki jest dolnym ograniczeniem na liczbę chromatyczną, ponieważ przy kolorowaniu każdy wierzchołek kliki musi otrzymać inny kolor. W grafach doskonałych to ograniczenie jest ścisłe, nie tylko dla samego grafu ale również dla wszystkich jego podgrafów. Dla innych grafów nie musi tak być: przykładowo cykl długości 5 ma liczbę chromatyczną 3, choć rozmiar największej kliki wynosi 2.
Wiele istotnych klas grafów jest grafami doskonałymi, co umożliwia znalezienie łatwych rozwiązań dla niektórych problemów trudnych w ogólności. Przykładowo problem kolorowania grafów, problem kliki i problem maksymalnego zbioru niezależnego mają rozwiązania działające dla wszystkich grafów doskonałych w wielomianowym czasie.
Przykładowe klasy grafów doskonałych to:
- grafy dwudzielne
- grafy krawędziowe uzyskane z grafów dwudzielnych
- grafy przedziałowe
[edytuj] Charakterystyka grafów doskonałych
Silne twierdzenie o grafach doskonałych (Chudnovsky, Robertson, Seymour, Thomas 2002) mówi że graf jest doskonały wtedy i tylko wtedy gdy jest grafem Berge – to znaczy nie zawiera ani nieparzystych dziur (podgrafów będących cyklami nieparzystej długości większej niż 4) ani nieparzystych antydziur (podgrafów będących dopełnieniami dziur).
Twierdzenie to umożliwiło stworzenie wielomianowego algorytmu rozstrzygającego czy dany graf jest grafem doskonałym. Tym samym problem ten należy do klasy P.
