MO417 - Questão para a prova oral

Número: 2003-162

Enunciado: Uma rede de fluxo pode modelar diversos problemas encontrados na vida real, às vezes com algumas adaptações. Suponha que desejamos modelar o seguinte problema. Uma fábrica (origem) produz pães e deve transportá-los para um distribuidor (destino). No entanto, a capacidade de produção da fábrica é limitada e pode ser inferior ao fluxo de valor máximo proporcionado pela rede de transporte.
Dado um grafo G=(V,E) representando a rede de transporte entre a fábrica (s) e o distribuidor (t), como podemos modificar G, resultando numa nova rede G', de modo o fluxo de valor máximo em G' não ultrapasse a limitação p de produção da fábrica?


A) Acrescenta-se uma aresta (s,t) com capacidade c(s,t) = p.
B) Para todas as arestas (i,j) de G tais que c(i,j) > p, modifica-se c(i,j) = p em G'.
C) Cria-se um novo vétice s' que será a nova origem e uma aresta (s',s) com capacidade c(s',s) = p.
D) Para qualquer aresta (s, i), define-se c(s,i) = p em G'.
E) NDA

Ideia original de: André Santanchè