Brontekst bekijken van Clique (grafentheorie)

[[Bestand: 6n-graf-clique.svg|thumb|in rood: een clique van 3 knopen]]
In de [[grafentheorie]] is een '''clique''' of '''kliek''' een [[deelverzameling]] van de knopen van een niet-gerichte [[Grafentheorie#Enkelvoudige graaf|enkelvoudige graaf]], waarvan de geïnduceerde deelgraaf [[Grafentheorie#De volledige graaf|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.<ref>{{aut|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|id= 10.1007/BF02289146}}</ref>Een clique of [[kliek]] is daarin een groep personen waarvan elke persoon elke andere persoon kent.

==Definities==
[[Bestand: VR complex.svg|thumb|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 <math>G=(V,E)</math> is een niet-gerichte enkelvoudige graaf. Een ''clique'' is een deelverzameling <math>U</math> van <math>V</math> die een volledige graaf induceert. Als men met <math>F</math> de verzameling aanduidt van alle zijden uit <math>E</math> die twee knopen uit <math>U</math> verbinden, dan is de deelgraaf <math>H=(U,F)</math> een volledige graaf.

Een ''maximale clique'' <math>U</math> van <math>G</math> is een clique waar men geen andere knoop <math>v</math> uit <math>V</math> aan kan toevoegen, zodanig dat <math>U</math> met <math>v</math> 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 <math>G.</math> Het aantal knopen van de maximale clique noemt men het ''cliquegetal'' <math>c(G)</math> van de graaf.

Een ''clique cover'' ("clique-[[Overdekking (topologie)|overdekking]]") is een verzameling van cliques die samen alle knopen van de graaf omvatten.

==Eigenschappen==
Elke clique van een graaf <math>G</math> vormt een [[onafhankelijke verzameling]] in de [[complementgraaf]] van <math>G</math> en vice versa. Deze twee begrippen zijn dus complementair.

Het [[Kleuren van grafen|chromatisch getal]] <math>\chi(G)</math> van een graaf <math>G</math> is een bovengrens voor het cliquegetal <math>c(G)</math>: <math>\chi(G) \ge c(G)</math> 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<ref>{{aut|Patrick Prosser.}} "Exact Algorithms for Maximum Clique: A Computational Study." ''Algorithms'' 2012, Vol. 5, pp. 545-587. {{doi|id=10.3390/a5040545}}</ref> of, wat op hetzelfde neerkomt: vind het cliquegetal van de graaf.  Van [[Perfecte graaf|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)''<ref>[https://web.archive.org/web/20120115202021/http://web.eecs.utk.edu/~yzhang/ce/ Maximal Clique Enumeration Problem]</ref> 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<ref>[http://www.kennislink.nl/publicaties/groen-licht-voor-meer-wiskunde-in-het-verkeer Betty Majoor: "Groen licht voor meer wiskunde in het verkeer". Kennislink, 1 juli 2011]</ref> enzovoort. Hiervoor zijn verschillende [[algoritme]]s ontwikkeld, waaronder het [[Bron-Kerbosch-algoritme]], dat de Nederlanders [[Coenraad Bron|Coen Bron]] en Joep Kerbosch in 1973 publiceerden.<ref>{{aut|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|id=10.1145/362342.362367}}</ref>  De afkorting ''MCE'' wordt ook gebruikt voor ''maximum clique enumeration'': het vinden van alle maximumcliques in een graaf.<ref>[https://www.biomedcentral.com/1471-2105/13/S10/S5 {{aut|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.]</ref> Een algoritme dat het ''maximal clique enumeration''-probleem oplost, lost uiteraard ook het ''maximum clique enumeration''-probleem op.

{{Appendix}}

[[Categorie:Grafentheorie]]