MO417 - QUESTÃO PARA PROVA ORAL

Número: 2013-091

Enunciado: Na rede abaixo, considere o problema do fluxo máximo, onde o nó S é a origem e o nó T é o sorvedouro.  Partindo do fluxo nulo, suponha que foi empurrada a maior quantidade possível de fluxo ao longo do caminho aumentante S → V3 → V2 → T e, logo após, também foi enviado o máximo fluxo possível ao longo do caminho aumentante S → V2 → V1 → T.

Marque a alternativa correta contendo capacidades de arestas no grafo residual neste momento.

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

Ideia original de: Laurindo de Sousa Britto Neto