11.º anoPercurso edumaterial
O que vais aprender
- Usar conceitos de «Visitar cada vértice numa rota» num caso e justificar a conclusão.
Compreender
Um circuito hamiltoniano visita cada vértice uma vez e regressa ao vértice inicial. A condição refere-se a vértices, ao contrário do percurso euleriano, que se refere a arestas. O circuito pode deixar arestas do grafo por usar.
A rota A-B-C-D-A visita B, C e D uma vez e regressa a A. Se todas as quatro ligações indicadas existem no grafo, a sequência exemplifica um circuito hamiltoniano. A repetição de A apenas fecha a rota e não conta como segunda visita intermédia. Na sequência A-B-C-D-A, os quatro locais aparecem uma vez antes do retorno ao início. Isso só define um circuito válido se as ligações A-B, B-C, C-D e D-A existirem na rede. O facto de visitar cada vértice não exige usar todas as arestas; podem existir caminhos adicionais ignorados. Para decidir sobre grafo maior, desenhe uma rota candidata e marque vértices usados, mas não conclua inexistência só porque a primeira tentativa falhou. Ao contrário do critério euleriano de graus ímpares, não há regra elementar única de paridade que resolva todos os casos hamiltonianos.
Conhecer o número de vértices e arestas não determina sozinho se existe circuito hamiltoniano. Uma ligação indispensável ausente pode impedir o fecho. A verificação deve mostrar cada aresta usada e evitar saltos entre locais não adjacentes.
Exemplo resolvido
Numa rede diferente da figura, cinco locais A, B, C, D e E formam um pentágono de arestas AB, BC, CD, DE e EA; existe ainda a ligação AC. Indica um circuito que visite todos os locais uma vez antes de regressar.
- Escolhemos o início A e seguimos as cinco arestas do contorno: AB, BC, CD, DE e EA.
- A sequência A–B–C–D–E–A visita B, C, D e E uma vez cada, e só repete A no fecho permitido.
- A aresta adicional AC fica sem uso; um circuito hamiltoniano não exige passar por todas as arestas.
A–B–C–D–E–A é um circuito hamiltoniano válido para a rede descrita.
Atenção ao erro
Hamilton exige percorrer todas as arestas uma vez
Verifica agora
Numa rede de cinco locais há ligações A-B, B-C, C-D, D-E e E-A. A sequência A-B-C-D-E-A é um circuito hamiltoniano?
Ver solução explicada
Resposta: Sim, se estes forem os cinco vértices da rede: cada um aparece uma vez antes de regressar a A, usando ligações existentes.
Mostra os dados e cálculo: Sim, se estes forem os cinco vértices da rede: cada um aparece uma vez antes de regressar a A, usando ligações existentes.
Se existir ainda uma ligação extra A-C na rede de cinco locais, o circuito indicado deixa de valer?
Ver solução explicada
Resposta: Não. O circuito usa as cinco arestas do ciclo e pode deixar a ligação adicional A-C por percorrer.
Explica o resultado: Não. O circuito usa as cinco arestas do ciclo e pode deixar a ligação adicional A-C por percorrer.
Corrige esta leitura do caso: «Hamilton exige percorrer todas as arestas uma vez». Que relação foi confundida?
Ver solução explicada
Resposta: A leitura é injustificada. A rota é exemplo de circuito hamiltoniano neste grafo. A existência de uma rota depende das ligações concretas.
Refuta a afirmação com uma razão ligada ao caso e apresenta alternativa correta.
Que cautela é necessária ao estudar outro caso de «Visitar cada vértice numa rota»?
Ver solução explicada
Resposta: A existência de uma rota depende das ligações concretas.
Indica limite pertinente à evidência, sem prometer generalização indevida.
Alinhamento curricular e fontes
- Diferenciar circuito hamiltoniano de percurso euleriano, página 14. Objetivo oficial parafraseado: Diferenciar circuito hamiltoniano de percurso euleriano. O exemplo, a sequência e os exercícios são editoriais. · Aprendizagens Essenciais · matematica-aplicada-ciencias-sociais · 11-ano