Questão 769210

• Banca: CESPE / CEBRASPE
• Órgão: Banco da Amazônia
• Ano: 2012
• Provas: CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Grafos

Uma árvore de espalhamento de um grafo ponderado conectado é mínima se a soma dos pesos de todas as arestas for mínima.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• Uma árvore de espalhamento de um grafo é uma árvore que contém todos os vértices de um grafo. O item é a definição de uma árvore de espalhamento mínima, "é mínima se a soma dos pesos de todas as arestas for mínima". Veja que é importante o fato de o grafo ser conectado (ou conexo). Se ele fosse desconexo, é impossível haver UMA árvore de espalhamento.

• A árvore de espalhamento é gerado por um algoritmo guloso que pega as arestas com os menores valores, desde que eles não gerem um ciclo.
  

• Força Guerreiro!!!!!!