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

Из Википедије, слободне енциклопедије
K5, потпун граф. Ако подграф изгледа овако, чворови тог подграфа чине клику величине 5.

У теорији графова, клика у неусмереном графу G је скуп чворова V, такав да између свака два чвора из V, постоји грана која их спаја. Другим речима, клика је граф у коме је сваки чвор директно повезан са сваким другим чвором. Ово је еквивалентно исказу да је подграф индукован са V потпун граф. Величина клике одговара броју чворова које клика садржи.

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

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

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

Види још[уреди]