Problème de la clique

Carte Commune · n° 456230

En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées. Les formulations courantes du problème de la clique incluent : la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets) ; la recherche d'une clique de poids maximum dans un graphe pondéré ; la liste de toutes les cliques maximums ; la résolution du problème de décision consistant à déterminer si un graphe contient une clique plus grande qu'une taille donnée. Le problème de la clique apparaît dans la situation réelle suivante. Considérons un réseau social, où les sommets du graphe représentent des personnes et les arêtes représentent la connaissance mutuelle entre les personnes. Une clique représente alors un sous...

Lire sur Wikipédia · Image Thore Husfeldt, CC BY-SA 3.0