Klika (teorie grafů)

Klika, anglicky Clique 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.

Největší klika (1,2,5) tohoto grafu je označena červeně

Klikovost grafu je celé číslo udávající velikost největší kliky (úplného podgrafu) v daném grafu. Klikovost úplného grafu K_n 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á).

Tento problém je ze třídy NP-úplných, jelikož nalezením nezávislé množiny IND v grafu alespoň k získáme zároveň v doplňku grafu i kliku (viz vzorec níže). A Lze také dokázat, že problém logických formulí SAT z NP-úplných je redukovatelný na IND a dle předchozího je IND redukovatelný na Clique a tak patří třídě NP-úplných problémů.

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).

Související články

• Silně souvislá komponenta – příbuzný pojem pro orientované grafy

Portály: Matematika