Nome:Turma:Data:
Computação + Matemática · 6º ao 7º ano · Grafos

Mapa dos bairros

BNCC: EF07CO04 Explorar propriedades básicas de grafos. · EF06MA34 Interpretar e desenvolver fluxogramas simples, identificando relações entre objetos (por exemplo, cidades ligadas por estradas).

Este é um grafo: cada lugar é um vértice e cada rua é uma aresta. O número na aresta é o tempo, em minutos, para ir de um lugar ao outro.

4215810263ACentroBEscolaCPraçaDMercadoEPostoFParque

1. Quantos vértices e quantas arestas tem o grafo?

Vértices: ______    Arestas: ______

2. O grau de um vértice é o número de arestas ligadas a ele. Complete:

VérticeABCDEFSoma
Grau

Compare a soma dos graus com o número de arestas. O que você percebe?

3. Qual é o caminho mais rápido do Centro (A) até o Parque (F)?

Teste pelo menos três caminhos e calcule o tempo de cada um.

Caminho (ex.: A → B → D → F)Tempo total

O caminho mais rápido é: ______________________ com ______ minutos.

4. A rua entre Mercado (D) e Posto (E) fechou para obras. Qual é o novo caminho mais rápido de A até F?

5. Escreva com suas palavras uma estratégia (algoritmo) para encontrar o caminho mais rápido em qualquer mapa.

Gabarito e orientações para o professor

1. 6 vértices e 9 arestas. 2. Graus: A=2, B=3, C=4, D=4, E=3, F=2; soma 18 = 2 × 9 (cada aresta conta duas vezes).

3. A → C → B → D → E → F = 2 + 1 + 5 + 2 + 3 = 13 min. Caminhos “óbvios” como A → B → D → F dão 15 e A → C → B → D → F dá 14.

4. Sem a aresta D–E: A → C → B → D → F = 14 min.

5. Aceite estratégias como a de Dijkstra: a partir da origem, sempre avançar para o lugar ainda não visitado com menor tempo acumulado, atualizando os tempos dos vizinhos.

Use junto com: 📋 Grafos e o caminho mais curto · 🎮 Rota Mais Curta