Grafos e o caminho mais curto

Do mapa do bairro ao grafo: vértices, arestas, grau e menor caminho.

Habilidades da BNCC

• EF07CO04Explorar propriedades básicas de grafos. 📥 Baixar slides (PDF)
• EF06MA34Interpretar e desenvolver fluxogramas simples, identificando relações entre objetos (por exemplo, cidades ligadas por estradas).

Objetivos de aprendizagem

• Representar locais e ligações como vértices e arestas.
• Identificar o grau de um vértice.
• Encontrar o caminho de menor custo entre dois vértices.

Materiais

• Ficha “Mapa dos bairros”
• Mapa impresso ou projetado do bairro da escola
• Dispositivos para o jogo

Desenvolvimento

Tempo total previsto: 100 minutos.

1. 15 minDo mapa ao grafo

   Projete o mapa do entorno da escola. Escolham 6 lugares conhecidos e desenhem bolinhas (vértices) e linhas (arestas) para as ruas que os ligam. Anote os minutos a pé em cada aresta.

2. 25 minFicha Mapa dos bairros

   Em duplas: contar vértices e arestas, calcular o grau de cada vértice e achar o caminho mais curto entre dois bairros, registrando a soma.

3. 10 minEstratégias

   Compare as estratégias da turma. Apresente a ideia do algoritmo de Dijkstra em linguagem simples: sempre expandir o lugar mais próximo ainda não visitado.

4. 30 minJogo Rota Mais Curta

   Duplas resolvem as fases e comparam o custo da rota com o ótimo mostrado pelo jogo.

5. 20 minAplicação

   Onde grafos aparecem? Aplicativos de mapas, redes sociais (quem segue quem), rede elétrica. Cada dupla escreve um exemplo com vértices e arestas.

Avaliação

Na ficha: grau correto dos vértices e caminho mínimo com a soma. No jogo: número de fases resolvidas com custo ótimo.

Acessibilidade e inclusão

Materiais relacionados