AlgèbreNotion · Glossaire
Clan
En théorie des graphes, un clan (ou clique) est un sous-ensemble de sommets d'un graphe tel que deux sommets quelconques de ce sous-ensemble sont reliés par une arête. Autrement dit, le sous-graphe induit par un clan est un graphe complet. La recherche du clan de taille maximale dans un graphe est un problème NP-difficile classique. Cette notion est utilisée en informatique, en bioinformatique et dans l'étude des réseaux sociaux.
Sommaire
Ce que vous allez apprendre
- Définir un clan comme un ensemble entièrement relié.
- Vérifier la propriété sur un graphe concret.
- Distinguer connexité, maximalité et taille maximale.
En clair
Imaginez un groupe de personnes, et reliez deux personnes lorsqu'elles se connaissent directement. Un clan est un groupe dans lequel chaque personne est reliée à toutes les autres. Le dessin obtenu est donc entièrement connecté : aucune paire de membres ne manque de lien. En théorie des graphes, les personnes deviennent des sommets et les liens deviennent des arêtes. Le mot « clique » désigne le même objet.
Définition
Un clan est un sous-ensemble de sommets d'un graphe dont chaque paire de sommets est reliée par une arête. Le sous-graphe induit est obtenu en conservant ces sommets et toutes les arêtes du graphe qui relient deux d'entre eux ; il est alors complet. Le terme « clique » est synonyme de « clan » dans ce contexte.
La propriété dépend des arêtes présentes entre les sommets choisis, et non de leur position dans un dessin. Un sommet isolé forme un clan à un seul sommet, car il n'existe aucune paire à relier ; cette convention est souvent incluse. Deux sommets reliés forment un clan à deux sommets. En revanche, un ensemble de trois sommets n'est un clan que si ses trois paires sont reliées.
La taille d'un clan est son nombre de sommets. Un clan maximal ne peut pas être agrandi dans le graphe considéré, tandis qu'un clan de taille maximale est un clan dont la taille est la plus grande parmi tous les clans. Ces deux adjectifs ne désignent donc pas nécessairement la même chose. La recherche d'un clan de taille maximale est un problème NP-difficile classique.
Un exemple, pas à pas
Considérons un graphe dont les sommets sont A, B, C et D. Les arêtes sont AB, AC, AD, BC, BD et CD. On cherche à vérifier si l'ensemble {A, B, C, D} est un clan.
Les six paires de sommets sont AB, AC, AD, BC, BD et CD.
Chacune de ces paires figure dans la liste des arêtes.
Le sous-graphe induit contient donc les six arêtes possibles entre quatre sommets.
Le critère est satisfait : {A, B, C, D} est un clan de taille 4.
Chacune de ces paires figure dans la liste des arêtes.
Le sous-graphe induit contient donc les six arêtes possibles entre quatre sommets.
Le critère est satisfait : {A, B, C, D} est un clan de taille 4.
Le contrôle consiste à retirer une arête, par exemple CD. La paire C-D ne serait alors plus reliée, et l'ensemble des quatre sommets ne serait plus un clan.
En pratique
En informatique, on recherche des groupes de sommets entièrement reliés pour repérer une structure dense dans un graphe. Le geste consiste à tester les arêtes de chaque paire candidate ; une paire manquante exclut immédiatement l'ensemble.
En bioinformatique, la notion peut servir à examiner des ensembles de relations représentées par un graphe. Lorsque l'on cherche le plus grand groupe possible, il faut distinguer un clan simplement non extensible d'un clan de taille maximale.
Dans l'étude des réseaux sociaux, les sommets peuvent représenter des personnes et les arêtes des relations directes. Un groupe qui paraît dense n'est retenu comme clan que si chaque paire possède effectivement l'arête définie par le modèle.
À ne pas confondre
Un clan ne se confond pas avec un sous-graphe seulement connexe. Dans un sous-graphe connexe, il suffit qu'un chemin relie les sommets ; dans un clan, chaque paire doit être reliée directement par une arête. Ainsi, trois sommets formant une chaîne A-B-C sont connexes, mais ils ne forment pas un clan si l'arête AC manque.
Un clan maximal ne se confond pas avec un clan de taille maximale. Le premier ne peut plus être agrandi avec les sommets disponibles ; le second possède la plus grande taille dans tout le graphe. Un clan de taille 3 peut être maximal alors qu'un autre clan de taille 4 existe ailleurs.
Limites et pièges
Le cas d'un seul sommet est un cas limite : il forme un clan selon la définition par paires, car aucune paire ne viole la condition. Il ne faut donc pas exiger une arête visible pour accepter ce cas ; il faut vérifier le nombre de sommets et la convention retenue.
Un graphe peut contenir plusieurs clans maximaux de même taille. Le symptôme d'une lecture erronée est de déclarer unique le clan obtenu par une méthode particulière. Il faut comparer les candidats pertinents avant d'affirmer qu'un clan est de taille maximale.
La difficulté algorithmique concerne la recherche d'un clan de taille maximale, signalée dans la définition source comme un problème NP-difficile classique. Cette limite ne signifie pas que le test d'un ensemble donné est impossible : il suffit d'examiner ses paires de sommets.
Pour aller plus loin
Le concept se prolonge naturellement vers l'étude algorithmique des graphes : après avoir reconnu un clan donné, on peut comparer les tailles des clans du graphe pour rechercher un clan de taille maximale. Cette étape change la question locale « cet ensemble est-il complet ? » en un problème global d'optimisation, dont la difficulté est mentionnée dans la définition de référence.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres