Klika (teorie grafů)
Z Wikipedie, otevřené encyklopedie
Klika je takový podgraf nějakého grafu, který je úplným grafem, tzn. jehož všechny vrcholy jsou spojeny hranou se všemi zbylými.
Klikovost grafu je celé číslo udávající velikost největší kliky (úplného podgrafu) v daném grafu. Klikovost úplného grafu Kn je n, klikovost diskrétního grafu je 1. Klikovost grafu G se značí ω(G).
Problém nalezení takového čísla (resp. nalezení největší kliky) je NP-těžký (rozhodovací verze, zda daný graf má klikovost alespoň k, je NP-úplná).
Klikovost těsně souvisí s nezávislostí – je zřejmé, že v doplňku grafu odpovídá klice nezávislá podmnožina, takže platí
- ω(G) = α(−G).
