MO417 - Questão para a prova oral

Número: 098

Enunciado:
Seja G = (V,E) uma rede de fluxo com origem s e sorvedor t, e seja f um fluxo em G. Considere as afirmações abaixo:

1. Se a uma aresta (u,v) ∈ E do grafo está associada uma capacidade c, então a aresta (v,u) ∈ E deve estar associada a uma capacidade −c
2. O vértice s tem um fluxo total líquido maior que zero e o vértice t tem um fluxo total líquido menor que zero.
3. Seja (S,T) um corte de G com s ∈ S e t ∈ T. O fluxo líquido por este corte é igual ao valor do fluxo.
4. Suponha que a aresta (u,v) ∈ E, mas a aresta (v,u) ∉ E. Se f(u,v) = 5, estão f(v,u) = −5 e c(v,u) = 0

1. Apenas as afirmações I e II estão corretas.
2. Apenas as afirmações I e III estão corretas.
3. Apenas as afirmações II e IV estão corretas.
4. Apenas as afirmações III e IV estão corretas.
5. NDA

Autor(a): Thiago Augusto Lopes Genez