Edición de «Práctica 10: Matching - Flujo Máximo (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 37: | Línea 37: | ||
* (TEO) Sea N una red con fuente s y sumidero t, tal que c(e)=1 para todo eje e -> el valor F* de un flujo máximo en N es igual al número de caminos simples disjuntos en los ejes entre s y t | * (TEO) Sea N una red con fuente s y sumidero t, tal que c(e)=1 para todo eje e -> el valor F* de un flujo máximo en N es igual al número de caminos simples disjuntos en los ejes entre s y t | ||
* (DEF) Un conjunto de ejes | * (DEF) Un conjunto de ejes “s-t separador” en un digrafo G es un conjunto de ejes, tal que si se los saca de G, no quedan caminos orientados entre s y t en el grafo resultante | ||
* (TEO) Sea N una red tal que c(e)=1 para todo eje e. La capacidad de un corte mínimo en N es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en N | * (TEO) Sea N una red tal que c(e)=1 para todo eje e. La capacidad de un corte mínimo en N es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en N | ||
* (TEO) (Menger) Sean s y t dos nodos distintos en un grafo orientado D. Entonces el máximo número de caminos orientados disjuntos entre s y t en D es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en D | * (TEO) (Menger) Sean s y t dos nodos distintos en un grafo orientado D. Entonces el máximo número de caminos orientados disjuntos entre s y t en D es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en D |