Klika (teorie grafů)

Největší klika (1,2,5) tohoto grafu je označena červeně 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.

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. +more 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

Kategorie:Grafové pojmy