[Enunciado do exercício.]
Várias respostas erradas:
O algoritmo de Karger …
sorteia uma aresta do grafo, junta as duas pontas da aresta, e continua fazendo isso recursivamente até que sobrem só dois vértices.
calcula o corte mínimo de um grafo.
devolve um corte aleatório de um grafo.
calcula probabilisticamente o corte mínimo de um grafo.
devolve o corte mínimo de um grafo com probabilidade ≥ 2/n².