Teorema de Menger

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.

Conectividad de borde

La versión de conectividad de borde del teorema de Menger es la siguiente:

Sea G un gráfico 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 gráfico 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 gráfico 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 gráfico 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 gráficos dirigidos (cuando se consideran las rutas dirigidas).

Bibliografía

• Menger, Karl (1927). «Zur allgemeinen Kurventheorie». Fund. Math. 10: 96-115. doi:10.4064/fm-10-1-96-115. 
• Aharoni, Ron; Berger, Eli (2008). «Menger's theorem for infinite graphs». Inventiones Mathematicae 176 (1): 1-62. Bibcode:2009InMat.176....1A. S2CID 15355399. arXiv:math/0509397. doi:10.1007/s00222-008-0157-3. 
• Halin, R. (1974). «A note on Menger's theorem for infinite locally finite graphs». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 40: 111-114. S2CID 120915644. doi:10.1007/BF02993589. 

• Datos: Q928813