Teorema de Menger
Menger's theorem
- Fecha
- 1927 · fiabilidad alta
- Lugar
- Viena, Austria
- Autoría
- Karl Menger
- Ámbito
- Saber y símbolos
Qué se descubrió
Teorema de teoría de grafos que afirma que, en un grafo finito, el tamaño mínimo de un conjunto de corte entre dos vértices es igual al número máximo de caminos disjuntos entre ellos; demostrado por Karl Menger en 1927 y generalizado más tarde por el teorema de flujo máximo y corte mínimo.
A qué dio paso
- caracterización fundamental de la conectividad de grafos
- generalización posterior mediante el teorema de flujo máximo y corte mínimo
- aplicaciones en el diseño de redes robustas y tolerantes a fallos
- base teórica de los algoritmos de conectividad en informática