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.

Aspects algorithmiques[modifier | modifier le code]

Plusieurs problème algorithmiques sont définis à partir de cliques, notamment le problème de la clique et de le problème de partition en cliques.

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

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.

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