Stable (théorie des graphes)
# 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.

