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. Está generalizado por el teorema de flujo máximo y corte mínimo , 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:
- Deje G un grafo no dirigido finito y x y Y dos vértices distintos. A continuación, el tamaño de la mínima corte borde para x y y (el número mínimo de bordes cuya desconecta eliminación x y Y ) es igual al número máximo de pares caminos de borde-independiente de x a y .
- Extendido a todos los pares: un gráfico es k conectado--Edge (que permanece conectada después de la eliminación de menos de k bordes) si y sólo si cada par de vértices tiene k caminos de borde-disjuntos en el medio.
Conectividad vértice
El enunciado de conectividad de vértice del teorema de Menger es el siguiente:
- Deje G un grafo no dirigido finito y x y Y dos no adyacentes vértices. A continuación, el tamaño de la mínima corte vértice para x y y (el número mínimo de vértices, distintos de x y y , cuyos desconecta eliminación x y y ) es igual al número máximo de pares internamente caminos vértice-disjuntos de x a y .
- Extendido a todos los pares: un gráfico es k -vertex conectados (que tiene más de k vértices y permanece conectada después de la eliminación de menos de k vértices) si y sólo si cada par de vértices tiene al menos k internamente caminos vértice-disjuntos en entre .
Todas estas afirmaciones (tanto en versiones de borde como de vértice) siguen siendo verdaderas en gráficos dirigidos (cuando se consideran trayectorias dirigidas).
Prueba corta
La mayoría de las pruebas directas consideran un enunciado más general para permitir probarlo 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 gráficos múltiples, siempre que tomemos la ruta a la ruta media dirigida.
Para los conjuntos de vértices A, B ⊂ G (no necesariamente disjuntos), un AB-trayectoria es una trayectoria en G con un vértice a partir de A , un vértice final en B , y no hay 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 intersecar A y B ) de manera 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 de vértice.
- Teorema: El tamaño mínimo de un separador AB es igual al tamaño máximo de un conector AB .
En otras palabras, si no k -1 vértices de desconexión A de B , entonces existen k caminos disjuntos de A a B . Esta variante implica la declaración de conectividad de vértice anterior: 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 . A continuación, un conjunto de vértices desconectando x y y es el mismo que un AB -separator, y la eliminación de los vértices de extremo en un conjunto de independientes xy -vías da una AB -Conector.
Prueba del teorema de: [1] de inducción sobre el número de aristas en G . Para G sin aristas, el separador AB mínimo es A ∩ B , que en sí mismo es un conector AB que consta de trayectorias de vértice único.
Para que G tenga una arista e , podemos suponer por inducción que el teorema se cumple para G − e . Si G-e tiene un mínimo AB -separator de tamaño k , entonces hay un AB -Conector de tamaño k en G-e , y por lo 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 era menos, S , junto con los puntos finales de e sería una mejor AB -separator de G . En G-S hay un AB -path a través de correo , ya que S solo es demasiado pequeño para ser un AB -separator de G . Sea v 1 el anterior y v 2 el último vértice de e en dicha trayectoria. Entonces v 1 es alcanzable desde A pero no de B en G-S-e , mientras que v 2 es alcanzable desde B pero no de A .
Ahora, sea S 1 = S ∪ {v 1 } , y considere un separador AS 1 mínimo T en G − e . Desde v 2 no es accesible desde A en G-S 1 , T es también un AS 1 -separator en G . Entonces T es también un separador AB en G (porque cada camino AB se cruza con S 1 ). Por tanto, tiene un tamaño de 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 las rutas 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 C 2 S 2 B de tamaño k , con caminos cuyos puntos de partida son exactamente S 2 .
Además, dado que S 1 desconecta G , cada ruta en C 1 es internamente disjunta de cada ruta en C 2 , y podemos definir un conector AB de tamaño k en G concatenando rutas ( k − 1 rutas a través de S y una ruta que va a través de e = v 1 v 2 ). QED
Otras pruebas
La versión de borde dirigida del teorema implica fácilmente las otras versiones. Para inferir la versión gráfica vértice dirigido, basta con dividir cada vértice v en dos vértices v 1 , v 2 , con todos los bordes entrante va a v 1 , todos los bordes salientes que va de 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 borde de un gráfico no dirigido con un par de bordes dirigidos (un digón).
La versión de borde dirigido, a su vez, se deriva de su variante ponderada, el teorema de corte mínimo de flujo máximo . Sus pruebas son a menudo pruebas de corrección para 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:
- Deje que A y B sean grupos de vértices en un finito dígrafo G . Entonces existe una familia P de disjuntos AB -vías y un AB conjunto -separating que consiste en exactamente un vértice de cada trayectoria en P .
En esta versión, el teorema se sigue con bastante facilidad 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: reemplace cada vértice v en el dígrafo original D por dos vértices v ' , v' ' , y cada borde uv por el borde u'v' ' . Esto da como resultado un gráfico bipartito, cuyo un lado está formado por los vértices v ' y el otro por los vértices v' ' .
Aplicando el teorema de König obtenemos una M coincidente y una cubierta C del mismo tamaño. En particular, exactamente un punto final de cada borde de M está en C . Añadir a C todos los vértices A '' , por una en A, y todos los vértices b' , por b en B . Sea P el conjunto de todos los caminos AB compuestos de 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 de AB , que cada camino en la familia P contiene precisamente un vértice de Q , y cada vértice en Q se encuentra en un camino de P , como se desea. [2]
Gráficos infinitos
El teorema de Menger es válido para gráficas infinitas, y en ese contexto se aplica al corte mínimo entre dos elementos cualesquiera que sean vértices o extremos de la gráfica ( Halin 1974 ). El siguiente resultado de Ron Aharoni y Eli Berger fue originalmente una conjetura propuesta por Paul Erdős , y antes de ser probado se conocía como la conjetura de Erdős-Menger . Es equivalente al teorema de Menger cuando el gráfico es finito.
- Sean A y B conjuntos de vértices en un dígrafo G (posiblemente infinito) . Entonces existe una familia P de disjuntos A - B -vías y un conjunto de separación que consiste en exactamente un vértice de cada trayectoria en P .
Ver también
Referencias
- ^ F. Göring, Prueba corta del teorema de Menger , Matemáticas discretas 219 (2000) 295-296.)
- ^ Aharoni, Ron (1983). "Teorema de Menger para gráficos que no contienen caminos infinitos". Revista europea de combinatoria . 4 (3): 201–4. doi : 10.1016 / S0195-6698 (83) 80012-2 .
Otras lecturas
- Menger, Karl (1927). "Zur allgemeinen Kurventheorie". Fondo. Matemáticas . 10 : 96-115.
- Aharoni, Ron; Berger, Eli (2008). "Teorema de Menger para gráficos infinitos". Inventiones mathicae . 176 : 1. arXiv : math / 0509397 . Código Bibliográfico : 2009InMat.176 .... 1A . doi : 10.1007 / s00222-008-0157-3 .
- Halin, R. (1974). "Una nota sobre el teorema de Menger para infinitos gráficos localmente finitos". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 40 : 111. doi : 10.1007 / BF02993589 .
enlaces externos
- Una prueba del teorema de Menger
- Teoremas de Menger y Max-Flow-Min-Cut
- Flujo de red [ enlace muerto permanente ]
- Max-Flow-Min-Cut [ enlace muerto permanente ]