Uma árvore geradora é uma árvore que conecta todos os vértices de um grafo. Uma árvore geradora mínima é uma árvore que conecta todos os vértices e...

Uma árvore geradora é uma árvore que conecta todos os vértices de um grafo. Uma árvore geradora mínima é uma árvore que conecta todos os vértices em um gráfico com peso cujo peso total é mínimo. Um dos algoritmos para obter este tipo de árvore teve o objetivo de minimizar o custo de instalação de fiações para energia elétrica no final dos anos 1920. Considere a matriz de adjacências a seguir. Fonte: Takenaka (2021). Execute o algoritmo de Prim e selecione a alternativa que apresenta o resultado do algoritmo.


a) A (A,0), B (A,1), C (B,3), D (C,6), E (A,8).
{X,A,2}, {D,C,2}, {B,C,4}, {D,F,4}, {B,X,5}, {C,E,5}, {G,D,6}, {H,G,7}, 35.
A (A, 0), B (A, 6), A (X, 2), C (B, 4), D (C, 2), E (X, 9), F (E,14), G (H, 14), A (H, 7).
{H,G,7}, {G,D,6}, {D,F,4}, {D,C,2}, {C,E,5}, {C,B,4}, {B,X,5}, {X,A,2}. 35.
{A, X}, {X, B}, {B, C}, {C, E}, {E, F}, {F, D}, {D, G}, {G, H}