Atividade 3 Grafos

Prévia do material em texto

INTRODUÇÃO A TEORIA DOS GRAFOS: atividade 3
Para encontrar o caminho de menor custo, devemos analisar os valores entregues para a 
tabela abaixo:
Tendo em mente que o ponto inicial é o vértice AAA, devemos percorrer a linha 
pertencente ao ponto inicial e nela encontrar o menor custo de locomoção. Analisando a 
primeira linha, temos que o menor valor a ser percorrido é 20, tanto para o vértice BBB 
quanto para o vértice CCC (Linha 1, coluna 2 e 3). Observando com amplitude para a tabela, 
ao escolher o vértice BBB teríamos que percorrer sua coluna, tendo o valor 27 (Linha 3, 
coluna 2) como menor custo, custo esse de locomoção até o vértice CCC. Por outro lado, ao 
escolher o valor 20 referente ao custo de locomoção entre o vértice AAA e o vértice CCC, 
teríamos na coluna de CCC que o menor custo de locomoção seria 21 para FFF (Linha 6, 
coluna 3), nosso objetivo principal.
Seguindo a explicação acima, temos então que:
Tendo o ponto de partida em AAA, o menor custo escolhido está em CCC (20);
Após chegar em CCC, o menor custo está em FFF (21);
Com isso, podemos concluir que a rota utilizada foi AAA -> CCC -> FFF conforme 
demonstrado no grafo abaixo, gerando os seguintes custos: 20+21 = 41. Pode-se concluir 
que a rota otimizada, utilizando o método do vértice adjacente mais próximo, partindo de 
AAA para chegar em FFF foi de 41.
1
Fonte:
Material didatico apresentado no curso.
2