as sete pontes de Königsberg

Segundo ano de engenharia.
Cadeira de Matemática Discreta.
Capítulo dos Grafos.
A cidade de Königsberg, banhada pelo rio Pregel, possui uma pequena ilha (no meio do rio, claro está) que se encontra ligada às margens por sete pontes.
Os habitantes da cidade, nos dias de sol, tentavam efectuar um percurso que os obrigasse a passar por todas as pontes, mas somente uma e uma única vez em cada uma.
Esta história dava depois origem ao Teorema do Caixeiro Viajante, em que se pretendia que o tal vendedor conseguisse percorrer todas as terras do seu percurso, mas nunca passando na mesma terra mais do que uma vez.
O Teorema do Caixeiro Viajante é ainda apresentado num exemplo do Departamento de Matemática da Universidade de Coimbra (lamento, mas já foi há uns anos e tenho de consultar bibliografia para escrever os meus posts) como um plano de viagem, baseado em quatro cidades, onde Lisboa se encontra a 200 km de Coimbra, 150 km de Évora e 383 km de Viana; claro que depois temos Coimbra, que se encontra ainda a 255 km de Évora e 191 km de Viana... para sermos correctos ainda sabemos que Viana está a 432 km de Évora.
A ideia disto seria depois encontrar o caminho de custo mínimo que começa e acaba em Coimbra e que visitaria Lisboa, Évora e Viana uma única vez.
Se ainda não estão a dormir, poderia ainda adiantar que a resolução do problema é possível e pode ser feita com um Ciclo de Hamilton de Custo Mínimo (vão pesquisar esta... não há almoços grátis, lol).
Ignorando a questão dos custos das auto-estradas e do consumo de combustível, que aumenta nas subidas, por exemplo, definimos que a distância é a única variável da nossa definição de custo.
Desta forma, poderíamos desenhar uma árvore, tendo sempre Coimbra como raiz. Saberíamos então que existiriam três percursos iniciais: Coimbra-Lisboa, Coimbra-Évora e Coimbra-Viana.
Depois, caso começássemos pelo percurso Coimbra-Lisboa, teríamos dois novos sub-percursos: Lisboa-Évora ou Lisboa-Viana. No sub-percurso Lisboa-Évora encontraríamos agora um único percurso (Évora-Viana) e concluindo com o sub-sub-sub-percurso Viana-Coimbra.
Finalmente, tendo todos os percursos e respectivas distâncias indicadas, poderíamos verificar o percurso óptimo para a nossa viagem.
Acontece também que as coisas não são assim tão simples e, se para quatro cidades isto ainda vai, no caso de n cidades torna-se intragável.
Usamos então o Princípio Fundamental da Contagem para analisar as opções que temos. Facilmente percebemos que a cidade a ser visitada depois da primeira pode ser escolhida de (n-1) formas diferentes; a cidade a seguir a essa, de (n-2) formas e assim sucessivamente até termos uma única escolha.
Só naquela... existem (n-1)!=(n-1).(n-2)...2.1 percursos.
Façam as contas para um percurso de 10 cidades e vejam como isto fica divertido.
Para quem resistiu a ler toda a merda que publiquei aqui, mesmo só para quem resistiu à fome, sede e vontade de ir à casa de banho para ler esta treta toda sem qualquer nexo, a questão que se impõe é mesmo a pérola que se segue: não seria mais fácil o gajo usar o eBay?