clique - graphe -

Imaginez un réseau où chaque sommet représente une personne et chaque arête, une relation entre deux personnes. Choisissez A, B, C et D : si chacun des quatre est relié aux trois autres, ce groupe forme une clique. Une seule relation manquante suffit à empêcher le groupe entier d'en être une.

La taille de la clique se compte en sommets, pas en arêtes. Le groupe A, B, C, D est donc une clique de taille 4, même si les six arêtes qui relient ses membres sont toutes nécessaires.

Dans un graphe G, notons V(G) son ensemble de sommets et E(G) son ensemble d'arêtes. Une clique est un sous-ensemble S de V(G) tel que deux sommets distincts quelconques, notés u et v, soient adjacents.

Autrement dit, le sous-graphe formé par les sommets de S contient toutes les arêtes possibles entre eux : c'est un sous-graphe complet. Le nombre de sommets de S est la taille, ou l'ordre, de la clique. Une clique est maximale lorsqu'aucun sommet extérieur ne peut lui être ajouté tout en conservant l'adjacence de chaque paire. Cette propriété dépend de l'inclusion : une clique maximale peut être plus petite qu'une autre clique du même graphe. Une clique est maximum lorsque sa taille est la plus grande parmi toutes les cliques du graphe. Toute clique maximum est maximale, mais la réciproque est fausse.

Chercher une clique maximum est un problème NP-difficile. Le retour arrière peut exploiter une récurrence simple : retirer un sommet d'une clique de taille n laisse une clique de taille n − 1. Cette propriété guide l'exploration, sans garantir que le nombre de possibilités restera petit.

Une clique repose sur quatre éléments. Le graphe G fournit les sommets et les arêtes. Un ensemble S sélectionne certains sommets. L'adjacence deux à deux exige une arête pour chaque paire distincte de S. Le sous-graphe complet est alors la structure obtenue sur ces sommets, et sa taille est le nombre de sommets sélectionnés.

Les arêtes entre membres de S définissent la clique ; les positions, couleurs et longueurs dessinées n'ont aucun rôle mathématique. Les arêtes reliant S au reste du graphe servent ensuite à tester la maximalité : un sommet extérieur agrandit la clique seulement s'il est adjacent à tous ses membres. Le graphe conducteur rend visibles une clique maximum de taille 4 et une clique maximale de taille 3.

Considérons sept sommets A, B, C, D, E, F et G. Toutes les paires parmi A, B, C et D sont reliées. Les sommets E, F et G forment aussi un triangle, et une arête supplémentaire relie D à E.

1. Pour A, B, C et D, on vérifie les six paires AB, AC, AD, BC, BD et CD. Les six arêtes existent : ces quatre sommets forment une clique de taille 4.

2. E, F et G sont reliés deux à deux par EF, EG et FG. Ils forment donc une clique de taille 3. Elle est maximale : aucun des sommets A, B, C ou D n'est adjacent à E, F et G à la fois.

3. La clique EFG n'est pas maximum, puisque ABCD compte quatre sommets. Pour contrôler que ABCD est maximum, on observe qu'un cinquième sommet devrait être adjacent aux quatre membres ; E ne l'est qu'à D, tandis que F et G ne le sont à aucun. Le résultat est donc une taille maximum égale à 4.

Dans l'analyse d'un réseau social, une clique repère un groupe où chaque membre est directement relié à tous les autres. Si quelques relations manquent mais que le groupe reste très dense, il faut employer un modèle moins strict qu'une clique.

En bioinformatique, la recherche de cliques sert à isoler des ensembles d'éléments dont toutes les paires satisfont la relation représentée par une arête. Le graphe doit donc traduire une relation pertinente avant que la clique ait un sens dans l'application.

En optimisation combinatoire, on cherche parfois la clique maximum pour maximiser le nombre d'objets compatibles deux à deux. Une clique seulement maximale suffit si l'objectif est de ne plus pouvoir agrandir la sélection ; elle ne suffit pas si la meilleure taille globale est exigée.

Clique maximale et clique maximum. « Maximale » signifie qu'aucun sommet ne peut être ajouté à cette clique ; « maximum » signifie qu'aucune clique du graphe n'a davantage de sommets. Dans le graphe conducteur, EFG est maximale avec 3 sommets, mais ABCD est maximum avec 4 sommets.

Taille et nombre d'arêtes. La taille d'une clique est son nombre de sommets. Une clique de taille 4 possède bien six arêtes internes, mais sa taille reste 4 : compter les arêtes répond à une autre question.

Une relation manquante brise la clique. Un groupe presque complet ne répond pas à la définition : il suffit qu'une paire de sommets ne soit pas adjacente. Il faut alors réduire le groupe ou choisir un modèle de sous-graphe moins strict.

Le dessin peut tromper. Des sommets proches sur la page ne sont pas forcément adjacents, et deux arêtes qui se croisent ne créent pas un sommet. Seules les extrémités déclarées des arêtes comptent pour vérifier chaque paire.

Le retour arrière n'efface pas la difficulté. Retirer un sommet d'une clique de taille n donne bien une clique de taille n − 1, mais de nombreux choix de sommets peuvent rester à explorer. La recherche d'une clique maximum demeure NP-difficile.

La fiche Graphe complet précise la structure obtenue lorsque toutes les paires de sommets sont reliées. Elle aide à voir qu'une clique est un graphe complet trouvé à l'intérieur d'un graphe plus vaste.