Clique (théorie des graphes)

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.

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 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

Dans la théorie des graphes, une clique est un ensemble de sommets deux-à-deux adjacents. Mais le terme « clique » est aussi souvent utilisé pour parler du graphe induit par une clique c'est-à-dire un sous-graphe induit complet[1].

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 sommets.

Le nombre chromatique d'un graphe est supérieur ou égal au nombre de sommets dans sa plus grande clique

Aspects algorithmiques

Plusieurs problèmes algorithmiques sont définis à partir de cliques, notamment le problème de la clique et du problème de partition en cliques, qui font partie des 21 problèmes NP-complets de Karp[2].

Notes et références

Michel Rigo, Théorie des graphes (lire en ligne), p. 43.
(en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103.

Voir aussi

Articles connexes

Bibliographie

Claude Berge, Théorie des graphes et ses applications, Dunod, 1958, 267 p., chap. 4 (« Les nombres fondamentaux de la théorie des graphes »)
M. Gondran et M. Minoux, Graphes et algorithmes, Paris, Eyrolles, coll. « Dir. Ét. & Rech. EDF », 1979 (réimpr. 1985, 1995, 2009 chez Lavoisier, 4e ed.), 784 p. (ISBN 978-2-7430-1035-5), p. 546

Lien externe

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

Portail de l'informatique théorique
Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Michel Rigo, Théorie des graphes (lire en ligne), p. 43.

[2] (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103.