MO417 - Questão para a prova oral

Número: 2010-102

Enunciado: No problema de fluxo máximo, considere um fluxo de rede G = (V, E) sendo o grafo orientado ilustrado abaixo, em que cada aresta (u,v) ∈ E tem uma capacidade não negativa c(u,v) ≥ 0. O vértice s é a origem e o vértice t é o sorvedouro.



Um corte (S,T) de fluxo de rede G = (V, E) é uma partição de V em S e T = V - S tal que s ∈ S e t ∈ T. Um corte mínimo de uma rede é um corte cuja capacidade é mínima dentre todos os cortes da rede. Qual das alternativas abaixo representa um corte mínimo em G? Em cada caso, defina T = V - S.

1. S = { s, v1, v2, v3 }
2. S = { s, v1, v2, v4 }
3. S = { s, v1, v2, v3, v4 }
4. S = { s, v1, v2, v3, v4, v6 }
5. NDA

Ideia original de: Maikon Cismoski dos Santos