dam2

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um programador dispõe de um código executável capaz de retornar uma árvore espalhada mínima, a partir de um dado grafo conexo e não orientado. Curioso para saber como tal rotina foi implementada, ele resolveu submeter o grafo G abaixo ao procedimento, e observar os diversos  estados assumidos pela memória de seu computador.

Após algum tempo interpretando os dados, ele percebeu que, por algumas vezes, duas árvores disjuntas T'⊂G e T''⊂G, ambas com mais de um nó, estiveram presentes em uma mesma iteração do programa, durante a construção da resposta.

Sobre esta situação, analise as seguintes afirmativas:
I. O algoritmo utilizado pode ser o de Kruskal.

II. O algoritmo utilizado pode ser o de Prim.

III. Considerando o grafo G em particular, para diferenciar o algoritmo de Kruskal do algoritmo de Prim, bastava o programador analisar a árvore espalhada mínima retornada ao final da execução.

Marque a alternativa correta.

a. Todas as afirmativas são corretas.
b. Apenas a afirmativa I é correta.
c. Apenas a afirmativa II é correta.
d. Apenas as afirmativas I e III são corretas.
e. N.D.A. 

Ideia original de: Daniel Henriques Moreira