Atividades sobre Propriedades de grafos com gabarito — 7º ano (EF07CO04)

Quando recebo a EF07CO04 no planejamento, meu primeiro cuidado é não deixar a palavra “grafos” assustar a turma. No 7º ano, eu parto de situações que eles reconhecem: mapa da escola, amizades numa rede social, rotas entre bairros ou conexões de jogos. A ideia é fazer a representação ganhar sentido antes de pedir qualquer linguagem mais técnica.

Também preciso transformar a habilidade em evidência de aprendizagem: o estudante não pode só repetir o que é vértice e aresta. Ele precisa olhar para um desenho ou uma lista, identificar conexões, comparar representações e justificar o que concluiu. É esse caminho que uso para preparar aula e avaliação.

O que a habilidade EF07CO04 pede, de verdade?

A habilidade EF07CO04 pede que o aluno explore as propriedades básicas de grafos, isto é, reconheça uma rede formada por pontos e ligações e consiga extrair informações dela. Na prática, eu espero que a turma identifique o que cada ponto representa, o que cada conexão representa, quais vértices são vizinhos, quantas ligações chegam a um ponto e se há caminhos ou ciclos. Também vale apresentar maneiras simples de registrar o mesmo grafo, como desenho, lista de arestas e lista de adjacência. O foco não é transformar a aula em disciplina universitária de algoritmos: é desenvolver leitura, organização e análise de relações. Quando o aluno percebe que uma planta de salas, uma rede social ou um mapa podem ser modelados com vértices e arestas, ele entende por que esse conteúdo pertence ao Pensamento Computacional. A partir daí, questões objetivas deixam de ser adivinhação e passam a cobrar observação e argumentação.

“Explorar propriedades básicas de grafos.”

Essa é uma habilidade da unidade temática Pensamento Computacional, no objeto de conhecimento Propriedades de grafos, para o componente de Computação no 7º ano.

Como trabalhar EF07CO04 em sala?

1. Mapa da própria escola: desenho salas, pátio, biblioteca e secretaria como vértices. Em duplas, os alunos traçam as passagens possíveis como arestas e respondem quem é adjacente a quem.
2. Rede de interesses: cada grupo cria uma rede fictícia de personagens ligados por um interesse comum. Depois, conta o grau de cada personagem e discute quem tem mais conexões.
3. Cartões no chão: uso folhas com nomes de lugares e barbante, fita crepe ou linhas desenhadas no quadro. Peço que um aluno percorra um caminho e que outro identifique se ele voltou a um ponto já visitado.
4. Desenho para lista: entrego um grafo pequeno e proponho a conversão para lista de adjacência. É uma ótima prática para perceber que duas formas diferentes podem guardar a mesma informação.

Como avaliar essa habilidade?

Uma boa questão de EF07CO04 apresenta uma situação ou uma representação visual clara e pede uma leitura específica: identificar vértices e arestas, localizar adjacências, calcular grau ou comparar formas de armazenar conexões. Eu evito avaliar apenas vocabulário solto. Se o estudante marca “vértice” corretamente, mas não consegue dizer quem está ligado a quem, ainda preciso retomar a ideia.

Um erro comum é usar diagramas poluídos, com linhas cruzadas sem legenda, e acabar medindo atenção visual em vez de compreensão. Outro é cobrar termos muito avançados sem contextualização. Posso ampliar o desafio para estudantes que já dominam o básico, mas preciso manter o grafo e a pergunta como centro da avaliação. Para mais itens alinhados, consulto a consulta completa do código EF07CO04.

Questões prontas de EF07CO04 (com gabarito comentado)

1. Lista de adjacência no mapa de caminhos

Em um mapa de caminhos, cada ponto é representado por um vértice, e cada caminho direto entre dois pontos é representado por uma aresta. O grafo possui os vértices Central, Norte, Sul e Leste, com as arestas Central–Norte, Central–Leste e Norte–Sul. Qual é a lista de adjacência do vértice Central nesse grafo?

• ❌ A) Central: [Leste, Sul] — Leste é adjacente a Central, mas Sul está ligado diretamente a Norte.
• ❌ B) Central: [Central, Sul] — inclui uma ligação inexistente de Central com ele mesmo e com Sul.
• ✅ C) Central: [Norte, Leste] — são os dois vértices ligados diretamente a Central.
• ❌ D) Central: [Norte, Sul] — essa combinação descreve as ligações de Norte, não as de Central.
• ❌ E) Central: [Central, Norte] — cria uma ligação com o próprio Central e omite Leste.

2. Vértices e arestas em uma rede social

Em um grafo que modela uma rede social, o que representa um vértice e o que representa uma aresta?

• ❌ A) Vértice = um número; aresta = uma linha — não explica a modelagem da rede social.
• ❌ B) Vértice = uma conexão; aresta = uma pessoa — inverte entidades e conexões.
• ❌ C) Vértice = um relacionamento; aresta = uma conta — também confunde as definições.
• ✅ D) Vértice = uma pessoa (ou conta); aresta = uma conexão/relacionamento entre duas pessoas — vértices representam entidades e arestas representam relações.
• ❌ E) Vértice = um grupo de pessoas; aresta = uma conta individual — arestas conectam entidades, não representam contas.

3. Caminhos mínimos em lote

Projete a assinatura de um algoritmo que resolve várias instâncias de caminho mínimo: recebe um grafo e uma lista de pares (origem,destino). Quais parâmetros tornam a solução genérica e que estrutura pode ser reutilizada entre instâncias para otimizar desempenho?

• ❌ A) Assinatura: caminhos_em_lote(grafo) — faltam os pares de origem e destino.
• ❌ B) Usar apenas um parâmetro de origem/destino — não atende a múltiplos casos nem explicita o grafo.
• ❌ C) Assinatura: caminhos_em_lote(grafo, pares, lista_pesos) — uma lista de pesos não garante a flexibilidade descrita.
• ✅ D) Assinatura: caminhos_em_lote(grafo, pares, heurística_opcional), com tabela de distâncias pré-computada ou árvore de caminhos por fonte — permite atender critérios distintos e evitar recálculos.
• ❌ E) Não é necessário definir uma estrutura reutilizável — ignorar o reaproveitamento torna o processamento ineficiente.

4. Representação de uma rede social extensa

Para modelar conexões entre usuários em uma rede social com milhões de usuários e grau médio pequeno, qual representação de grafo é mais eficiente: matriz de adjacência ou listas de adjacência? Justifique em termos de espaço.

• ❌ A) Lista de pares — a alternativa não apresenta uma estrutura de grafo adequada como resposta à comparação.
• ❌ B) Tabela hash — pode ajudar em buscas, mas não representa por si só todas as arestas do grafo.
• ❌ C) Matriz de adjacência — não é sempre mais eficiente; em grafos esparsos ocupa muito espaço.
• ✅ D) Listas de adjacência — usam O(V+E) e armazenam apenas as conexões existentes, sendo adequadas a grafos esparsos.
• ❌ E) Array bidimensional — exige espaço para todas as combinações possíveis, como uma matriz.

5. Detecção de ciclo com DFS

No algoritmo DFS aplicado a um grafo dirigido, qual condição envolvendo a variável booleana “recStack” indica a existência de um ciclo?

• ❌ A) Verificar se recStack[v] == false — isso indica que v não está em processamento.
• ❌ B) Se recStack.length > 1 — o tamanho da estrutura não prova a existência de ciclo.
• ❌ C) Encontrar uma aresta para vértice sem recStack — isso não indica ciclo.
• ❌ D) Ciclos são identificados apenas pela quantidade de vértices visitados — quantidade não determina ciclo.
• ✅ E) Encontrar uma aresta para um vértice com recStack[v] == true — a aresta retorna a um vértice ainda em processamento, indicando ciclo dirigido.

6. Vantagem de registrar o grau do vértice

Ao representar um grafo com listas de adjacência em um programa, que vantagem traz manter uma variável “grau” para cada vértice ao executar algoritmos de análise?

• ✅ A) Fornece acesso O(1) ao número de arestas incidentes, evitando percorrer a lista para contagens repetidas — o grau pode ser atualizado ao inserir ou remover arestas.
• ❌ B) Manter o grau aumenta a complexidade — na prática, pode simplificar e acelerar consultas frequentes.
• ❌ C) Calcular o grau requer percorrer todo o grafo constantemente — com atualização adequada, isso não é necessário.
• ❌ D) O grau é irrelevante para todos os algoritmos — vários algoritmos usam essa informação estrutural.
• ❌ E) Listas de adjacência são desnecessárias se os graus são conhecidos — grau não informa quais são os vizinhos.

Próximos passos

Eu começaria com um grafo pequeno desenhado pela turma e, depois, aplicaria duas ou três questões para observar onde estão as dúvidas. Se quiser variar rapidamente nível, formato e contexto, experimente o gerador de provas do GeraProva. Há 50 questões alinhadas a esta habilidade no acervo, o que ajuda bastante na montagem de listas e avaliações.

Use estas propostas como ponto de partida e ajuste os exemplos à sua turma. Para organizar suas próximas avaliações, faça seu cadastro grátis no GeraProva.