title: Stable (théorie des graphes)
text: # Stable (théorie des graphes)
  
  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
  
  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).
  
  ## Problème algorithmique
  
  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.
  
  