Teorema de Menger
From Wikipedia, the free encyclopedia
En la disciplina matemática de la teoría de grafos, el Teorema de Menger dice que en un gráfico finito, el tamaño de un conjunto de corte mínimo es igual al número máximo de caminos disjuntos que se pueden encontrar entre cualquier par de vértices. Probado por Karl Menger en 1927, caracteriza la conectividad de un gráfico. Se generaliza mediante el teorema de corte mínimo de flujo máximo, que es una versión de borde ponderada y que a su vez es un caso especial del teorema de dualidad fuerte para programas lineales.
