MO417 - Questão para a prova oral

Número: 152

Enunciado:
Sobre o problema de Fluxo Máximo, assinale a alternativa INCORRETA:

1. A capacidade residual de uma aresta (u,v) nunca pode ser maior que a sua capacidade total, mesmo considerando a existência de um fluxo negativo nesta aresta.
2. No problema do fluxo máximo desejamos calcular a maior taxa na qual o material pode ser enviado desde a origem até o sorvedor sem violar quaisquer restrições de capacidade.
3. Podemos reduzir o problema de determinar um fluxo máximo em uma rede com várias origens e vários sorvedores a um problema de fluxo máximo comum.
4. O problema de se encontrar um emparelhamento máximo em um grafo bipartido pode ser reduzido a um problema de fluxo máximo.
5. NDA

Autor(a): Renato Hirata