Número: 2013-
Enunciado: Dada a matrix de adjacência
abaixo, que representa uma rede de fluxo, onde está o seu gargalo,
ou seja, quais são as partições S e T que mostra o corte 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(20)
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
a) S = {s, a, b, c} T = {d, e, f, g,
t}; |fluxo máximo| = 27
b) S = {s, a, b} T = {c, d, e, f, g,
t}; |fluxo máximo| = 26
c) S = {s} T = {a, b, c, d, e, f, g,
t}; |fluxo máximo| = 30
d) S = {s, a} T = {b, c, d, e, f, g,
t}; |fluxo máximo| = 25
e) N.D.A.
Ideia original de: Paulo Henrique Hack
de Jesus
Nenhum comentário:
Postar um comentário