fab

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Considere as seguintes afirmações relativas ao problema de encontrar uma árvore geradora mínima (AGM) de um grafo G = (V, E):

I. Supondo que o peso das arestas são inteiros de 1 a |V| é possível usar Counting Sort com o algoritmo de Kruskal para obter uma AGM em O(Eα(V)).

II. Quando |E| = Ω(V lg V), o algorítimo de Prim, implementado usando heap de Fibonacci, obtem uma AGM em O(E).

III. Não existe algorítimo que encontre uma AGM em tempo linear.

A) Todas são verdadeiras.
B) Apenas I é verdadeira.
C) Somente I e II são verdadeiras.
D) Somente I e III são verdadeiras.
E) NDA

Ideia original de: Fabrício Matheus Gonçalves