Graficul clică al unui grafic nedirecționat G este un alt grafic K ( G ) care reprezintă structura clică a graficului G .
Graficele clicurilor au fost discutate cel puțin din 1968 [1] , iar o descriere a graficelor clicurilor a fost dată în 1971 [2] .
O clică a unui grafic G este o mulțime X de vârfuri ale unui grafic G care are proprietatea că orice pereche de vârfuri distincte ale lui X este conectată printr-o muchie în G . Clica maximă a lui G este o clică X de vârfuri a lui G , astfel încât să nu existe nicio clică a vârfurilor Y a lui G care să conțină toate vârfurile lui X plus cel puțin un alt vârf.
Având în vedere un grafic G , graficul său clică K ( G ) este un grafic astfel încât
Un grafic H este un grafic de clică K ( G ) al altui grafic dacă și numai dacă există o mulțime C de clicuri în H a cărei mulțime acoperă toate marginile lui H astfel încât C formează o familie Helly . Aceasta înseamnă că dacă S este o submulțime a lui C cu proprietatea că oricare două elemente ale lui S au o intersecție nevide, atunci S trebuie să aibă în sine o intersecție nevidă. Cu toate acestea, clicurile din setul C nu trebuie să fie clicuri maxime [2] .
Dacă H = K ( G ), se poate construi o familie C de acest tip în care fiecare clică din C corespunde unui vârf v din G și este formată din clicuri ale graficului G care conține v . Aceste clicuri au toate v la intersecția lor, deci formează o clică în H . Familia C astfel construită are proprietatea Helly, deoarece orice subfamilie C cu o intersecție perechi nevidă trebuie să corespundă unei clicuri în G care poate fi extinsă la o clică maximă care aparține intersecției subfamiliei [2] .
În schimb, dacă H are o familie de clicuri Helly C care acoperă toate muchiile lui H , atunci este un grafic de clică K ( G ) pentru G , ale cărui vârfuri sunt uniunea disjunsă a vârfurilor lui H și elementelor lui C . Acest grafic G are o muchie pentru fiecare pereche de clicuri din C cu o intersecție nevidă și pentru fiecare pereche de vârfuri din H și o clică din C care o conține. Totuși, acest grafic nu conține muchii care conectează perechi de vârfuri în H . Clicile maxime din acest grafic G constau dintr-un vârf al graficului H cu toate clicurile din C care îl conțin, iar graficul lor de intersecție este izomorf cu graficul H [2] .
Totuși, această descriere nu conduce la algoritmi eficienți - problema recunoașterii dacă un graf dat este un graf clic este NP-complet [4] .