Una cricca di un grafo non orientato è, nella teoria dei grafi , un sottoinsieme dei vertici di questo grafo il cui sottografo indotto è completo , cioè due vertici della cricca sono sempre adiacenti.
Una cricca massima di un grafo è una cricca con la cardinalità massima (cioè ha il maggior numero di vertici). La cardinalità di tale cricca massima è una caratteristica del grafo, chiamata numero di cricca , e che possiamo mettere in relazione con il suo numero cromatico . Il problema della cricca massima, trovando una delle cricche massime per un dato grafo (finito), è un problema NP-difficile .
Nella teoria dei grafi , una cricca è un insieme di due per due vertici adiacenti. Ma il termine “click” è spesso usato anche per parlare del grafo indotto da una cricca cioè un sottografo indotto completo .
Allo stesso modo, il termine "biclico" è comunemente usato per designare un grafo bipartito completo piuttosto che il suo insieme di vertici o spigoli.
A volte usiamo il termine p-clique o anche cricca di cardinalità p per denotare una cricca contenente p vertici.
Il numero cromatico di un grafo è maggiore o uguale al numero di vertici nella sua cricca più grande
Diversi problemi algoritmici sono definiti dalle cricche, in particolare il problema della cricca e il problema della partizione della cricca , che fanno parte dei 21 problemi NP-completi di Karp .
(it) Ke Xu, " Benchmark con soluzioni ottimali nascoste per problemi grafici (cricca massima, insieme indipendente massimo, copertura minima dei vertici e colorazione dei vertici " , su BUAA