Exercícios: O caixeiro-viajante

Um grafo tem vértices {A, B, C, D, E} e arestas AB, BC, CD, DE, EA, AC e BD.

1. a) Explica, com as tuas palavras, o que é um ciclo de Hamilton (ciclo hamiltoniano).
2. b) A sequência A → C → D → E → B → A é um ciclo hamiltoniano deste grafo? Justifica.
3. c) Indica um ciclo hamiltoniano do grafo, escrevendo a sequência de vértices percorridos.

Um grafo tem vértices {P, Q, R, S} e arestas PQ, PR, PS, QR e RS.

1. a) O grafo admite um ciclo hamiltoniano? Em caso afirmativo, indica-o.
2. b) Se for retirada a aresta QR, continua a existir um ciclo hamiltoniano? Justifica, relacionando a tua resposta com o grau dos vértices.

A empresa de catering SaborLuso, sediada em Coimbra (C), tem de entregar refeições em três escolas, situadas em Aveiro (A), Leiria (L) e Viseu (V), regressando a Coimbra no fim. A tabela indica as distâncias rodoviárias, em quilómetros, entre as cidades.

	A	C	L	V
A	—	65	115	95
C	65	—	75	90
L	115	75	—	135
V	95	90	135	—

1. a) Partindo de Coimbra, quantos percursos diferentes existem que visitam as três escolas exatamente uma vez e regressam a Coimbra? Lista todos esses percursos.
2. b) Calcula a distância total de cada percurso.
3. c) Indica o percurso mais curto e a respetiva distância.
4. d) O que observas quanto aos comprimentos dos percursos percorridos em sentidos opostos?

A empresa de painéis solares SolSul, sediada em Évora (E), tem de visitar clientes em Beja (B), Faro (F), Setúbal (S) e Portalegre (P), regressando a Évora no fim. A tabela indica as distâncias aproximadas, em quilómetros.

	E	B	F	S	P
E	—	80	220	105	110
B	80	—	145	150	155
F	220	145	—	200	300
S	105	150	200	—	200
P	110	155	300	200	—

1. a) Aplica o método do vizinho mais próximo: parte de Évora e desloca-te sempre para a cidade ainda não visitada mais próxima; no fim, regressa a Évora. Escreve o percurso obtido e calcula a sua distância total.
2. b) Um colega sugere o percurso E → S → F → B → P → E. Calcula a distância total deste percurso e compara-a com a do método do vizinho mais próximo.
3. c) O que concluis sobre a fiabilidade do método do vizinho mais próximo? Como poderias garantir que encontras o percurso mais curto de todos?