Stable (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe.

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]

  1. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag, 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »)
  2. Voir article détaillé.