Número:
Enunciado: Seja um grafo não orientado G=(V,E), com uma função de peso w: E -> R. Sobre a construção da árvore geradora mínima de G é correto afirmar:
a) No algoritmo de Kruskal, o conjunto inicial para a construção de uma árvore geradora mínima é uma árvore única.
b) No algoritmo de Prim, a aresta segura a ser adicionada à árvore geradora mínima em formação é sempre uma aresta de peso mínimo no grafo que conecta dois componentes distintos.
c) Para certas conformações de G, pode-se construir um algoritmo que crie uma árvore geradora mínima permitindo a ligação de dois vértices que pertencem à mesma árvore.
d) Para evitar ciclos na árvore geradora mínima, o algoritmo de Kruskal pode fazer uso de uma estrutura de conjuntos disjuntos.
e) N.D.A
Ideia original de: Danielle Furtado dos Santos Dias
Nenhum comentário:
Postar um comentário