Fluxo Máximo

12 Março 2019, 14:30 • Maria Eugénia Captivo

Resolução de alguns exercícios da Folha 3.

Caminho óptimo e Fluxo Máximo

11 Março 2019, 17:30 • Maria Eugénia Captivo

Demonstração da utilização do software para determinar caminhos óptimos entre todos os pares de vértices.

Resolução de alguns exercícios da Folha 2.

Demonstração da utilização do software para determinar o fluxo máximo de s a t numa rede.
Resolução de alguns exercícios da Folha 3.

Problema do fluxo máximo (s a t) numa rede (Conclusão)

11 Março 2019, 16:30 • Maria Eugénia Captivo

Grafos com limites superiores e inferiores no valor do fluxo que atravessa cada arco. Determinação de um fluxo compatível. Exemplos de aplicação. Adaptação do algoritmo de Ford-Fulkerson para determinar o fluxo máximo de s a t neste caso.

Exemplo de aplicação do algoritmo de Ford-Fulkerson partindo de um fluxo inicial admissível dado, para o caso em que existem limites inferiores não nulos.

Identificação da solução óptima do problema dual.

Problema de fluxo de custo mínimo admissível numa rede:
Introdução.
Formulação em PL. Problema dual. Determinação da solução óptima do dual.
Exemplo de aplicação.

Caminhos Óptimos

7 Março 2019, 14:00 • Maria Eugénia Captivo

Demonstração da utilização do software para determinar caminhos óptimos entre todos os pares de vértices.

Resolução de alguns exercícios da Folha 2

Problema do fluxo máximo (s a t) numa rede

7 Março 2019, 13:00 • Maria Eugénia Captivo

Conclusão do exemplo de aplicação do algoritmo de Ford-Fulkerson para determinação do fluxo máximo (s a t) numa rede.
Corte de capacidade mínima separando s de t.
Identificação da solução óptima do problema dual.

Teorema de Ford-Fulkerson. Demonstração.

Exemplo de aplicação do algoritmo de Ford-Fulkerson partindo de um fluxo inicial admissível não nulo.