Clique (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir clique.
Exemple de graphe possédant une 3-clique (en rouge) : les trois sommets de ce sous-graphe sont tous adjacents deux-à-deux.
Exemple de « biclique » : le graphe biparti complet K3,3.

Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents.

La clique maximum d'un graphe en est la clique dont le cardinal est le plus grand (c'est-à-dire qu'elle possède le plus grand nombre de sommets). Le cardinal de cette clique maximum est une caractéristique du graphe, appelée nombre de clique, et que l'on peut relier à son nombre chromatique. Le problème de la clique maximum, la recherche de cette clique particulière pour un graphe donné, est un problème NP-complet, et à ce titre un problème modèle en informatique théorique.

Définition[modifier | modifier le code]

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 nœuds.

Problème de la clique[modifier | modifier le code]

Énoncé[modifier | modifier le code]

Il s'agit d'établir si un graphe G donné contient une clique de cardinal au moins égal à un entier donné k. Lorsqu'on a constitué une liste de k sommets, il est trivial de vérifier s'ils forment une clique, et c'est pourquoi ce problème est de type NP.

La recherche d'une clique dans un graphe revient aussi à rechercher un stable dans le graphe complémentaire. Ce dernier graphe s'obtient en enlevant les arêtes du graphe G et en rajoutant toutes les arêtes reliant les sommets, qui n'y étaient pas.

Ainsi, le caractère « NP-complet » du problème de la clique résulte directement du caractère NP-complet du problème du « stable », parce que dire qu'un graphe contient une clique de taille k, revient à affirmer qu'il existe un stable de cardinal k dans le graphe complémentaire : en effet, si un sous-graphe est complet, le sous-graphe complément n'a pas d'arêtes.

Algorithmes[modifier | modifier le code]

La recherche exhaustive d'une k-clique à l'intérieur d'un graphe procédera par examen de tous les sous-graphes de taille k, en testant s'ils forment une clique. Toutefois, le nombre de sous-graphes de taille k dans un graphe à n sommets peut être très élevé : il est égal à {n \choose k} = \frac{n!}{k!(n-k)!}.

Une heuristique consiste à considérer chaque sommet comme une 1-clique (une clique de cardinal 1), et à former des cliques de tailles croissantes par réunion de deux cliques connues jusqu'à ce qu'il n'y ait plus de réunion possible. On pourra réunir deux cliques A et B si tout sommet de la clique A est adjacent à chaque sommet de la clique B. Cette heuristique s'exécute à un coût linéaire (fonction linéaire du nombre de sommets du graphe), mais elle peut passer à côté d’une grande clique, parce que deux ou plusieurs sommets de cette « clique intéressante » auront déjà été regroupés à une étape antérieure avec des sommets qui n'appartiennent pas à cette clique. On peut mettre en œuvre avantageusement cet algorithme grâce à la stratégie « Union-Find ».

Certains cas particuliers peuvent être résolus à un coût sous-exponentiel. Pour k = 3, il existe un algorithme de complexité O(n1.41) où n est le nombre de sommets du graphe[1].

Problème de la plus grande clique d'un graphe[modifier | modifier le code]

Le problème d'optimisation associé au « problème de la clique » est le problème de la clique maximum : il consiste à trouver la plus grande clique (au sens de son cardinal) dans un graphe. (Dans le cas où il existe plusieurs cliques de cardinal maximal, on en cherche une). La recherche dans un graphe d'une clique de taille maximale est un problème classique de la théorie de la complexité des algorithmes. Cette taille maximale, appelée nombre de clique, minore alors le nombre chromatique du graphe ; lorsque ces deux nombres sont égaux pour tous les sous-graphes induits, on dit que le graphe est parfait.

Le problème de la clique maximum fait partie des 21 problèmes NP-complets de Karp publiés en 1972 dans Reducibility Among Combinatorial Problems[2]. L'article didactique de Cook sur les problèmes NP-complets le mentionne aussi.

Notes et références[modifier | modifier le code]

  1. Observez que le « problème de la k-clique », consistant à établir s'il y a, ou pas, une « k-clique » dans un graphe donné G de taille n, est de coût exponentiel en k (et non exponentiel en n, ordre du graphe G) ; cf. à ce sujet N. Alon R. Yuster, U. Zwick, « Finding and counting given length cycles », Algorithmica, vol. 17,‎ 1997, p. 209-223 (DOI 10.1007/BF02523189)
  2. (Karp 1972)

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Claude Berge, Théorie des Graphes, éditions Dunod,‎ 1958, 250 p., « 4. Les nombres fondamentaux de la théorie des graphes »
  • M. Gondran, M. Minoux, Graphes et algorithmes, éditions Eyrolles, coll. « Dir. Ét. & Rech. EDF »,‎ 1979 (réimpr. 1985), 546 p.
  • Cook, Stephen A. (1971). « The Complexity of Theorem-Proving Procedures » Proceedings of the Third Annual ACM Symposium on Theory of Computing: 151-158. Consulté le 2007-06-11. 
  • (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, Plenum,‎ 1972 (lire en ligne), p. 85-103
  • Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, vol. A1.2: GT19, W.H. Freeman,‎ 1979 (ISBN 0-7167-1045-5), p. 194