jor

MO417 - Questão para a prova oral

Número:

Enunciado: As afirmações abaixo descrevem a importância dos conceitos em fluxo maximal (maximum flow). Qual delas está incorreta?

a. Redes residuais (residual networks) são a estrutura usada para encontrar caminhos incrementantes (augmenting paths).
b. Caminhos incrementantes (augmenting paths) descrevem como aumentar o fluxo atual no grafo e a sua ausência indica que encontramos o fluxo maximal.
c. Cortes (cuts) descrevem o movito pelo qual a ausência de caminhos incrementantes implicam que encontramos o fluxo maximal.
d. Arestas antiparalelas (antiparallel edges), superfonte (supersource) e supersorvedouro (supersink) são formas de adaptar um grafo direcionado para que seja possível obter uma rede residual (residual network) a partir dele.
e. NDA

Idéia original de: Jorge Augusto Hongo