MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-108

Enunciado: Considere problemas de fluxo onde arestas possuem uma necessidade mínima de fluxo que deve ser cumprida. Por exemplo, no grafo abaixo, a aresta AB tem capacidade igual a 8 e necessidade mínima igual a 5, o que significa que o fluxo nesta aresta tem de estar entre 5 e 8.

No grafo abaixo, quais podem ser os valores de x e y, representando respectivamente a necessidade mínima e a capacidade da aresta AC, para que exista um fluxo entre a origem S e o destino T?

1. x=1 e y=3
2. x=4 e y=6
3. x=7 e y=9
4. x=10 e y=12
5. NDA

Ideia original de: Lucas Miguel de Carvalho