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