Aula Teórica 25

9 dezembro 2014, 10:30 • Maria Paula Antunes Abrantes Gouveia

Fluxos em redes capacitadas: motivação. Rede s-t capacitada, fluxo e valor de fluxo, capacidade residual de um arco induzida por fluxo, rede residual induzida por fluxo e trajetórias e quasi-trajetórias  de incremento. Exemplos. Descrição genérica do algoritmo de Ford-Fulkerson para cálculo de fluxo máximo numa rede capacitada. Teorema do fluxo-máximo.