Klika (teoria grafów)

Klika – 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. Rząd największej kliki grafu $G$ (ang. clique number) oznaczamy $\omega (G).$

Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki $(\chi (G)=\omega (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 zbioru niezależnego.

Zobacz też

• graf pełny
• graf doskonały
• liczba chromatyczna

Graf pełny K₅, będąc swoim własnym podgrafem tworzy klikę rozmiaru 5