MO405 - Questão para a prova oral

Número: 116

Enunciado: Dados pesos nos elementos de um matróide M, considere o algoritmo (guloso) A a seguir: partindo do conjunto vazio, adicionar iterativamente o elemento de maior peso cuja adição ao conjunto independente selecionado gera um outro conjunto independente. Sobre o algoritmo A, marque a alternativa CORRETA:

a)  Se M for um matróide cíclico (os circuitos são os ciclos de um grafo), o algoritmo A consiste no algoritmo de Kruskal.

b)   Se M for um matróide cíclico (os circuitos são os ciclos de um grafo), o algoritmo A consiste no algoritmo de Dijkstra.
c)  Se M for um matróide cíclico (os circuitos são os ciclos de um grafo), o algoritmo A consiste no algoritmo de Prim.

d)  Nem sempre A gera um conjunto independente maximal.

e) N.D.A

Ideia original de: Thierry Pinheiro Moreira