Polytope des stables
Un article de Wikipédia, l'encyclopédie libre.
Soit G un graphe à n sommets. On munit l'espace usuel à n dimensions d'une correspondance entre ses dimensions et les sommets de G. Les vecteurs 0-1 de l'espace correspondent alors aux sous-ensembles de sommet de G. Naturellement, un tel vecteur correspondant à un stable de G est appelé caractéristique d'un stable de G.
Le polytope des stables d'un graphe est l'enveloppe convexe des vecteurs caractéristiques des stables du graphe.
