En la combinatoria poliédrica , una rama de las matemáticas, el teorema de Balinski es una afirmación sobre la estructura grafo-teórica de los poliedros convexos tridimensionales y los politopos convexos de dimensiones superiores . Afirma que, si se forma un grafo no dirigido a partir de los vértices y aristas de un poliedro o politopo convexo d -dimensional (su esqueleto ), entonces el grafo resultante es al menos d -conexo por vértices : la eliminación de cualesquiera d − 1 vértices deja un subgrafo conexo. Por ejemplo, para un poliedro tridimensional, incluso si se eliminan dos de sus vértices (junto con sus aristas incidentes), para cualquier par de vértices seguirá existiendo un camino de vértices y aristas que conecten el par. [1]
El teorema de Balinski debe su nombre al matemático Michel Balinski , quien publicó su prueba en 1961, [2] aunque el caso tridimensional se remonta a principios del siglo XX y al descubrimiento del teorema de Steinitz de que los gráficos de los poliedros tridimensionales son exactamente los gráficos planos tridimensionales. [3]
Balinski demuestra el resultado basándose en la corrección del método símplex para hallar el mínimo o máximo de una función lineal en un politopo convexo (el problema de programación lineal ). El método símplex comienza en un vértice arbitrario del politopo y se mueve repetidamente hacia un vértice adyacente que mejora el valor de la función; cuando no se puede realizar ninguna mejora, se ha alcanzado el valor óptimo de la función.
Si S es un conjunto de menos de d vértices que se deben eliminar del grafo del politopo, Balinski agrega un vértice más v 0 a S y encuentra una función lineal ƒ que tiene el valor cero en el conjunto aumentado pero no es idénticamente cero en todo el espacio. Entonces, cualquier vértice restante en el que ƒ no sea negativo (incluido v 0 ) se puede conectar mediante pasos símplex al vértice con el valor máximo de ƒ, mientras que cualquier vértice restante en el que ƒ no sea positivo (de nuevo incluido v 0 ) se puede conectar de manera similar al vértice con el valor mínimo de ƒ. Por lo tanto, todo el grafo restante está conectado.