En la disciplina matemática de la teoría de grafos, el Teorema de Menger dice que en un grafo 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 grafo. 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.
Conectividad de borde La versión de conectividad de borde del teorema de Menger es la siguiente:
Sea G un grafo finito no dirigido y x e y dos vértices distintos. Entonces, el tamaño del corte de borde mínimo para x e y (el número mínimo de bordes cuya eliminación desconecta x e y) es igual al número máximo de caminos independientes de los bordes por pares de x a y.
Extendido a todos los pares: un grafo está conectado a k-bordes (permanece conectado después de eliminar menos de k-bordes) sí y solo si cada par de vértices tiene k caminos disjuntos de bordes en el medio.
Conectividad de vértices La declaración de conectividad de vértices del teorema de Menger es la siguiente:
Sea G un grafo finito no dirigido y x e y dos vértices no adyacentes. Entonces, el tamaño del corte de vértice mínimo para x e y (el número mínimo de vértices, distinto de x e y, cuya eliminación desconecta x e y) es igual al número máximo de caminos disyectos de vértice internos de x a y.
Extendido a todos los pares: un grafo está conectado al vértice k (tiene más de k vértices y permanece conectado después de eliminar menos de k vértices) si y solo si cada par de vértices tiene al menos k trayectorias disjuntas de vértices internas en el medio.
Todas estas declaraciones (tanto en las versiones de borde como de vértice) siguen siendo ciertas en grafo dirigidos (cuando se consideran las rutas dirigidas).
Bibliografía
Categoría:Teoremas de la teoría de grafos Categoría:Teoría de redes Categoría:Conectividad de grafos