MO417 - Questão para a prova oral
Número: 152
Enunciado:
Sobre o problema de Fluxo Máximo, assinale a alternativa INCORRETA:
- 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.
- 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.
- 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.
- O problema de se encontrar um emparelhamento máximo em um grafo bipartido pode ser reduzido a um problema de fluxo máximo.
- NDA
Autor(a): Renato Hirata