MO417 - Questão para a prova oral

Número: 2009-116

Enunciado: O algoritmo de Prim é um eficiente algoritmo guloso utilizado para resolver o problema de árvore espalhada mínima. Dado um grafo como entrada, o algoritmo seleciona, a cada etapa, uma aresta e adiciona-a à árvore, até que as arestas selecionadas formem uma árvore espalhada mínima. A forma como este algoritmo realiza esta seleção de arestas é decisivo para garantir a sua eficiência. O grafo abaixo apresenta seis arestas com seus pesos correspondentes (1, 2, 3, 4, 5 e 6). Aplicando algoritmo de Prim neste grafo, qual das alternativas abaixo corresponde a uma possível sequência que descreva a ordem correta em que as arestas foram selecionadas? (as arestas foram identificadas com os valores de seus pesos.)

1. 1, 2, 3, 4
2. 1, 2, 3, 5
3. 2, 1, 5, 3
4. 6, 1, 2, 5
5. NDA

Ideia original de: Paulo Gurgel Pinheiro