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
];
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
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
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):
Essas serão justamente as arestas que entrarão em nossa MST.
Passo 3
Aplicando o algoritmo de Prim começando em
:
- Conjunto inicial
. A menor aresta que sai de é para com peso .
Adicionamos aresta. - Agora
. As distâncias mínimas de para o resto são:
- a
via com peso , - a
via com peso , - etc.
A menor é, então adicionamos .
-
. Agora o mais barato fora de é a aresta com . -
. A próxima aresta mínima é com . -
. Entre os remanescentes, sai com . - Finalmente só falta
, que se liga via com .
Passo 4
A árvore geradora mínima encontrada tem as arestas
Passo 5
Somando os pesos:
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
,
,
,
,
,
com peso total aproximado de .
com peso total aproximado de