Clique (théorie des graphes)
Pour les articles homonymes, voir clique.
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
modifierDans 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
modifierPlusieurs 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
modifier- 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, (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103.
Voir aussi
modifierArticles connexes
modifierBibliographie
modifier- 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, Paris, Eyrolles, coll. « Dir. Ét. & Rech. EDF », (réimpr. 1985, 1995, 2009 chez Lavoisier, 4e ed.), 784 p. (ISBN 978-2-7430-1035-5), p. 546
Lien externe
modifier(en) Ke Xu, « Benchmarks with Hidden Optimum Solutions for Graph Problems (Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring », sur BUAA
