Circuitos de Hamilton

Circuitos de Hamilton

Tarefa 1

Considere o grafo da figura.

a) Como classifica este grafo, tendo em atenção o grau dos seus vértices?
b) Consegue encontrar algum circuito de Hamilton?
c) Quantos circuitos conseguiu encontrar na questão anterior?

Tarefa 2

Uma empresa internacional vai abrir cinco novas sucursais em cinco cidades portuguesas: Porto, Viseu, Coimbra, Lisboa e Faro.

A empresa pretende colocar a sede nacional numa das cinco cidades e, periodicamente, fazer uma visita às restantes sucursais. Sendo limitado o orçamento, é preciso que tal vistoria seja feita numa única viagem, de modo a que o circuito que parta da sede e passe por todas as sucursais tenha uma quilometragem total mínima.

Atendendo às distâncias, em quilómetros, entre cada uma das cidades indicada na tabela seguinte, encontre a solução ótima para o problema proposto.

Porto
Viseu
Coimbra
Lisboa
Faro
Porto
0
133
114
332
607
Viseu
133
0
90
308
629
Coimbra
114
90
0
218
493
Lisboa
332
308
218
0
315
Faro
607
629
493
315
0

Tarefa 1

Como organizar a contagem do número de circuitos de Hamilton num grafo completo de 4 vértices - K4?

Consideramos, por exemplo, todos os circuitos que começam no vértice A.

- A partir de A, podemos escolher um dos restantes 3 vértices:

- Para cada um desses, restam ainda duas opções possíveis para qualquer um deles:

-Finalmente regressemos ao vértice A, e o esquema completo de todos os circuitos possíveis será:

Numa primeira análise parecem existir 6 circuitos possíveis (3 x 2 x 1 = 6).

Mas são apenas 3 os circuitos distintos, uma vez que os últimos 3 são os mesmos apenas por ordem inversa!!

Se começarmos noutro vértice qualquer, vamos encontrar exatamente os mesmos circuitos!

Note que ABCDA é o mesmo que BCDAB ou CDABC.

Generalizando…

- Num grafo completo k5, teremos circuitos, mas apenas 12