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

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

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

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

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

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

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