Flujos

Question 1

Definir el problema de flujo máximo (qué datos toma y qué resultados se esperan).

Question 2

Mostrar un ejemplo de modelado de un problema como una instancia de flujo máximo.

Question 3

Enunciar el Teorema de flujo máximo-corte mínimo. Dar todas las definiciones necesarias para comprender el enunciado de este teorema.

Question 4

Describir el Algoritmo de Ford-Fulkerson para el problema de flujo máximo dar su pseudocódigo demostrar que es correcto y dar su complejidad computacional justificando las afirmaciones realizadas.

Question 5

Desarrollar una exposición del algoritmo de cancelación de ciclos para el problema de flujo de costo mínimo que contenga los siguientes puntos:

Question 6

Describir el problema de flujo de costo mínimo que resuelve este algoritmo

Question 7

Dar un ejemplo de un problema que se puede modelar con el problema de flujo de costo mínimo.

Question 8

Definir el concepto de red residual dar un ejemplo y explica informalmente qué representa la residual de una solución.

Question 9

Demostrar que una solución factible es óptima si y sólo si la red residual asociada a la solución no contiene ningún ciclo dirigido de costo negativo.

Question 10

Describir el algoritmo dando su pseudocódigo y explicando informalmente la idea del algoritmo y dar la complejidad.