MO417 - Questão para a prova oral

Número: 100

Enunciado: Nesta questão, V é o número de vértices e E é o número de arestas de uma rede onde se deseja calcular o fluxo máximo. Sobre o algoritmo de Edmonds-Karp, é incorreto afirmar:

1. Tem uma complexidade de O(E²V)
2. Para encontrar um caminho aumentante utiliza busca em largura
3. Tem um tempo assintótico melhor que o algoritmo de Ford-Fulkerson, se o fluxo máximo é assintoticamente maior que VE
4. É o algoritmo mais rápido conhecido para fluxo máximo.
5. NDA

Autor(a): Rodolfo Ipolito Meneguette