Árvore geradora mínima

Prévia do material em texto

Árvore geradora mínima 
1. Em um grafo ponderado e conexo, o que representa uma arvore geradora minima (AGM)?
a) Um subgrafo que contem todos os vertices e tem o menor numero de arestas possivel.
b) Um subgrafo que contem todos os vertices e cuja soma dos pesos das arestas e minima.
c) Um grafo completo com pesos iguais.
d) Um grafo direcionado sem ciclos.
Resposta explicativa: A alternativa correta e b. A arvore geradora minima e uma arvore que conecta
todos os vertices de um grafo com o menor custo total possivel, considerando os pesos das
arestas.
2. Qual dos seguintes algoritmos e tradicionalmente usado para encontrar uma arvore geradora
minima?
a) Dijkstra
b) Bellman-Ford
c) Kruskal
d) Floyd-Warshall
Resposta explicativa: A resposta e c. O algoritmo de Kruskal e amplamente usado para encontrar a
AGM, pois adiciona arestas em ordem crescente de peso, garantindo que nao haja ciclos.
3. No algoritmo de Prim, qual e a principal estrategia utilizada para construir a arvore geradora
minima?
a) Escolher arestas aleatorias e eliminar ciclos.
b) Adicionar vertices ao conjunto ja conectado, sempre escolhendo a aresta de menor peso que o
conecta a um novo vertice.
c) Remover as arestas mais pesadas ate restar apenas uma arvore.
d) Dividir o grafo em subgrafos menores e conectar cada um individualmente.
Resposta explicativa: Correta e b. O algoritmo de Prim expande a arvore a partir de um vertice
inicial, conectando-a a novos vertices por meio da menor aresta possivel.
4. Em um grafo com
n vertices, quantas arestas tera uma arvore geradora minima?
a)
n
b)
n1
c)
n+1
d) Depende do numero de componentes conexas
Resposta explicativa: A alternativa correta e b. Toda arvore com
n vertices possui exatamente
n1 arestas, caracteristica que tambem vale para a AGM.
5. O que acontece se um grafo nao for conexo ao tentarmos encontrar uma arvore geradora
minima?
a) Nao existe AGM, pois nem todos os vertices podem ser conectados.
b) O algoritmo retorna varias arvores geradoras distintas.
c) O algoritmo cria ciclos para unir os componentes.
d) E possivel encontrar uma AGM, mas com arestas duplicadas.
Resposta explicativa: Correta e a. Uma AGM so existe em grafos conexos; caso contrario, teriamos
uma floresta geradora minima.
6. Qual a diferenca principal entre os algoritmos de Kruskal e Prim?
a) Kruskal usa listas de adjacencia, enquanto Prim usa matriz de adjacencia.
b) Kruskal adiciona arestas por peso, enquanto Prim adiciona vertices por proximidade.
c) Kruskal e exclusivo para grafos direcionados.
d) Prim nao garante uma arvore minima.
Resposta explicativa: A resposta e b. Kruskal trabalha ordenando e adicionando arestas, enquanto
Prim expande uma arvore a partir de um vertice inicial.
7. Se todas as arestas de um grafo tiverem o mesmo peso, qual sera o resultado da arvore
geradora minima?
a) Havera varias AGMs possiveis com o mesmo custo total.
b) A AGM sera unica.
c) Nao havera AGM.
d) O algoritmo de Kruskal falhara.
Resposta explicativa: Correta e a. Se os pesos forem iguais, qualquer arvore geradora possivel tera
o mesmo custo, logo existem varias AGMs equivalentes.
8. O que significa dizer que a arvore geradora minima e um subgrafo aciclico?
a) Que ela nao contem ciclos e ainda conecta todos os vertices.
b) Que possui apenas um ciclo minimo.
c) Que as arestas podem se repetir.
d) Que ha vertices desconectados.
Resposta explicativa: A resposta e a. A AGM e uma arvore, e por definicao, arvores sao subgrafos
aciclicos e conexos.
9. Qual e a complexidade de tempo do algoritmo de Kruskal quando se usa a estrutura de dados
Union-Find?
a)
O(E
2
)
b)
O(V
2
)
c)
O(ElogV)
d)
O(V+E)
Resposta explicativa: Correta e c. O uso de Union-Find otimiza a deteccao de ciclos, tornando o
algoritmo eficiente para grafos grandes.
10. Qual das opcoes descreve corretamente o conceito de corte em um grafo, usado em algoritmos
de AGM?
a) Uma particao dos vertices em dois conjuntos disjuntos.
b) Um caminho mais curto entre dois vertices.
c) Um ciclo minimo do grafo.
d) A remocao de todas as arestas de peso maximo.
Resposta explicativa: A alternativa correta e a. Um corte divide o conjunto de vertices em duas
partes e ajuda a determinar quais arestas podem pertencer a AGM.
11. Em que situacao o algoritmo de Kruskal pode ser preferido em relacao ao de Prim?
a) Quando o grafo e denso.
b) Quando o grafo e esparso.
c) Quando todos os pesos sao iguais.
d) Quando o grafo e direcionado.
Resposta explicativa: A resposta e b. Kruskal e mais eficiente em grafos esparsos, pois trabalha
diretamente com as arestas ordenadas.
12. Ao utilizar o algoritmo de Prim, qual estrutura de dados geralmente melhora o desempenho?
a) Lista simples
b) Pilha
c) Fila de prioridade (heap)
d) Matriz de transicao
Resposta explicativa: Correta e c. A fila de prioridade permite selecionar rapidamente a aresta de
menor peso que conecta a arvore parcial a um novo vertice.
13. Se adicionarmos uma aresta de peso negativo a um grafo, isso afetara a AGM?
a) Sim, pois a AGM buscara incluir a aresta de menor peso, mesmo que negativo.
b) Nao, pois pesos negativos sao ignorados.
c) Depende do algoritmo utilizado.
d) Sim, mas apenas se houver ciclos.
Resposta explicativa: Correta e a. A AGM busca minimizar o custo total; portanto, uma aresta
negativa sera incluida se nao formar ciclo e reduzir o custo.
14. Em um grafo com multiplas arestas entre os mesmos vertices, o que os algoritmos de AGM
fazem?
a) Escolhem sempre a primeira aresta encontrada.
b) Consideram apenas a de menor peso.
c) Ignoram todas as arestas duplicadas.
d) Somam os pesos.
Resposta explicativa: A alternativa correta e b. Os algoritmos de AGM, como Kruskal e Prim,
avaliam o menor peso entre arestas multiplas para otimizar o resultado.