Questão para a prova oral 162
Enunciado:
Um fluxo em rede pode modelar diversos problemas encontrados na vida
real. Entre eles podemos imaginar o fluxo de água que sai de uma barragem,
trafega por tubulações e atinge um consumidor x. Neste
caso, o enfoque do problema está relacionado com o fluxo de água
que passa pela tubulação, portanto, podemos assumir - para
fins de simplificação - que a barragem será capaz de
fornecer tanta água quanto for exigida pelo fluxo de saída
da mesma. A limitação ao fluxo será estabelecida pela
capacidade da rede de tubulação.
Por outro lado, suponha que desejamos modelar um problema, na forma de um
fluxo em rede, onde uma fábrica produz pães (origem)
e deve transportá-los para um distribuidor (depósito). No entanto,
a capacidade de produção da fábrica é limitada
e pode ser inferior ao fluxo de valor máximo proporcionado
pela capacidade da rede de transporte.
Dado um grafo G=(V,E) representando um fluxo em rede entre a fábrica
(s) e o distribuidor (t). Como podemos modificar o grafo G (resultando em
G'), de modo que seja possível calcular o fluxo de valor máximo
que não ultrapasse a limitação p de produção
da fábrica, utilizando algoritmos que desconsideram tais limitações
de produção?
A) Acrescenta-se uma aresta (s,t) cujo c(s,t) = p.
B) Para todas as arestas (i,j) de G cujo c(i,j) > p; modifica-se para c(i,j) = p em G'.
C) Cria-se um novo vétice s' que será a nova origem e uma aresta (s',s) cujo c(s',s) = p.
D) Para qualquer aresta (s, i), define-se c(s,i) = p em G'.
E) NDA
Autor(a): André Santanchè
RA: 022287