¿Qué significa esta afirmación: ‘Por el teorema de Menger, para cada x, y hay k’ (G) aristas disjuntas por pares ‘?

Answer 1

Tu pregunta está mal formulada. La afirmación “para todos x! = Y [vértices?] Hay k ‘(G) pares separados aristas” es trivial, ya que k’ (G) le da un corte de borde mínimo (estos bordes son pares separados) que una vez eliminados hacen x estar desconectado de y.

Probablemente tenga la pregunta equivalente como en el teorema de Menger y ¿cuántos caminos disjuntos en el borde por pares? Eso pregunta

“Según el Teorema de Menger, por cada $ x, y $ hay $ k ‘(G) $ pairwise edge-disjoint $ x, y $ path, donde $ k’ (G) $ es el tamaño mínimo de un conjunto de bordes de desconexión “.

Esta es precisamente la versión global del teorema de Menger: ver http://www.math.ubc.ca/~solymosi… (Teorema 3.3.6 (ii)). La prueba se desprende de la versión local del vértice del teorema que se prueba al comienzo de la sección.

Por cierto. Si conoce el teorema de flujo máximo-corte mínimo, puede probar fácilmente esa versión de Menger estableciendo capacidades en 0/1 e identificando los flujos con rutas.