Clique (théorie des graphes)
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Dans la théorie des graphes, une clique est un ensemble de sommets deux-à-deux adjacents (notion de graphe complet). Mais le terme « clique » est aussi souvent utilisé pour parler du graphe induit par une clique. De même, on désigne couramment par le terme « biclique » un graphe biparti complet plutôt que son ensemble de sommets ou d'arêtes.
On utilise parfois le terme p-clique ou encore clique de cardinalité p pour désigner une clique contenant p noeuds.
La recherche dans un graphe d'une clique de taille maximum est un problème classique de la théorie de la complexité. La recherche d'une clique dans un graphe revient aussi à rechercher un stable dans le graphe complémentaire (on enlève les arêtes du graphe et on rajoute celles qui n'y étaient pas).
Cette taille maximum de clique dans un graphe sert à la détermination du nombre chromatique dudit graphe.
