Loading AI tools
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.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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}}](http://wikimedia.org/api/rest_v1/media/math/render/svg/40160923273b7109968df994dca832b91d957bf2)
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.
Le polytope des stables permet de caractériser certains graphes, par exemple les graphes bipartis.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
