Consultas 2022

Hola

Con respecto a la complejidad, sí, es el tiempo de ejecución. Hay que establecer la cota superior en cada iteración, y una cota superior a la cantidad de iteraciones. Para esto último hay que hacer ver que en cada iteración el valor del flujo aumenta y que el aumento es un entero, o sea que es por lo menos 1.

Con respecto a la corrección. Además de demostrar que termina (lo que está relacionado con lo de la complejidad), hay que demostrar que en cada iteración el aumento sigue manteniendo un flujo válido (o sea que se cumplen las condiciones de capacidad y conservación), y que al terminar el valor del flujo es máximo. Para esto último lo más importante es la demostración de que si en un grafo residual no hay camino s-t entonces el valor del flujo es igual a la capacidad de algún corte s-t. A esto hay que agregarle que el algoritmo termina porque no hay camino s-t en el grafo residual, y unos puntos anteriores con los cuales se llega a que el valor de un flujo nunca puede ser mayor que la capacidad de ningún corte.

Por otra parte, si para la resolución de un ejercicio te parece que podés usar el algoritmo, entonces no tenés que escribirlo ni hacer las demostraciones, sino hacer las referencias a lo que se dice en el libro. Una excepción a esto es si en la letra dice de manera explícita algo como "reescriba cualquier argumento del libro de referencia"; si fuera así, sí, hay que escribir el algoritmo o las demostraciones que se necesiten.

Saludos