En combinatoria poliédrica , una rama de las matemáticas, el teorema de Balinski es un enunciado sobre la estructura teórica de grafos de poliedros tridimensionales y politopos de dimensiones superiores . Establece que, si uno 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 está al menos conectado con el vértice d : la eliminación de cualquier d - 1 vértices deja un subgrafo conectado. Por ejemplo, para un poliedro tridimensional, incluso si se eliminan dos de sus vértices (junto con sus bordes incidentes), para cualquier par de vértices todavía existirá una ruta de vértices y bordes que conecten el par. [1]
El teorema de Balinski lleva el nombre del matemático Michel Balinski , quien publicó su demostración en 1961, [2] aunque el caso tridimensional se remonta a principios del siglo XX y al descubrimiento del teorema de Steinitz de que las gráficas de poliedros tridimensionales son exactamente las tres gráficas planas conectadas. [3]
La prueba de Balinski
Balinski prueba el resultado basándose en la exactitud del método simplex para encontrar el mínimo o máximo de una función lineal en un politopo convexo (el problema de programación lineal ). El método simplex 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 de función óptimo.
Si S es un conjunto de menos de d vértices que se eliminarán de la gráfica 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 f no sea negativo (incluido v 0 ) se puede conectar mediante pasos simplex al vértice con el valor máximo de f, mientras que cualquier vértice restante en el que f no sea positivo (nuevamente incluido v 0 ) se puede conectar de manera similar al vértice con el valor mínimo de f. Por lo tanto, todo el gráfico restante está conectado.
Referencias
- ^ Ziegler, Günter M. (1995), "Sección 3.5: de Balinski Teorema: La gráfica es d comunicado con los", Conferencias sobre Polytopes , Graduate Textos en Matemáticas , 152 , Springer-Verlag.
- ^ Balinski, ML (1961), "Sobre la estructura gráfica de poliedros convexos en n- espacio" , Pacific Journal of Mathematics , 11 (2): 431–434, doi : 10.2140 / pjm.1961.11.431 , MR 0126765.
- ^ Steinitz, E. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathischen Wissenschaften , Band 3 (Geometries) , págs. 1-139.