Árvore geradora mínima

Prévia do material em texto

Árvore geradora mínima 
O que e uma arvore geradora minima (AGM) em um grafo?
a) Uma arvore que contem todos os vertices do grafo e o menor numero possivel de arestas.
b) Uma arvore que contem todos os vertices e arestas de um grafo, mas com o maior custo
possivel.
c) Uma arvore que contem todos os vertices, mas com arestas de custo aleatorio.
d) Uma arvore que conecta todos os vertices com o menor custo total de arestas.
Resposta correta: d) Uma arvore que conecta todos os vertices com o menor custo total de arestas.
Explicacao: A arvore geradora minima e uma arvore que conecta todos os vertices de um grafo com
o menor custo possivel, ou seja, minimizando a soma dos pesos das arestas que a compoem.
Qual e o algoritmo mais conhecido para encontrar uma arvore geradora minima em um grafo
ponderado?
a) Algoritmo de Bellman-Ford.
b) Algoritmo de Dijkstra.
c) Algoritmo de Kruskal.
d) Algoritmo de Floyd-Warshall.
Resposta correta: c) Algoritmo de Kruskal.
Explicacao: O algoritmo de Kruskal e um dos mais utilizados para encontrar a arvore geradora
minima em um grafo ponderado, funcionando de forma eficiente ao ordenar as arestas pelo peso e
unir os vertices de maneira que nao se formem ciclos.
Qual e a principal caracteristica de um grafo em que e possivel aplicar o conceito de arvore
geradora minima?
a) O grafo precisa ser orientado.
b) O grafo deve ser conexo e ponderado.
c) O grafo deve ser completo.
d) O grafo nao pode ter ciclos.
Resposta correta: b) O grafo deve ser conexo e ponderado.
Explicacao: Para que o conceito de arvore geradora minima seja aplicavel, o grafo deve ser conexo
(deve ser possivel alcancar qualquer vertice a partir de qualquer outro) e ponderado (as arestas
precisam ter pesos).
O que caracteriza uma arvore geradora minima de um grafo?
a) Ela contem todos os vertices, mas nao necessariamente todas as arestas.
b) Ela contem todos os vertices e todas as arestas, independentemente do custo.
c) Ela contem todos os vertices e o numero maximo de arestas possiveis.
d) Ela e composta apenas por vertices com peso zero.
Resposta correta: a) Ela contem todos os vertices, mas nao necessariamente todas as arestas.
Explicacao: A arvore geradora minima conecta todos os vertices do grafo, mas o numero de arestas
e o minimo necessario para isso, sem formar ciclos e com o menor custo total.
Em que tipo de problema a arvore geradora minima pode ser aplicada?
a) Problemas de otimizacao de rotas em redes de transporte.
b) Problemas de segmentacao de imagens.
c) Problemas de analise de redes sociais.
d) Problemas de agrupamento de dados em aprendizado de maquina.
Resposta correta: a) Problemas de otimizacao de rotas em redes de transporte.
Explicacao: A arvore geradora minima e amplamente utilizada em problemas de otimizacao de
redes, como no calculo de rotas minimas entre diferentes pontos, que pode ser util em redes de
transporte, telecomunicacoes e outras areas.
O que ocorre se um grafo nao for conexo ao tentar encontrar uma arvore geradora minima?
a) O grafo tera varias arvores geradoras minimas.
b) Nao e possivel encontrar uma arvore geradora minima.
c) O algoritmo de Kruskal sempre encontrara uma solucao.
d) O grafo se torna incompleto e nao e possivel adicionar arestas.
Resposta correta: b) Nao e possivel encontrar uma arvore geradora minima.
Explicacao: Se o grafo nao for conexo, ou seja, se houver vertices isolados sem caminhos entre
eles, nao e possivel formar uma arvore geradora minima, pois nao sera possivel conectar todos os
vertices em uma unica arvore.
O que e o criterio utilizado pelo algoritmo de Kruskal para escolher as arestas da arvore geradora
minima?
a) Escolher as arestas com o maior peso.
b) Escolher as arestas de menor peso que nao formem ciclos.
c) Escolher as arestas de maior peso que formem ciclos.
d) Escolher as arestas aleatoriamente.
Resposta correta: b) Escolher as arestas de menor peso que nao formem ciclos.
Explicacao: O algoritmo de Kruskal escolhe as arestas de menor peso disponiveis e as adiciona a
arvore geradora minima, desde que nao formem ciclos, ate que todos os vertices estejam
conectados.
Qual das seguintes propriedades e verdadeira para uma arvore geradora minima?
a) Ela possui o maior numero possivel de arestas.
b) Ela pode ter ciclos, mas com o menor custo.
c) Ela conecta todos os vertices com o menor custo total de arestas.
d) Ela sempre tera um numero igual de arestas e vertices.
Resposta correta: c) Ela conecta todos os vertices com o menor custo total de arestas.
Explicacao: A arvore geradora minima conecta todos os vertices com o menor custo total possivel
de arestas, sem formar ciclos e sem exceder o numero minimo necessario de arestas.
Como o algoritmo de Prim encontra a arvore geradora minima em um grafo?
a) Comeca a partir de qualquer vertice e vai adicionando arestas de menor peso conectando os
vertices ja visitados aos nao visitados.
b) Ordena todas as arestas pelo peso e adiciona as mais leves.
c) Conecta todos os vertices em um ciclo e depois remove as arestas mais pesadas.
d) Conecta os vertices em ordem crescente de peso.
Resposta correta: a) Comeca a partir de qualquer vertice e vai adicionando arestas de menor peso
conectando os vertices ja visitados aos nao visitados.
Explicacao: O algoritmo de Prim comeca com um vertice qualquer e, a partir dele, vai adicionando
as arestas de menor peso, expandindo a arvore geradora minima ate que todos os vertices estejam
conectados.
O que diferencia o algoritmo de Kruskal do algoritmo de Prim para a construcao de uma arvore
geradora minima?
a) Kruskal comeca com um vertice e vai adicionando arestas, enquanto Prim ordena as arestas
pelo peso.
b) Kruskal utiliza uma abordagem global, enquanto Prim utiliza uma abordagem local.
c) Kruskal e mais eficiente em grafos densos, enquanto Prim e mais eficiente em grafos esparsos.
d) Kruskal requer que o grafo seja orientado, enquanto Prim nao tem essa exigencia.
Resposta correta: b) Kruskal utiliza uma abordagem global, enquanto Prim utiliza uma abordagem
local.
Explicacao: O algoritmo de Kruskal trabalha de forma global, ordenando as arestas do grafo e
escolhendo as de menor peso, enquanto o algoritmo de Prim comeca com um vertice e vai
conectando os vertices proximos de forma local.
O que acontece quando dois vertices ja estao conectados por uma aresta ao tentar adicionar uma
nova aresta na arvore geradora minima?
a) A aresta e adicionada normalmente.
b) A nova aresta e ignorada, pois formaria um ciclo.
c) O algoritmo reinicia a busca por uma arvore geradora minima.
d) O custo da arvore geradora minima e alterado.
Resposta correta: b) A nova aresta e ignorada, pois formaria um ciclo.
Explicacao: Quando duas arestas ja conectam os vertices de um grafo, a adicao de uma nova
aresta formaria um ciclo. Por isso, a aresta e ignorada para garantir que a arvore geradora minima
nao contenha ciclos.
O que define o "custo total" de uma arvore geradora minima?
a) O numero total de vertices no grafo.
b) A soma dos pesos das arestas que a compoem.
c) O numero de arestas presentes na arvore.
d) A diferenca entre o peso da aresta mais leve e a mais pesada.
Resposta correta: b) A soma dos pesos das arestas que a compoem.
Explicacao: O custo total de uma arvore geradora minima e a soma dos pesos de todas as arestas
que formam a arvore, sendo o objetivo minimizar esse custo.
Quais dos seguintes tipos de grafos podem ter uma arvore geradora minima?
a) Apenas grafos nao ponderados.
b) Apenas grafos conexos.
c) Apenas grafos ponderados.
d) Grafos conexos e ponderados.
Resposta correta: d) Grafos conexos e ponderados.
Explicacao: A arvore geradora minima pode ser encontrada em grafos que sao tanto conexos (em
que existe um caminho entre qualquer par de vertices) quanto ponderados (onde as arestas tem
pesos definidos).
O que e uma "floresta" no contexto da arvore geradora minima?
a) Uma arvore geradora minima de um grafo desconexo.
b) Um conjunto dever