mały|Graf pełny K5, będąc swoim własnym podgrafem tworzy klikę rozmiaru 5
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 (ang. clique number) oznaczamy .
Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki (tzn. ma być: ), 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
Przypisy
Linki zewnętrzne [dostęp 2025-10-12].
Kategoria:Teoria grafów