|
Polytope des stables  Cet article ne cite aucune source et peut contenir des informations erronées (signalé en janvier 2025). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
Trouver des sources sur « Polytope des 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.
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éfinitionSoit 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ésLe polytope des stables permet de caractériser certains graphes, par exemple les graphes bipartis. Notes et référencesLiens externes
Information related to Polytope des stables |
![{\displaystyle [0,1]^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40160923273b7109968df994dca832b91d957bf2)
