Клика (теорија графова)

K₅, потпун граф. Ако подграф изгледа овако, чворови тог подграфа чине клику величине 5.

У теорији графова, клика у неусмереном графу $G=(V,E)$ је скуп чворова $V^{\prime }\subseteq V,$ такав да између свака два чвора из $V^{\prime }$, постоји грана из $E$ која их спаја. Другим речима, клика је подграф у коме је сваки чвор директно повезан са сваким другим чвором. Ово је еквивалентно исказу да је подграф индукован са $V^{\prime }$ потпун граф. Величина клике одговара броју чворова које клика садржи.

Одговор на питање да ли постоји клика дате величине у неком графу (проблем клике) је НП-комплетан проблем.

Супротност клики је независан скуп, у смислу да свакој клики одговара независан скуп у комплементу графа.

Израз клика вероватно долази од идеје да ако чворови представљају људе, а гране представљају познанства два човека, онда у датој групи свако познаје свакога, што чини клику.

Види још

• Проблем клике
• Максимална клика