Questão FC406579
Considere uma árvore que contém todo e qualquer nó em um grafo, mais formalmente, uma spanning tree de um grafo G = (N, E) e um grafo G' = (N, E') tal que E' é um subconjunto de E,
Gerenciamento de Redes
FGV · 2024
Considere uma árvore que contém todo e qualquer nó em um grafo, mais formalmente, uma spanning tree de um grafo G = (N, E) e um grafo G' = (N, E') tal que E' é um subconjunto de E, G' é conectado, G' não contém nenhum ciclo e G' contém todos os nós originais em G.
Se cada enlace tiver um custo associado e o custo de uma árvore for a soma dos custos dos enlaces, é correto afirmar que uma árvore cujo custo seja o mínimo entre todas as spanning trees é denominada:
- spanning tree mínima;
- spanning tree máxima;
- spanning tree de diâmetro mínimo;
- spanning tree de diâmetro máximo;
- spanning tree geradora de caminho máximo.
Mostrar resposta e comentário
Gabarito
A
Comentário do professor
Spanning tree mínima é a árvore geradora de um grafo que tem o menor custo possível entre todas as spanning trees do grafo. Ou seja, é uma árvore que conecta todos os nós, sem ciclos, e cuja soma dos custos das arestas é mínima.
Formalmente, se \(w(e)\) é o peso de uma aresta e \(T\) é uma árvore geradora, o custo de \(T\) é \(C(T)=\sum_{e\in T} w(e)\). A spanning tree mínima \(T^*\) satisfaz \(C(T^*)=\min_{T\in\mathcal{T}} C(T)\), onde \(\mathcal{T}\) é o conjunto de todas as árvores geradoras.
Essa árvore pode não ser única quando existem arestas com pesos iguais; contudo, qualquer spanning tree mínima atende às exigências de conectividade e ausência de ciclos while minimizando \(C(T)\).
Algoritmos clássicos para obtê‑la são Kruskal e Prim, ambos baseados em abordagem gulosa e eficientes na prática.
Conteúdo do catálogo FC Concursos · Atualizado em