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