Qu'est-ce qu'une clique dans la théorie des graphes ?
What is a clique in graph theory?
In graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent.
Dans la théorie des graphes, une clique est un sous-ensemble de sommets d'un graphe non orienté tel que tous les deux sommets distincts de la clique sont adjacents.
closed_qa
Dans le domaine mathématique de la théorie des graphes, une clique est un sous-ensemble de sommets d'un graphe non orienté tel que tous les deux sommets distincts de la clique sont adjacents. En d'autres termes, une clique d'un graphe G est un sous-graphe induit de G qui est complet. Les cliques sont l'un des concepts de base de la théorie des graphes et sont utilisées dans de nombreux autres problèmes mathématiques et constructions sur les graphes. Les cliques ont également été étudiées en informatique : la tâche consistant à déterminer s'il existe une clique d'une taille donnée dans un graphe (le problème des cliques) est NP-complet, mais malgré ce résultat de dureté, de nombreux algorithmes de recherche de cliques ont été étudiés.

Bien que l'étude des sous-graphes complets remonte au moins à la reformulation de la théorie de Ramsey par Erdős et Szekeres (1935), le terme "clique" vient de Luce et Perry (1949), qui ont utilisé des sous-graphes complets dans des réseaux sociaux pour modéliser des cliques de personnes, c'est-à-dire des groupes de personnes qui se connaissent toutes. Les cliques ont de nombreuses autres applications dans les sciences et notamment en bio-informatique.
fr