Matemática Aplicada 11.º Ano: Grafos e Caminhos Eulerianos (Exame 2011, 2.ª Fase)

O senhor Manuel ofereceu o capital acumulado no final de 2008 ao seu filho Miguel.
Esse dinheiro foi investido pelo Miguel na sua empresa de distribuição de congelados.
Na Figura 1, encontra-se o grafo que serve de modelo à volta utilizada pelo camião da empresa do Miguel, para efectuar a distribuição de congelados pelos supermercados que fornece.
No grafo, o vértice A representa a sede da empresa do Miguel, e os vértices B, C, D e E representam os supermercados.
Cada aresta representa um trajecto directo que liga dois supermercados, ou que liga um supermercado à sede da empresa do Miguel.
O Miguel elaborou uma lista com as voltas de distribuição, que começam e terminam na sede da sua empresa, visitando todos os supermercados, e não repetindo nenhum deles.
Para o Miguel, o que importa é o número de quilómetros percorridos, por isso, é indiferente, por exemplo, percorrer ABCDEA ou percorrer AEDCBA.
Mostre que o grafo da Figura 1 admite, exactamente, doze voltas distintas, que podem fazer parte da lista do Miguel.

Este item pode ser resolvido por, pelo menos, dois processos. 1.º Processo Calcular o número de voltas ((5 – 1)! = 24) (ou equivalente) 12 pontos Concluir da existência de 12 voltas distintas 3 pontos 2.º Processo Apresentar as 24 voltas 12 pontos Concluir da existência de 12 voltas distintas 3 pontos