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 , 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 . 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.

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.