Teorema de Balinski

En combinatoria poliédrica, una rama de las matemáticas, el teorema de Balinski es una declaración acerca de la estructura de la teoría de grafos de poliedros tridimensionales y politopos de dimensiones superiores. Afirma que, si uno forma un grafo no dirigido desde los vértices y aristas de un poliedro d-tridimensional convexo o politopo (su esqueleto), entonces la gráfica resultante es al menos d-vértices conectados: la eliminación de cualquier d - 1 vértices deja un subgrafo conexo. Por ejemplo, para un poliedro tridimensional, incluso si dos de sus vértices (junto con sus bordes incidentes) se eliminan, para cualquier par de vértices todavía existirá un camino de vértices y aristas que conectan el par.​

La eliminación de cualquiera de los dos vértices (amarillos) no se pueden desconectar de un poliedro tridimensional: se puede elegir un tercer vértice (verde), y una función lineal no trivial cuya puesta a cero (azul) pasa a través de estos tres vértices, lo que permite conexiones desde el vértice elegido a la mínimo y máximo de la función, y de cualquier otro vértice al mínimo o máximo.

El teorema de Balinski se llama así por el matemático Michel Balinski, quien publicó su demostración en 1961,​ aunque el caso tridimensional se remonta a la primera parte del siglo XX y el descubrimiento del teorema de Steinitz que las gráficas de poliedros tridimensionales son exactamente los tres grafos planos conectados.​

La demostración de Balinski

Balinski demuestra el resultado basado en la exactitud del algoritmo símplex para encontrar el mínimo o el máximo de una función lineal en un politopo convexo (el problema de la programación lineal). El algoritmo símplex comienza en un vértice arbitrario del politopo y en repetidas ocasiones se mueve hacia un vértice adyacente que mejora el valor de la función; cuando no hay mejoría que puede ser hecha, se ha alcanzado el valor de la función óptima.

Si S es un conjunto de menos de vértices d para ser retirado de la gráfica de la politopo, Balinski añade un vértice más v₀ a S y encuentra una función lineal ƒ que tiene el valor cero en el conjunto ampliado pero no es idénticamente igual a cero en el espacio completo. Entonces, cualquier vértice restante a la que ƒ no es negativo (incluyendo v₀) puede ser conectado por pasos simplex al vértice con el máximo valor de ƒ, mientras que cualquier vértice restante a la que ƒ no es positivo (de nuevo incluyendo v₀) puede ser conectado de manera similar al vértice con el valor mínimo de ƒ. Por lo tanto, todo el gráfico restante está conectado.

Referencias

• Datos: Q32182