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 ${\displaystyle G}$ (ang. clique number) oznaczamy ${\displaystyle \omega (G).}$

Graf, którego liczba chromatyczna jest równa rozmiarowi największej kliki ${\displaystyle (\chi (G)=\omega (G)),}$ nazywa się grafem doskonałym (ang. perfect graph)^[1].

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

Przypisy

1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 110–111. ISBN 0-387-95014-1.