Matemática 11.º Ano: Caminhos Mínimos em Grafos (Exame 2009, 2.ª Fase)

A empresa GNC, de transporte de gás natural comprimido, está sediada em Sines.
A sua frota de distribuição utiliza diferentes trajectos, que ligam as cidades de Coimbra, Évora, Faro, Lagos, Porto, Vila Real e Sines.
A distribuição começa sempre em Sines e termina sempre em Sines.
Na figura 1, encontra-se o grafo que serve de modelo aos vários circuitos utilizados pela GNC.
Cada vértice do grafo representa uma cidade, e cada aresta representa um trajecto que liga duas cidades.
Considere, agora, apenas os circuitos que incluem as cidades de Évora, Porto, Vila Real e Sines, percorridas não necessariamente por esta ordem.
Na tabela seguinte, encontram-se as distâncias entre cada duas dessas cidades quando se percorrem os trajectos indicados pelas arestas do grafo da figura 1.

	Porto	Vila Real	Sines
Évora	406 km	525 km	172 km
Porto	—	125 km	442 km
Vila Real	—	—	559 km

O preço do transporte cobrado pela empresa GNC aos clientes é de €2,00 por quilómetro.
A empresa GNC faz um desconto de 8% sobre o preço total de transporte quando o camião, partindo da refinaria de Sines, faz entregas de gás natural comprimido nas cidades de Évora, Porto e Vila Real (percorridas não necessariamente por esta ordem), passando apenas uma vez por cada cidade, e regressa à refinaria em Sines.
Determine o preço mínimo, em euros, que o comprador paga por cada transporte.
Na sua resposta deve:

• indicar o número de circuitos possíveis e as respectivas extensões, referindo apenas os que têm extensão distinta e obedecem aos critérios definidos;

• calcular o preço a pagar pelo menor circuito.

Indicar o número de circuitos distintos possíveis e as respectivas extensões 10 pontos Referir que existem 3 circuitos possíveis com extensões distintas 4 Referir as extensões dos circuitos: S-E-VR-P-S (ou S-P-VR-E-S): 1264 km 2 S-VR-E-P-S (ou S-P-E-VR-S): 1932 km 2 S-VR-P-E-S (ou S-E-P-VR-S): 1262 km 2 Calcular o preço a pagar pelo menor circuito 15 pontos Determinar o preço total (€2524) 5 Determinar o valor correspondente a 8% do preço total (€201,92) 5 Indicar o preço mínimo (€2322,08) 5 ou Determinar o preço total (€2524) 5 Determinar o preço a pagar, após o desconto (€2524 × 0,92) 10