title: Polytope des stables
text: # Polytope des stables
  
  En théorie des graphes et en optimisation combinatoire, un stable est un ensemble de sommets d'un graphe deux-à-deux non adjacents. Le polytope des stables d'un graphe G est l'enveloppe convexe des fonctions caractéristiques de ses stables.
  
  ## Définition
  
  Soit G un graphe à n sommets. On se place dans l'espace $[0,1]^{n}$, et l'on représente un ensemble S de sommets de G par le vecteur ayant à la coordonnée i, 1 si i appartient à S et 0 sinon.
  
  On peut ainsi représenter les stables, qui sont les ensembles de sommets, tel que pour toute paire de sommets il n'y a pas d'arête les reliant. Étant donné un graphe on obtient ainsi un ensemble de points de $[0,1]^{n}$. Le polytope des stables d'un graphe est l'enveloppe convexe de ces points.
  
  ## Propriétés
  
  Le polytope des stables permet de caractériser certains graphes, par exemple les graphes bipartis.
  
  