lau

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: No grafo abaixo, execute o algoritmo básico de Ford-Fulkerson para resolver o problema do fluxo máximo, onde o nó S é a origem e o nó T é o solvedor.

Supondo que na primeira iteração do algoritmo foi selecionado o caminho aumentante S → V3 → V2 → T e na segunda iteração foi selecionado o caminho aumentante S → V2 → V1 → T, marque a alternativa correta contendo apenas capacidades de fluxo de arestas do grafo residual após a execução das duas primeiras iterações do algoritmo.

1.  c_f(S,V2) = 2,  c_f(V2,S) = 5, c_f(V1,T) = 5, c_f(T,V1) = 10;
2.  c_f(S,V2) = 5,  c_f(V2,S) = 2, c_f(V1,T) = 5, c_f(T,V1) = 10;
3. c_f(V2,T) = 2,  c_f(T,V2) = 8, c_f(V1,T) = 10, c_f(T,V1) = 5;
4. c_f(V2,T) = 8,  c_f(T,V2) = 2, c_f(V1,T) = 5, c_f(T,V1) = 10;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto