Questões BNCC EF07CO04

Em um grafo não direcionado, como se determina o grau de um vértice?

Qual estrutura de dados é mais indicada para representar um grafo em um programa?

Identifique a propriedade de um grafo que garante que não existem caminhos repetidos entre vértices.

Qual é a representação gráfica mais comum para um grafo em um software de visualização?

Em um grafo, como as arestas contribuem para a interpretação dos dados representados?

— Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta começar a circular.

Para planejar, a equipe anotou as ligações entre pontos do bairro, pensando em cada ponto como um “nó” e cada rua como uma “ligação”. As ruas registradas foram: Feira–Terminal, Terminal–Biblioteca, Biblioteca–Parque, Parque–Feira, Biblioteca–Unidade de saúde, Unidade de saúde–Terminal, Parque–Mirante, Mirante–Feira e Terminal–Parque.

O percurso precisa usar cada rua exatamente uma vez (sem voltar pela mesma rua). Por organização do mutirão, o triciclo deve terminar na Biblioteca, onde os sacos são pesados antes de seguir para o caminhão.

Com base nas ligações do texto, identifique em qual ponto o triciclo deve iniciar para conseguir usar cada rua exatamente uma vez e terminar na Biblioteca.

Depois de duas quedas de energia no fim de semana, um bairro decidiu montar uma rede comunitária de internet por rádio. Cada ponto com antena funciona como um “nó” e cada ligação direta entre dois pontos funciona como uma “conexão”. Para evitar que uma falha derrube o bairro inteiro, o grupo desenhou as ligações planejadas entre os pontos:

Terminal (T) ligado a Feira (F), Mirante (R), Hospital (H) e Parque (P).
Feira (F) ligada também ao Mirante (R).
Mirante (R) ligado também ao Museu (U).
Museu (U) ligado também ao Terminal (T).
Hospital (H) ligado também à Estação (E).
Estação (E) ligada também ao Parque (P).
Parque (P) ligado também ao Terminal (T).

O objetivo é descobrir qual ponto exige manutenção prioritária por ser crítico para manter a rede “em uma só peça”.

Com base nas ligações descritas no texto, identifique o ponto que, se ficar fora do ar junto com suas conexões, faz a rede se separar em dois grupos sem caminho entre eles.

"Se um corredor ficar bloqueado, a gente precisa ter uma volta sem se perder", explicou a monitora de um parque ao registrar rotas de apoio no celular. Ela marcou seis pontos de referencia (A, B, C, D, E e F) e anotou as passagens que existem entre eles. Cada passagem pode ser usada nos dois sentidos.

As ligacoes registradas foram: A-B, B-C, C-D, D-E e C-F. Depois, a monitora pediu para abrir um atalho temporario ligando B a D, para facilitar a circulacao durante um evento.

No aplicativo, cada ponto funciona como um "no" e cada ligacao como uma "conexao" entre dois nos. A equipe quer testar se, com o novo atalho, ja existe um percurso que saia de um ponto e volte a ele, sem repetir ponto no meio do caminho.

Com base nas ligacoes descritas, identifique um percurso que forma um ciclo (com pelo menos 3 pontos), começando e terminando no mesmo ponto, sem repetir ponto no meio do caminho.