Questão de Tecnologia da Informação · FGV CVM 2024 (nº 41)

Uma árvore geradora (spanning tree) é um subconjunto das conexões (enlaces) de uma rede (grafo) que liga todos os dispositivos (nós) sem criar nenhum caminho redundante (ciclo). Se cada conexão tem um "custo" (por exemplo, tempo ou dinheiro), uma árvore geradora mínima (Minimum Spanning Tree - MST) é aquela que conecta todos os dispositivos com o menor custo total possível.

(A) Correta: Esta é a definição exata de uma árvore geradora mínima (Minimum Spanning Tree - MST). O objetivo é encontrar a árvore geradora que tenha a menor soma dos custos de seus enlaces.
(B) Incorreta: Uma "spanning tree máxima" seria aquela com o maior custo total, o que é o oposto do que a questão descreve.
(C) Incorreta: O "diâmetro" de uma árvore é o caminho mais longo entre quaisquer dois nós. Minimizar o diâmetro é um problema diferente de minimizar o custo total da árvore. A armadilha aqui é o uso da palavra "mínimo", que pode confundir o aluno, mas se refere a uma métrica diferente (diâmetro, não custo total).
(D) Incorreta: Maximizar o diâmetro é outro problema diferente, não relacionado ao custo total da árvore.
(E) Incorreta: "Caminho máximo" geralmente se refere ao caminho mais longo entre dois nós específicos, ou o caminho mais longo em termos de número de arestas ou peso. Não é uma propriedade que define uma árvore geradora com base no custo total.