Problem Kliki w Teorii Grafów
Problem kliki jest jednym z pierwszych zidentyfikowanych problemów NP-zupełnych. Klika w grafie to zbiór wierzchołków, w którym każda para wierzchołków jest połączona krawędzią. W praktyce oznacza to, że klika indukuje podgraf, który jest grafem pełnym.
Definicja Problemu
Problem kliki polega na stwierdzeniu, czy w danym grafie istnieje klika o określonym rozmiarze k. Jeśli wierzchołki należące do kliki są znane, łatwo jest potwierdzić, że tworzą one klika. Z tego powodu problem ten należy do klasy NP.
Problem Maksymalnej Kliki
Pokrewnym zagadnieniem jest problem maksymalnej kliki, który polega na wskazaniu największych klik w danym grafie. NP-zupełność problemu kliki jest związana z NP-zupełnością problemu zbioru niezależnego. Istnieje klika o rozmiarze k w grafie, jeśli i tylko jeśli w dopełnieniu tego grafu istnieje zbiór niezależny o rozmiarze k.
