Teorema de Balinski

Eliminar dos vèrtiços qualssevol (grocs) no permet desconectar els vèrtiços restants d'un poliedre tridimensional: es pot elegir un tercer vèrtiç (vert) i una funció llineal no trivial el conjunt de la qual de zeros (blau) passe per estos tres vèrtiços, lo que permet conexions des del vèrtiç elegit al mínim i al màxim de la funció, i des de qualsevol atre vèrtiç al mínim o al màxim

En combinatoria polièdrica, una branca de les matemàtiques, la teorema de Balinski és una declaració sobre l'estructura de la teoria de grafos de poliedres tridimensionals i politopos de dimensions superiors. Afirma que, si es forma un grafo no dirigit des dels vèrtiços i arestes d'un poliedre d-tridimensional convexo o politopo (la seua esquelet), llavors el grafo resultant és a lo manco d-vèrtiços conectat: l'eliminació de qualsevol d - 1 vèrtiços deixa un subgrafo conexo. Per eixemple, per a un poliedre tridimensional, inclús si dos dels seus vèrtiços (junt en les seues vores incidents) s'eliminen, per a qualsevol parell dels vèrtiços restants encara existirà un camí de vèrtiços i arestes que conecten el parell.

La teorema de Balinski es diu aixina pel matemàtic Michel Balinski, qui va publicar la seua demostració en 1961, encara que el cas tridimensional es remonta a la primera part de el XX i al descobriment del teorema de Steinitz, que afirma que els grafos dels poliedres tridimensionals són exactament tres grafos plans conectats.

Demostració de Balinski

Balinski demostra el resultat basat en l'exactitut del algoritme símplex per a trobar el mínim o el màxim d'una funció llineal en un politopo convexo (el problema de la programació llineal). L'algoritme símplex comença en un vèrtiç arbitrari del politopo i en successives iteraciones es mou cap a un vèrtiç adjacent que millora el valor de la funció; quan no hi ha milloria que pot ser feta, s'ha alcançat el valor òptim de la funció.

Si S és un conjunt de menys de d vèrtiços que van a ser retirats del grafo del politopo, Balinski afig un vèrtiç més v₀ a S i troba una funció llineal ƒ que té el valor zero en el conjunt ampliat pero no és idénticamente igual a zero en l'espai complet. Llavors, qualsevol vèrtiç restant en el que ƒ no siga negatiu (incloent v₀) pot ser conectat per passos d'un algoritme símplex al vèrtiç en el màxim valor de ƒ, mentres que qualsevol vèrtiç restant en el que ƒ no siga positiu (de nou incloent v₀) pot ser conectat de manera similar al vèrtiç en el valor mínim de ƒ. Per lo tant, tot el gràfic restant està conectat.