Algoritmo de Kruskal

Prévia do material em texto

Algoritmo de Kruskal 
O que o Algoritmo de Kruskal busca construir em um grafo?
a) Um ciclo minimo.
b) Um caminho hamiltoniano.
c) Uma arvore geradora minima.
d) Um grafo direcionado aciclico.
Resposta explicativa: O objetivo do Algoritmo de Kruskal e construir uma arvore geradora minima,
ou seja, uma subestrutura que conecta todos os vertices de um grafo com o menor custo possivel,
sem formar ciclos.
Como o Algoritmo de Kruskal escolhe as arestas que farao parte da arvore geradora minima?
a) Escolhe as arestas em ordem crescente de peso.
b) Escolhe aleatoriamente as arestas.
c) Escolhe as arestas em ordem decrescente de peso.
d) Escolhe todas as arestas incidentes em um unico vertice.
Resposta explicativa: O algoritmo seleciona as arestas em ordem crescente de peso e adiciona
cada uma delas a arvore, desde que nao forme um ciclo. Esse processo e repetido ate que todos
os vertices estejam conectados.
Qual estrutura de dados e comumente usada para evitar a formacao de ciclos no Algoritmo de
Kruskal?
a) Fila de prioridade.
b) Uniao e busca (Union-Find).
c) Lista de adjacencia.
d) Pilha recursiva.
Resposta explicativa: A estrutura de dados Union-Find (ou Disjoint Set Union) e utilizada para
verificar se dois vertices pertencem ao mesmo conjunto. Se pertencem, a aresta e descartada para
evitar ciclos.
O Algoritmo de Kruskal pode ser aplicado em grafos com arestas negativas?
a) Sim, desde que o grafo seja nao direcionado.
b) Nao, pois ele falha com pesos negativos.
c) Apenas se o grafo for direcionado.
d) Apenas se todos os pesos forem positivos.
Resposta explicativa: O algoritmo funciona corretamente mesmo com arestas negativas, contanto
que o grafo seja nao direcionado, pois ele apenas ordena as arestas por peso e evita ciclos, sem
depender da soma total de pesos ser positiva.
Em relacao a complexidade de tempo, qual e o custo aproximado do Algoritmo de Kruskal?
a) O(V2)
b) O(E log E)
c) O(V log V)
d) O(E2)
Resposta explicativa: A complexidade do Algoritmo de Kruskal e O(E log E), onde E e o numero de
arestas. Isso ocorre porque as arestas precisam ser ordenadas antes do processo de selecao.
Qual das seguintes opcoes descreve melhor o funcionamento geral do Algoritmo de Kruskal?
a) Ele adiciona vertices a arvore ate que todas as arestas sejam visitadas.
b) Ele adiciona arestas de menor peso que nao causem ciclos ate conectar todos os vertices.
c) Ele busca o caminho mais curto entre dois vertices especificos.
d) Ele cria uma matriz de custos minimos.
Resposta explicativa: O algoritmo seleciona arestas de menor peso que conectem componentes
distintos, evitando ciclos, ate que todos os vertices estejam conectados em uma unica estrutura.
O que acontece se o grafo for desconexo ao aplicar o Algoritmo de Kruskal?
a) Ele entra em loop infinito.
b) Ele gera uma floresta geradora minima.
c) Ele retorna erro e interrompe o processo.
d) Ele conecta os componentes automaticamente.
Resposta explicativa: Se o grafo for desconexo, o algoritmo nao consegue formar uma unica arvore
geradora, mas sim uma floresta geradora minima um conjunto de arvores geradoras, uma para
cada componente.
Qual e a diferenca principal entre os algoritmos de Kruskal e Prim?
a) O de Kruskal trabalha com vertices, enquanto o de Prim trabalha com arestas.
b) O de Kruskal constroi a arvore de forma global, enquanto o de Prim cresce a partir de um vertice
inicial.
c) O de Kruskal e sempre mais rapido.
d) O de Prim nao pode lidar com grafos nao direcionados.
Resposta explicativa: Kruskal adiciona arestas ordenadas globalmente, sem precisar de um vertice
inicial, enquanto Prim parte de um vertice e expande a arvore a cada passo. Essa e a principal
diferenca conceitual entre os dois.
Em que tipo de grafo o Algoritmo de Kruskal costuma ser mais eficiente?
a) Grafos densos.
b) Grafos direcionados.
c) Grafos esparsos.
d) Grafos completos.
Resposta explicativa: O Kruskal e especialmente eficiente em grafos esparsos, onde ha
relativamente poucas arestas em relacao ao numero de vertices, pois o custo de ordenacao das
arestas e menor.
O que caracteriza uma arvore geradora minima?
a) Uma arvore que possui o maior numero de arestas possivel.
b) Uma estrutura que conecta todos os vertices com o menor custo total e sem ciclos.
c) Uma arvore com o maior custo entre as possiveis.
d) Um subgrafo com ciclos permitidos.
Resposta explicativa: A arvore geradora minima e aquela que conecta todos os vertices de um
grafo com o menor custo total de arestas, sem formar ciclos.
Durante a execucao do Algoritmo de Kruskal, o que acontece quando uma aresta conecta dois
vertices que ja estao no mesmo conjunto?
a) Ela e adicionada normalmente.
b) Ela e descartada para evitar ciclo.
c) Ela e priorizada.
d) O algoritmo reinicia o processo.
Resposta explicativa: Quando uma aresta conecta vertices que ja pertencem ao mesmo conjunto,
ela e descartada, pois incluir essa aresta criaria um ciclo, o que violaria as condicoes da arvore
geradora minima.
O Algoritmo de Kruskal e considerado guloso. O que isso significa nesse contexto?
a) Ele escolhe sempre a solucao otima global de imediato.
b) Ele toma decisoes locais que parecem melhores naquele momento.
c) Ele escolhe aleatoriamente as solucoes intermediarias.
d) Ele avalia todas as combinacoes possiveis antes de decidir.
Resposta explicativa: Ser guloso significa que o algoritmo toma decisoes locais escolhe a melhor
aresta disponivel a cada passo acreditando que essas escolhas levarao a solucao otima global, o
que de fato acontece nesse caso.
Qual e a condicao de parada do Algoritmo de Kruskal?
a) Quando todas as arestas forem testadas.
b) Quando o numero de arestas adicionadas for igual a V - 1, onde V e o numero de vertices.
c) Quando todos os vertices tiverem grau igual a 2.
d) Quando nao houver mais ciclos possiveis.
Resposta explicativa: O algoritmo termina quando a arvore contem exatamente V - 1 arestas, pois
essa e a quantidade necessaria para conectar todos os vertices sem formar ciclos.
Quem foi Joseph Kruskal, o criador do algoritmo?
a) Um fisico teorico.
b) Um matematico e estatistico norte-americano.
c) Um engenheiro de redes.
d) Um programador russo.
Resposta explicativa: Joseph Kruskal foi um matematico e estatistico americano que desenvolveu o
algoritmo em 1956, contribuindo significativamente para a teoria dos grafos e a otimizacao.
Qual das seguintes aplicacoes praticas pode utilizar o Algoritmo de Kruskal?
a) Roteamento de cabos em redes eletricas ou de comunicacao.
b) Compressao de dados binarios.
c) Criptografia assimetrica.
d) Simulacao de sistemas fisicos.
Resposta explicativa: O Algoritmo de Kruskal e amplamente aplicado em problemas de otimizacao
de redes, como o planejamento de rotas, redes de energia ou fibra optica, onde o objetivo e
minimizar o custo total de conexao.