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