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 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.
La versión de conectividad de bordes del teorema de Menger es la siguiente:
El enunciado de conectividad de vértices del teorema de Menger es el siguiente:
Todas estas afirmaciones (tanto en la versión de borde como de vértice) siguen siendo ciertas en los gráficos dirigidos (cuando se consideran caminos dirigidos).
La mayoría de las pruebas directas consideran una afirmación más general para permitir demostrarla por inducción. También es conveniente utilizar definiciones que incluyan algunos casos degenerados. La siguiente prueba para gráficos no dirigidos funciona sin cambios para gráficos dirigidos o multigráficos, siempre que tomemos camino como camino dirigido.
Para conjuntos de vértices A,B ⊂ G (no necesariamente disjuntos), un camino AB es un camino en G con un vértice inicial en A , un vértice final en B y sin vértices internos en A o B. Permitimos un camino con un solo vértice en A ∩ B y cero aristas. Un separador AB de tamaño k es un conjunto S de k vértices (que pueden cruzarse con A y B ) tal que G−S no contiene ningún camino AB . Un conector AB de tamaño k es una unión de k caminos AB disjuntos en vértices .
En otras palabras, si no hay k −1 vértices que desconecten A de B , entonces existen k caminos disjuntos de A a B. Esta variante implica la afirmación anterior de conectividad de vértices: para x,y ∈ G en la sección anterior, aplique el teorema actual a G −{ x,y } con A = N(x) , B = N(y) , el vecino vértices de x,y . Entonces, un conjunto de vértices que desconectan x e y es lo mismo que un separador AB , y eliminar los vértices finales en un conjunto de caminos xy independientes da un conector AB .
Prueba del teorema: [1] Inducción sobre el número de aristas en G . Para G sin aristas, el separador AB mínimo es A ∩ B , que es en sí mismo un conector AB que consta de caminos de un solo vértice.
Para G que tiene una arista e , podemos suponer por inducción que el teorema es válido para G−e . Si G−e tiene un separador AB mínimo de tamaño k , entonces hay un conector AB de tamaño k en G−e y, por tanto, en G.
De lo contrario, sea S un separador AB de G−e de tamaño menor que k , de modo que cada camino AB en G contenga un vértice de S o el borde e . El tamaño de S debe ser k-1 , ya que si fuera menor, S junto con cualquiera de los extremos de e sería un mejor separador AB de G. En G−S hay un camino AB a través de e , ya que S por sí solo es demasiado pequeño para ser un separador AB de G . Sea v 1 el vértice anterior y v 2 el posterior de e en dicho camino. Entonces v 1 es alcanzable desde A pero no desde B en G−S−e , mientras que v 2 es alcanzable desde B pero no desde A .
Ahora, sea S 1 = S ∪ {v 1 } , y considere un separador AS 1 mínimo T en G−e . Dado que v 2 no es alcanzable desde A en G−S 1 , T también es un separador AS 1 en G . Entonces T también es un separador AB en G (porque cada camino AB corta a S 1 ). Por lo tanto tiene tamaño al menos k . Por inducción, G−e contiene un conector AS 1 C 1 de tamaño k . Debido a su tamaño, los puntos finales de los caminos deben ser exactamente S 1 .
De manera similar, dejando S 2 = S ∪ {v 2 } , un separador S 2 B mínimo tiene tamaño k , y hay un conector S 2 B C 2 de tamaño k , con caminos cuyos puntos de partida son exactamente S 2 .
Además, dado que S 1 desconecta G , cada camino en C 1 está internamente separado de cada camino en C 2 , y podemos definir un conector AB de tamaño k en G concatenando caminos ( k−1 caminos a través de S y un camino que va hasta e=v 1 v 2 ). QED
La versión de borde dirigido del teorema implica fácilmente las otras versiones. Para inferir la versión de vértice del gráfico dirigido, basta con dividir cada vértice v en dos vértices v 1 , v 2 , con todos los bordes entrantes yendo a v 1 , todos los bordes salientes yendo desde v 2 y un borde adicional de v 1 a v. 2 . Las versiones dirigidas del teorema implican inmediatamente versiones no dirigidas: basta con reemplazar cada arista de un grafo no dirigido por un par de aristas dirigidas (un digon).
La versión de borde dirigido, a su vez, se deriva de su variante ponderada, el teorema de flujo máximo y corte mínimo . Sus pruebas son a menudo pruebas de corrección de algoritmos de flujo máximo. También es un caso especial del teorema de dualidad aún más general (fuerte) para programas lineales .
Una formulación que para dígrafos finitos es equivalente a la formulación anterior es:
En esta versión, el teorema se deriva bastante fácilmente del teorema de Kőnig : en un gráfico bipartito , el tamaño mínimo de una cubierta es igual al tamaño máximo de una coincidencia.
Esto se hace de la siguiente manera: reemplazar cada vértice v en el dígrafo original D por dos vértices v' , v'' , y cada arista uv por la arista u'v'' ; Además, incluya las aristas v'v'' para cada vértice v que no esté ni en A ni en B. Esto da como resultado un gráfico bipartito, cuyo lado está formado por los vértices v' y el otro por los vértices v'' .
Aplicando el teorema de Kőnig obtenemos una coincidencia M y una cubierta C del mismo tamaño. En particular, exactamente un punto final de cada arista de M está en C. Agregue a C todos los vértices a'' , para a en A, y todos los vértices b ' , para b en B. Sea P el conjunto de todos los caminos AB compuestos por aristas uv en D tales que u'v'' pertenece a M. Sea Q en el gráfico original consta de todos los vértices v tales que tanto v' como v'' pertenecen a C . Es sencillo comprobar que Q es un conjunto de separación AB , que cada camino de la familia P contiene precisamente un vértice de Q y que cada vértice de Q se encuentra en un camino de P , como se desea. [2]
El teorema de Menger es válido para gráficos infinitos y, en ese contexto, se aplica al corte mínimo entre dos elementos cualesquiera que sean vértices o extremos del gráfico (Halin 1974). El siguiente resultado de Ron Aharoni y Eli Berger fue originalmente una conjetura propuesta por Paul Erdős , y antes de ser demostrada se conocía como conjetura de Erdős-Menger . Es equivalente al teorema de Menger cuando la gráfica es finita.