1. **Enunciado do problema:** Temos cinco cidades: Lisboa, Aveiro, Coimbra, Évora e Beja, com distâncias dadas entre cada par. O objetivo é encontrar um itinerário que passe por cada cidade exatamente uma vez, começando em Coimbra, retornando a Coimbra, e minimizando a distância total percorrida (problema do caixeiro viajante). 2. **Representação do grafo:** Cada cidade é um vértice e as distâncias são pesos das arestas entre os vértices. 3. **Distâncias dadas:** - Lisboa-Aveiro: 252 - Lisboa-Coimbra: 201 - Lisboa-Évora: 150 - Lisboa-Beja: 186 - Aveiro-Coimbra: 60 - Aveiro-Évora: 306 - Aveiro-Beja: 371 - Coimbra-Évora: 755 - Coimbra-Beja: 333 - Évora-Beja: 78 4. **Objetivo:** Encontrar o ciclo Hamiltoniano mínimo começando em Coimbra. 5. **Método:** Vamos listar possíveis itinerários começando em Coimbra, passando por todas as cidades uma vez, e retornando a Coimbra, calculando a soma das distâncias para cada um. 6. **Cálculo das distâncias para alguns itinerários:** - Itinerário 1: Coimbra → Aveiro → Lisboa → Évora → Beja → Coimbra Distância = Coimbra-Aveiro (60) + Aveiro-Lisboa (252) + Lisboa-Évora (150) + Évora-Beja (78) + Beja-Coimbra (333) = 60 + 252 + 150 + 78 + 333 = 873 - Itinerário 2: Coimbra → Aveiro → Lisboa → Beja → Évora → Coimbra Distância = 60 + 252 + 186 + 78 + 755 = 1331 - Itinerário 3: Coimbra → Lisboa → Évora → Beja → Aveiro → Coimbra Distância = 201 + 150 + 78 + 371 + 60 = 860 - Itinerário 4: Coimbra → Lisboa → Beja → Évora → Aveiro → Coimbra Distância = 201 + 186 + 78 + 306 + 60 = 831 - Itinerário 5: Coimbra → Beja → Évora → Lisboa → Aveiro → Coimbra Distância = 333 + 78 + 150 + 252 + 60 = 873 7. **Conclusão:** O itinerário com menor distância total é o Itinerário 4: $$\text{Coimbra} \to \text{Lisboa} \to \text{Beja} \to \text{Évora} \to \text{Aveiro} \to \text{Coimbra}$$ com distância total $$831$$.