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.

Une clique maximum d'un graphe est une clique dont le cardinal est le plus grand (c'est-à-dire qu'elle possède le plus grand nombre de sommets). Le cardinal d'une telle 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 l'une des cliques maximum pour un graphe (fini) donné, est un problème NP-difficile.

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 à exhiber, dans un graphe fini, l'une des cliques de taille maximale. C'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 décision associé à celui 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. 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 et U. Zwick, « Finding and counting given length cycles », Algorithmica, vol. 17,‎ 1997, p. 209-223 (DOI 10.1007/BF02523189, lire en ligne).
  2. (Karp 1972).

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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

Lien externe[modifier | modifier le code]

(en) Ke Xu, « Benchmarks with Hidden Optimum Solutions for Graph Problems (Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring », sur BUAA