Na preparação da sua digressão pelas ilhas do arquipélago dos Açores, a companhia de teatro optou por apresentar a peça somente nas ilhas com, pelo menos, 6000 habitantes.

Na Tabela 3, está registado o número de habitantes em cada uma das ilhas.

Tabela 3

Na Figura 1, estão indicadas essas ligações aéreas diretas entre as ilhas do arquipélago dos Açores e o respetivo custo, por pessoa.

De modo a minimizar o custo das deslocações aéreas, foram analisados os preços das ligações aéreas diretas, existentes entre as diferentes ilhas, a que a companhia de teatro poderá recorrer.

A companhia de teatro optou por começar a digressão na ilha do Faial, pretendendo terminá-la noutra ilha. De modo a minimizar o custo das viagens, aplicou o método que a seguir se descreve.

• Seleciona-se a ilha seguinte, tendo em conta que:
  • deverá corresponder à viagem de preço mais baixo;
  • se houver duas ilhas para as quais seja possível viajar pelo mesmo preço, a seleção é aleatória.
• Procede-se como foi indicado no ponto anterior, não se repetindo nenhuma ilha e terminando depois de serem visitadas todas as ilhas incluídas na digressão.

Determine o custo mínimo em deslocações aéreas de cada elemento da companhia de teatro na sua digressão pelo arquipélago dos Açores, respeitando as condições definidas.

Na sua resposta, apresente:

• um grafo ponderado que resulte da aplicação do método descrito;
• a ordem pela qual a companhia de teatro visitará as ilhas.