Klika (teoria grafów)
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Klika - w matematycznej teorii grafów jest to podgraf, w którym każde dwa wierzchołki są połączone krawędzią.
Klika jest maksymalna, jeśli nie da się dodać do niej wierzchołka tak, aby razem z nią również tworzył klikę. Klika jest największa (najliczniejsza), jeśli nie ma w grafie kliki o większej liczbie wierzchołków. Rozmiar największej kliki grafu G (ang. clique number) oznaczamy ω(G).
Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki (χ(G) = ω(G)), nazywa się grafem doskonałym (ang. perfect graph).
Stwierdzenie czy w grafie istnieje klika o zadanym rozmiarze (problem kliki) jest jednym z klasycznych problemów NP-zupełnych. Problemem dualnym dla problemu kliki jest problem pokrycia wierzchołkowego.
