MO417 - Questão para a prova oral

Número: 161

Enunciado:
Numa rede de fluxo G = (V,E), em que s é a origem e t é o sorvedor, um corte (S,T)
é uma partição de V em dois conjuntos, S e T = V-S, de tal forma que s ∈ S e
t ∈ T.
A respeito de cortes em uma rede de fluxo, foram dadas as seguintes afirmações:

I) Um corte mínimo de uma rede de fluxo é um corte cujo fluxo é mínimo dentre
todos os cortes da rede.
II) O c´lculo do fluxo líquido por um corte não pode incluir fluxos negativos entre vértices.
III) A capacidade de um corte (S,T) é calculada somente a partir de arestas que
vão de S para T.

Com base nessas afirmações, escolha a opção correta:

1. Apenas I é verdadeira.
2. Apenas I e II são verdadeiras.
3. Apenas II e III são verdadeiras.
4. Apenas III é verdadeira.
5. NDA

Autor(a): Fábio de Souza Azevedo