MO417 - Questão para a prova oral

Número: 2009-158

Enunciado: Sobre o algoritmo de Edmonds-Karp para fluxos máximos em redes de fluxo, é INCORRETO afirmar que:

1. É idêntico ao algoritmo básico de Ford-Fulkerson, exceto pela forma como encontra os caminhos aumentantes;
2. Ao contrário do algoritmo básico de Ford-Fulkerson, não pode ser usado para emparelhamentos bipartidos máximos;
3. Ele sempre seleciona o próximo caminho aumentante dentre os caminhos que possuem capacidade residual e número mínimo de arestas;
4. Sua complexidade para grafos densos é O(V⁵)
5. NDA

Ideia original de: Fernando José Vieira da Silva