MO417 - Questão para a prova oral

Número: 2009-155

Enunciado: Abaixo é apresentada uma rede de fluxo G = (V,E) com suas respectivas capacidades e fluxos nas arestas, fazendo uso da notação "fluxo/capacidade", ou apenas "capacidade" quando não há fluxo. Faz-se, então, um corte ({s, v3, v4}, {v1, v2, t}) na rede de fluxo dada. O fluxo através do corte e sua capacidade são, respectivamente:

1. 23 e 31
2. 23 e 50
3. 31 e 31
4. 31 e 50
5. NDA

Ideia original de: Jonathas Campi Costa