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 30: | Línea 30: | ||
* (TEO) Si f es una función de flujo con valor F y S es un corte en N, entonces F<=c(S). | * (TEO) Si f es una función de flujo con valor F y S es un corte en N, entonces F<=c(S). | ||
* (COR) Certificado de optimalidad: Si F es el valor de un flujo y S un corte en N tal que F=c(S) entonces F es un flujo máximo y S es un corte de capacidad mínima | * (COR) Certificado de optimalidad: Si F es el valor de un flujo y S un corte en N tal que F=c(S) entonces F es un flujo máximo y S es un corte de capacidad mínima | ||
* (TEO) Si los valores del flujo inicial y las capacidades de los ejes son enteras -> el método de Ford y Fulkerson termina en un número finito de pasos y determina un flujo máximo en N | * (TEO) Si los valores del flujo inicial y las capacidades de los ejes son enteras -> el método de Ford y Fulkerson termina en un número finito de pasos y determina un flujo máximo en N | ||
* (COR) El valor del flujo máximo en una red N es igual a la capacidad de un corte mínimo | * (COR) El valor del flujo máximo en una red N es igual a la capacidad de un corte mínimo |