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[1].
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.
![{\displaystyle [0,1]^{n}}](./40160923273b7109968df994dca832b91d957bf2.svg)
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.
Notes et références
- ↑ Annegret K. Wagler, Arnaud Pêcher et Sylvain Coulonges, « Polytope des stables des graphes fortement circulaires-parfaits », JPOC2 - Deuxièmes Journées Polyèdres et Optimisation Combinatoire, , p. 728–738 (lire en ligne, consulté le )
Liens externes
- Portail des mathématiques