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 ${\displaystyle [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 ${\displaystyle [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.

• Portail des mathématiques