Stable (théorie des graphes)
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Pour les articles homonymes, voir stable.
En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient.
Propriétés combinatoires
[modifier | modifier le code]La taille maximum d'un stable d'un graphe, noté I(G), est un invariant du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G). On appelle carré d'un graphe G le graphe G' utilisant les mêmes sommets et ayant une arête entre deux sommets u et v si et seulement s'il existe un chemin de longueur au plus 2 entre u et v dans G. Alors I(G') est inférieure ou égale à dom(G)[1].
Problème algorithmique
[modifier | modifier le code]La recherche d'un stable de taille maximum dans un graphe est un problème classique de la théorie de la complexité. Il est NP-complet et difficile à approximer[2].
Notes et références
[modifier | modifier le code]- (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)
- Voir article détaillé.
