Clique (grafentheorie)

In de grafentheorie is een clique of kliek een deelverzameling van de knopen van een niet-gerichte enkelvoudige graaf, waarvan de geïnduceerde deelgraaf volledig is. Dit houdt in dat elk tweetal knopen van een clique met elkaar verbonden zijn.

De term clique werd ingevoerd door Luce en Perry in 1949, in het kader van de analyse van sociale netwerken.^[1]Een clique of kliek is daarin een groep personen waarvan elke persoon elke andere persoon kent.

Definities

Deze graaf heeft cliquegetal 4: er zijn twee maximumcliques met 4 knopen (donkerblauw). Deze cliques zijn per definitie tevens maximaal. De elf lichtblauwe driehoeken zijn ook maximale cliques, met 3 knopen. De zes zijden die niet bij een driehoek horen zijn eveneens maximale cliques, met 2 knopen.

Stel $G=(V,E)$ is een niet-gerichte enkelvoudige graaf. Een clique is een deelverzameling $U$ van $V$ die een volledige graaf induceert. Als men met $F$ de verzameling aanduidt van alle zijden uit $E$ die twee knopen uit $U$ verbinden, dan is de deelgraaf $H=(U,F)$ een volledige graaf.

Een maximale clique $U$ van $G$ is een clique waar men geen andere knoop $v$ uit $V$ aan kan toevoegen, zodanig dat $U$ met $v$ erbij een clique blijft. Anders gezegd: een maximale clique is een complete deelgraaf die niet in een andere complete deelgraaf vervat is.

Onder alle maximale cliques is er minstens een met het grootste aantal knopen; dit noemt men de grootste clique of maximumclique van $G.$ Het aantal knopen van de maximale clique noemt men het cliquegetal $c(G)$ van de graaf.

Een clique cover ("clique-overdekking") is een verzameling van cliques die samen alle knopen van de graaf omvatten.

Eigenschappen

Elke clique van een graaf $G$ vormt een onafhankelijke verzameling in de complementgraaf van $G$ en vice versa. Deze twee begrippen zijn dus complementair.

Het chromatisch getal $\chi (G)$ van een graaf $G$ is een bovengrens voor het cliquegetal $c(G)$ : $\chi (G)\geq c(G)$ Voor bepaalde soorten grafen zoals perfecte grafen zijn deze twee getallen gelijk.

Problemen

Het cliqueprobleem is het beslissingsprobleem, te bepalen of een graaf een clique bevat met een gegeven minimumaantal knopen. Het is bewezen dat dit een algoritmisch moeilijk, NP-volledig probleem is. Hiermee verwant is het zoekprobleem: vind een grootste clique van een graaf^[2] of, wat op hetzelfde neerkomt: vind het cliquegetal van de graaf. Van perfecte grafen kan men het cliquegetal, en dus ook het chromatisch getal, toch in polynomiale tijd berekenen.
Het clique cover-probleem is het kleinste aantal cliques te vinden die samen alle knopen van de graaf omvatten.
Maximal clique enumeration (MCE)^[3] is het probleem om alle maximale cliques in een graaf te vinden. Dit is een NP-moeilijk probleem dat talrijke toepassingen heeft, onder meer in de bio-informatica, chemo-informatica, de analyse van verkeerssituaties^[4] enzovoort. Hiervoor zijn verschillende algoritmes ontwikkeld, waaronder het Bron-Kerbosch-algoritme, dat de Nederlanders Coen Bron en Joep Kerbosch in 1973 publiceerden.^[5] De afkorting MCE wordt ook gebruikt voor maximum clique enumeration: het vinden van alle maximumcliques in een graaf.^[6] Een algoritme dat het maximal clique enumeration-probleem oplost, lost uiteraard ook het maximum clique enumeration-probleem op.

Bronnen, noten en/of referenties

↑ R. Duncan Luce, Albert D. Perry. "A method of matrix analysis of group structure." Psychometrika, Juni 1949, Volume 14 nr. 2, pp. 95-116. DOI:10.1007/BF02289146
↑ Patrick Prosser. "Exact Algorithms for Maximum Clique: A Computational Study." Algorithms 2012, Vol. 5, pp. 545-587. DOI:10.3390/a5040545
↑ Maximal Clique Enumeration Problem
↑ Betty Majoor: "Groen licht voor meer wiskunde in het verkeer". Kennislink, 1 juli 2011
↑ Coen Bron, Joep Kerbosch. "Algorithm 457: finding all cliques of an undirected graph." Communications of the ACM, September 1973, Volume 16 nr. 9, pp. 575-577. DOI:10.1145/362342.362367
↑ John D. Eblen, Charles A. Phillips, Gary L. Rogers, Michael A. Langston. "The maximum clique enumeration problem: algorithms, applications, and implementations." BMC Bioinformatics, 2012, Vol. 13 (Suppl. 10):S5.

[1] R. Duncan Luce, Albert D. Perry. "A method of matrix analysis of group structure." Psychometrika, Juni 1949, Volume 14 nr. 2, pp. 95-116. DOI:10.1007/BF02289146

[2] Patrick Prosser. "Exact Algorithms for Maximum Clique: A Computational Study." Algorithms 2012, Vol. 5, pp. 545-587. DOI:10.3390/a5040545

[3] Maximal Clique Enumeration Problem

[4] Betty Majoor: "Groen licht voor meer wiskunde in het verkeer". Kennislink, 1 juli 2011

[5] Coen Bron, Joep Kerbosch. "Algorithm 457: finding all cliques of an undirected graph." Communications of the ACM, September 1973, Volume 16 nr. 9, pp. 575-577. DOI:10.1145/362342.362367

[6] John D. Eblen, Charles A. Phillips, Gary L. Rogers, Michael A. Langston. "The maximum clique enumeration problem: algorithms, applications, and implementations." BMC Bioinformatics, 2012, Vol. 13 (Suppl. 10):S5.

[1]

[2]

[3]

[4]

[5]

[6]