Aide
Ajouter cette page à votre livre
Afficher le livre (0 article)
Suggérer des pagesClique (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
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]- 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
[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, 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 | 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
