MO417 - Questão para a prova oral
Número: 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 sorvedor.
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.
- S = { s, v1, v2, v3 }
- S = { s, v1, v2, v4 }
- S = { s, v1, v2, v3, v4 }
- S = { s, v1, v2, v3, v4, v6 }
- NDA
Autor(a): Maikon Cismoski dos Santos