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.Een clique of kliek is daarin een groep personen waarvan elke persoon elke andere persoon kent.

Definities

Stel  is een niet-gerichte enkelvoudige graaf. Een clique is een deelverzameling  van  die een volledige graaf induceert. Als men met  de verzameling aanduidt van alle zijden uit  die twee knopen uit  verbinden, dan is de deelgraaf  een volledige graaf.

Een maximale clique  van  is een clique waar men geen andere knoop  uit  aan kan toevoegen, zodanig dat  met  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  Het aantal knopen van de maximale clique noemt men het cliquegetal  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  vormt een onafhankelijke verzameling in de complementgraaf van  en vice versa. Deze twee begrippen zijn dus complementair.

Het chromatisch getal  van een graaf  is een bovengrens voor het cliquegetal :  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 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) 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 enzovoort. Hiervoor zijn verschillende algoritmes ontwikkeld, waaronder het Bron-Kerbosch-algoritme, dat de Nederlanders Coen Bron en Joep Kerbosch in 1973 publiceerden.  De afkorting MCE wordt ook gebruikt voor maximum clique enumeration: het vinden van alle maximumcliques in een graaf. Een algoritme dat het maximal clique enumeration-probleem oplost, lost uiteraard ook het maximum clique enumeration-probleem op.

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 in het kader van de analyse van sociale netwerken.Een clique of kliek is daarin een groep personen waarvan elke persoon elke andere persoon kent . Definities Stel is een niet-gerichte enkelvoudige graaf . Een clique is een deelverzameling van die een volledige graaf induceert . Als men met de verzameling aanduidt van alle zijden uit die twee knopen uit verbinden , dan is de deelgraaf een volledige graaf . Een maximale clique van is een clique waar men geen andere knoop uit aan kan toevoegen , zodanig dat met 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 Het aantal knopen van de maximale clique noemt men het cliquegetal 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 vormt een onafhankelijke verzameling in de complementgraaf van en vice versa . Deze twee begrippen zijn dus complementair . Het chromatisch getal van een graaf is een bovengrens voor het cliquegetal \ : 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 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 ) 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 enzovoort . Hiervoor zijn verschillende algoritmes ontwikkeld , waaronder het Bron-Kerbosch-algoritme , dat de Nederlanders Coen Bron en Joep Kerbosch inpubliceerden . De afkorting MCE wordt ook gebruikt voor maximum clique enumeration : het vinden van alle maximumcliques in een graaf . Een algoritme dat het maximal clique enumeration-probleem oplost , lost uiteraard ook het maximum clique enumeration-probleem op . Grafentheorie