Klika (teorija grafova)

K₅, potpun graf. Ako podgraf izgleda ovako, čvorovi tog podgrafa čine kliku veličine 5.

U teoriji grafova, klika u neusmerenom grafu $G=(V,E)$ je skup čvorova $V'\subseteq V,$ takav da između svaka dva čvora iz $V'$, postoji grana iz $E$ koja ih spaja. Drugim rečima, klika je podgraf u kome je svaki čvor direktno povezan sa svakim drugim čvorom. Ovo je ekvivalentno iskazu da je podgraf indukovan sa $V'$ potpun graf. Veličina klike odgovara broju čvorova koje klika sadrži.

Odgovor na pitanje da li postoji klika date veličine u nekom grafu (problem klike) je NP-kompletan problem.

Suprotnost kliki je nezavisan skup, u smislu da svakoj kliki odgovara nezavisan skup u komplementu grafa.

Izraz klika verovatno dolazi od ideje da ako čvorovi predstavljaju ljude, a grane predstavljaju poznanstva dva čoveka, onda u datoj grupi svako poznaje svakoga, što čini kliku.

Vidi još

• Problem klike
• Maksimalna klika