Ficha de MACS — Grafos de Hamilton (11.º Ano)
Ficha de MACS para o 11.º ano sobre grafos de Hamilton: circuito hamiltoniano, o problema do caixeiro viajante, contagem de soluções com árvores, heurísticas e otimização de rotas — 12 exercícios com soluções.
O que inclui esta ficha
- Circuito de Hamilton: visitar todos os vértices uma vez só (vs Euler: arestas)
- Quando existe: grafo completo Kn, condição de Dirac, grau ≥ 2 necessário mas não suficiente
- Contagem (n − 1)!/2 — 10 cidades = 181 440, 20 cidades ≈ 6,1 × 1016
- Caixeiro viajante: enumeração completa de 4 cidades (melhor circuito = 47 km)
- Árvores combinatórias para não escapar nenhuma solução
- Heurística do vizinho mais próximo: soluções aceitáveis, não garantidas (73 vs 72)
- Otimização: km, custo, poluição, lucro — a decisão como discussão
- 12 exercícios de tipo diversificado, com soluções completas
Competências que desenvolve: Enumerar sistematicamente com árvores, construir algoritmos simples, comparar soluções por pesos e discutir otimização e limitações — pensamento computacional, raciocínio combinatório e decisão das AE de MACS.
Conteúdo programático: Tema «Modelos de grafos e populacionais» — tópico «Grafos de Hamilton» (AE de Matemática Aplicada às Ciências Sociais do 11.º ano): circuito hamiltoniano, condições de existência, esquemas combinatórios (árvores), algoritmos e soluções aceitáveis, viabilidade económica da procura de soluções ótimas.
Porque isto importa
É a contraparte de Euler e o coração «economicamente útil» do tema: onde Euler decide se dá para passar por tudo sem repetir, Hamilton decide qual a melhor rota — e isso é o que as distribuidoras, as recolhas e as frotas fazem todos os dias. A ficha obriga às três ferramentas do documento: a contagem (n − 1)!/2 que mostra porquê não dá para tentar tudo, a árvore que sistematiza sem esquecer (ex. 4–5) e a heurística que dá «soluções aceitáveis» (ex. 6 — com um caso onde ela falha, 73 vs 72, para não se confundir ótimo com rápido). Os ex. 9 e 10 preparam as armadilhas de prova (grau ≥ 2 não basta).
Erros comuns
- Confundir Hamilton (vértices) com Euler (arestas).
- Achar que todos os graus ≥ 2 garantem o circuito (contraexemplo: dois triângulos num vértice).
- Contar n! circuitos (é (n − 1)!/2 — divide-se por partida e sentidos).
- Tratar a heurística como garantia de ótimo.
Como usar esta ficha
Imprime a ficha e resolve os exercícios sem consultar as soluções. Faz sempre os cálculos dos pesos por extenso (soma das arestas) e desenha a árvore antes de comparar — é o desenho que evita esquecer circuitos. Só depois de terminar compara com as soluções da página 4 — é nessa comparação que se identifica o que ainda precisa de revisão.