Teorema de Menger

En la disciplina matemática de la teoría de grafos , el teorema de Menger establece 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 . Demostrado por Karl Menger en 1927, caracteriza la conectividad de un grafo. Se generaliza mediante el teorema de flujo máximo y corte mínimo , que es una versión ponderada para aristas, y que a su vez es un caso especial del teorema de dualidad fuerte para programas lineales.

La versión del teorema de Menger que considera la conectividad de aristas 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 arista mínimo para x e y (el número mínimo de aristas cuya eliminación desconecta x e y ) es igual al número máximo de caminos disjuntos por aristas de x a y .

La implicación para el grafo G es la siguiente versión:

Un grafo es k -arista-conexo (permanece conectado después de eliminar menos de k aristas) si y solo si cada par de vértices tiene k caminos disjuntos por aristas entre ellos.

El enunciado de conectividad de vértices del teorema de Menger es el 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, distintos de x e y , cuya eliminación desconecta x e y ) es igual al número máximo de caminos internamente disjuntos por pares de x a y .

Una consecuencia para todo el grafo G es esta versión:

Un grafo es k -conexo por vértices (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 caminos internamente disjuntos entre sí.

Todas estas afirmaciones, tanto en su versión para aristas como para vértices, siguen siendo válidas en grafos dirigidos (al considerar caminos dirigidos).

La mayoría de las demostraciones directas consideran una afirmación más general para permitir su demostración por inducción. También resulta conveniente utilizar definiciones que incluyan algunos casos degenerados. La siguiente demostración para grafos no dirigidos funciona sin modificaciones para grafos dirigidos o multigrafos, siempre que entendamos por camino un 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 ningún vértice interno ni en A ni en B. Se permite un camino con un único 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 ) 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 .

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 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 de conectividad de vértices 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) , los vértices vecinos 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 extremos en un conjunto de caminos xy independientes da un conector AB .

Demostración 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 a su vez es un conector AB que consta de caminos de un solo vértice.

Para G que tiene una arista e , podemos asumir por inducción que el Teorema se cumple 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 lo tanto , en G.

De lo contrario, sea S un AB -separador de G−e de tamaño menor que k , de modo que cada AB -camino en G contiene un vértice de S o la arista 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 AB -separador de G. En G−S hay un AB -camino que pasa por e , ya que S solo es demasiado pequeño para ser un AB -separador de G. Sea v ₁ el vértice anterior y v ₂ el vértice posterior de e en dicho camino. Entonces v ₁ es alcanzable desde A pero no desde B en G−S−e , mientras que v ₂ es alcanzable desde B pero no desde A.

Ahora, sea S ₁ = S ∪ {v ₁ } , y consideremos un separador AS ₁ mínimo T en G−e . Como v ₂ no es alcanzable desde A en G−S ₁ , T también es un separador AS ₁ en G . Entonces T también es un separador AB en G (porque cada camino AB interseca S ₁ ). Por lo tanto, tiene un tamaño de al menos k . Por inducción, G−e contiene un conector AS ₁ C ₁ de tamaño k . Debido a su tamaño, los puntos finales de los caminos en él deben ser exactamente S ₁ .

De manera similar, si tomamos S ₂ = S ∪ {v ₂ } , un separador S ₂ B mínimo tiene tamaño k , y hay un conector S ₂ B C ₂ de tamaño k , con caminos cuyos puntos de partida son exactamente S ₂ .

Además, dado que S ₁ desconecta G , cada camino en C ₁ es internamente disjunto de cada camino en C ₂ , y podemos definir un conector AB de tamaño k en G concatenando caminos ( k−1 caminos que pasan por S y un camino que pasa por e=v ₁ v ₂ ). QED

_{La versión del teorema para aristas dirigidas implica fácilmente las demás versiones. Para inferir la versión para vértices de} grafos dirigidos, basta con dividir cada vértice v en dos vértices v₁ _y v₂ , de modo que todas las aristas entrantes vayan a v₁ , todas las salientes _salgan de v₂ y haya una arista adicional de v₁ a v₂ . Las versiones dirigidas del teorema implican inmediatamente _las 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 aristas dirigidas, a su vez, se deriva de su variante ponderada, el teorema del flujo máximo y el corte mínimo . Sus demostraciones suelen ser demostraciones de corrección para algoritmos de flujo máximo. También es un caso especial del teorema de dualidad (fuerte) aún más general para programas lineales .

Una formulación que para digrafos finitos es equivalente a la formulación anterior es:

Sean A y B conjuntos de vértices en un digrafo finito G. Entonces existe una familia P de AB -caminos disjuntos y un conjunto AB -separador que consta de exactamente un vértice de cada camino en P.

En esta versión, el teorema se deduce con bastante facilidad del teorema de Kőnig : en un grafo bipartito , el tamaño mínimo de una cobertura es igual al tamaño máximo de un emparejamiento.

Esto se hace de la siguiente manera: se reemplaza cada vértice v en el digrafo original D por dos vértices v' y v '' , y cada arista uv por la arista u'v '' ; además, se incluyen las aristas v'v '' para cada vértice v que no está ni en A ni en B. Esto da como resultado un grafo bipartito, cuyo lado consta de los vértices v' y el otro de los vértices v '' .

Aplicando el teorema de Kőnig obtenemos un emparejamiento M y una cobertura C del mismo tamaño. En particular, exactamente un extremo de cada arista de M está en C. Añadimos 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 grafo original el conjunto de todos los vértices v tales que tanto v' como v '' pertenecen a C . Es sencillo comprobar que Q es un conjunto separador AB , que cada camino en la familia P contiene exactamente un vértice de Q , y que cada vértice en Q se encuentra en un camino desde P , como se deseaba. ^{[ 2 ]}

El teorema de Menger se cumple para grafos infinitos, y en ese contexto se aplica al corte mínimo entre dos elementos cualesquiera que sean vértices o extremos del grafo ( 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 la conjetura de Erdős-Menger . Es equivalente al teorema de Menger cuando el grafo es finito.

Sean A y B conjuntos de vértices en un digrafo G (posiblemente infinito) . Entonces existe una familia P de caminos A - B disjuntos y un conjunto separador que consta de exactamente un vértice de cada camino en P.

• Gammoid
• grafo k-vértice-conectado
• grafo k-aristas-conectado
• separador de vértices

• Menger, Karl (1927). "Zur allgemeinen Kurventheorie" . Financiar. Matemáticas . 10 : 96– 115. doi : 10.4064/fm-10-1-96-115 .
• Aharoni, Ron; Berger, Eli (2008). "Teorema de Menger para gráficos infinitos". Invenciones Mathematicae . 176 (1): 1– 62. arXiv : matemáticas/0509397 . Código Bib : 2009InMat.176....1A . doi : 10.1007/s00222-008-0157-3 . S2CID 15355399 . 
• Halin, R. (1974). "Una nota sobre el teorema de Menger para gráficos infinitos localmente finitos". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 40 : 111– 114. doi : 10.1007/BF02993589 . S2CID 120915644 . 

• Una demostración del teorema de Menger
• Teoremas de Menger y el método de flujo máximo-corte mínimo