MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-092

Enunciado: Dadas as listas de adjacência abaixo para uma rede de fluxo entre s e t, quantas são as partições S e T que fornecem cortes de menor capacidade e qual o fluxo máximo? Considere o número entre parênteses como a capacidade da aresta que vai de um vértice até o seu adjacente.

s → a(10) → b(15) → f(7)

a → c(5)

b → d(6) → e(15)

c → f(7)

d → f(15)

e → d(9) → g(20)

f → t(10)

g → t(19)

t

1. 1 corte mínimo; |fluxo máximo| = 27
2. 1 corte mínimo; |fluxo máximo| = 25
3. 2 cortes mínimos; |fluxo máximo| =27
4. 3 cortes mínimos; |fluxo máximo| = 25
5. N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus