Problemas de fluxo em redes

17 Novembro 2021, 18:00 • Ana Maria Duarte Silva Alves Paias

Determinação do fluxo máximo entre dois vertices)

Noção de caminho de aumento,  caminho saturado e de fluxo saturante,

Teorema de Ford-Fulkerson. Condição de otimalidade. 

Algoritmo de Ford-Fulkerson e suas limitações. Algoritmo de Malhotra et al.

Grafos com várias origens e destinos.

Grafos com capacidades nos arcos e nos vértices

Grafos com limites inferiores e superiores no fluxo que passa em cada arco: determinação de um fluxo admissível. Adaptação dos algoritmos Ford-Fulkerson e Malhotra et al.

Emparelhamento de cardinalidade máxima: definição e transformação num problema de determinação do fluxo máximo entre dois vértices.