Клика (теорија графова)
Из Википедије, слободне енциклопедије
У теорији графова, клика у неусмереном графу G је скуп чворова V, такав да између свака два чвора из V, постоји грана која их спаја. Другим речима, клика је граф у коме је сваки чвор директно повезан са сваким другим чвором. Ово је еквивалентно исказу да је подграф индукован са V потпун граф. Величина клике одговара броју чворова које клика садржи.
Одговор на питање да ли постоји клика дате величине у неком графу (проблем клике) је НП-комплетан проблем.
Супротност клики је независан скуп, у смислу да свакој клики одговара независан скуп у комплементу графа.
Израз клика вероватно долази од идеје да ако чворови представљају људе, а гране представљају познанства два човека, онда у датој групи свако познаје свакога, што чини клику.
