O clică a unui grafic neorientat este, în teoria graficelor , un subset al vârfurilor acestui grafic al cărui subgraf indus este complet , adică oricare două vârfuri ale clicei sunt întotdeauna adiacente.
O clică maximă a unui grafic este o clică cu cea mai mare cardinalitate (adică are cel mai mare număr de vârfuri). Cardinalitatea unei astfel de clici maxime este o caracteristică a graficului, numită număr de clică , și pe care o putem raporta la numărul său cromatic . Problema maximă a clicului, găsirea uneia dintre clicurile maxime pentru un grafic dat (finit), este o problemă NP-hard .
În teoria graficelor , o clică este un set de vârfuri adiacente două câte două. Dar termenul „clic” este, de asemenea, adesea folosit pentru a vorbi despre graficul indus de o clică, adică un subgraf indus complet .
La fel, termenul „biclical” este utilizat în mod obișnuit pentru a desemna un grafic bipartit complet, mai degrabă decât setul său de vârfuri sau margini.
Uneori folosim termenul p-clică sau chiar clica cardinalității p pentru a desemna o clică care conține p vârfuri.
Numărul cromatic al unui grafic este mai mare sau egal cu numărul de vârfuri din cea mai mare clică
Mai multe probleme algoritmice sunt definite din clici, în special problema clică și problema partiției clici , care fac parte din problemele Karp cu 21 NP-complete .
(ro) Ke Xu, „ Benchmarks with Hidden Optimum Solutions for Graph Problems (Maximum Clique, Maximum Independent Set, Minte Vertex Cover și Vertex Coloring) ” , pe BUAA