Construa o grafo gerado pela tabela de pontos abaixo, e aplique o algoritmo de Prim para encontrar a menor árvore geradora. Faça uma conclusão sobre os resultados obtidos. Dica: Ler sobre a função ‘minspantree’ (e suas entradas) no help do MATLAB.
XY_Points = [
10 25
10 42
20 6
30 11
40 33
22 18
26 25
];

Passo 1

O enunciado nos dá sete pontos no plano cujas coordenadas são
V_1=(10,25),\;V_2=(10,42),\;V_3=(20,6),\;V_4=(30,11),\;V_5=(40,33),\;V_6=(22,18),\;V_7=(26,25)
e pede que a gente construa o grafo completo em que cada aresta tem peso igual à distância euclidiana entre os vértices, e daí aplique o algoritmo de Prim para obter a árvore geradora mínima (MST). Vamos usar a fórmula da distância
d(V_i,V_j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}
e depois rodar Prim “na mão” (o MATLAB faz isso com minspantree(G)).

Passo 2

Calculemos as distâncias relevantes (arredondadas a duas casas):
\begin{aligned} d(V_1,V_6)&=\sqrt{(10-22)^2+(25-18)^2}=\sqrt{193}\approx13{,}89,\\\ d(V_6,V_7)&=\sqrt{(22-26)^2+(18-25)^2}=\sqrt{65}\approx8{,}06,\\\ d(V_4,V_6)&=\sqrt{(30-22)^2+(11-18)^2}=\sqrt{113}\approx10{,}63,\\\ d(V_3,V_4)&=\sqrt{(20-30)^2+(6-11)^2}=\sqrt{125}\approx11{,}18,\\\ d(V_5,V_7)&=\sqrt{(40-26)^2+(33-25)^2}=\sqrt{260}\approx16{,}12,\\\ d(V_1,V_2)&=\sqrt{(10-10)^2+(25-42)^2}=17{,}00. \end{aligned}
Essas serão justamente as arestas que entrarão em nossa MST.

Passo 3

Aplicando o algoritmo de Prim começando em V_1:
  1. Conjunto inicial T=\{V_1\}. A menor aresta que sai de V_1 é para V_6 com peso 13{,}89.
    Adicionamos aresta (V_1,V_6).
  2. Agora T=\{V_1,V_6\}. As distâncias mínimas de T para o resto são:
  • a V_7 via V_6 com peso 8{,}06,
  • a V_4 via V_6 com peso 10{,}63,
  • etc.
    A menor é 8{,}06, então adicionamos (V_6,V_7).
  1. T=\{V_1,V_6,V_7\}. Agora o mais barato fora de T é a aresta (V_6,V_4) com 10{,}63.
  2. T=\{V_1,V_6,V_7,V_4\}. A próxima aresta mínima é (V_4,V_3) com 11{,}18.
  3. T=\{V_1,V_6,V_7,V_4,V_3\}. Entre os remanescentes, sai (V_7,V_5) com 16{,}12.
  4. Finalmente só falta V_2, que se liga via (V_1,V_2) com 17{,}00.

Passo 4

A árvore geradora mínima encontrada tem as arestas
(V_1,V_6),\;(V_6,V_7),\;(V_6,V_4),\;(V_4,V_3),\;(V_7,V_5),\;(V_1,V_2).

Passo 5

Somando os pesos:
13{,}89 + 8{,}06 + 10{,}63 + 11{,}18 + 16{,}12 + 17{,}00 \approx 76{,}88.
No MATLAB, basta criar o grafo com G = graph(sparse(distMatrix)) e depois T = minspantree(G) — o T traz exatamente essas arestas e esse peso total.

Resposta

As arestas da MST são (V_1,V_6), (V_6,V_7), (V_6,V_4), (V_4,V_3), (V_7,V_5), (V_1,V_2)
com peso total aproximado de 76{,}88.

Exercícios relacionados