2024-144

Sobre o Algoritmo Húngaro, rodando num grafo de $n$ vértices, podemos dizer que:

a) Dado um grafo qualquer, o algoritmo acha um emparelhamento de peso máximo com tempo de execução $O(n^2)$

b) Dado um grafo bipartido qualquer, o algoritmo acha um emparelhamento de peso mínimo com tempo de execução $O(n^3)$

c) Dado um grafo bipartido qualquer, o algoritmo acha um emparelhamento de peso máximo com tempo de execução $O(n^2)$

d) Dado um grafo qualquer, o algoritmo acha um emparelhamento de peso mínimo com tempo de execução $O(n^3)$

e) N.D.A

Ideia original de: Wellington T. A. da Silva