Uma equipe de estudantes está modelando, como um grafo não direcionado, quatro pontos de coleta de uma cidade…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio de refinamentos, utilizando diversos níveis de abstração desde a especificação até a implementação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma equipe de estudantes está modelando, como um grafo não direcionado, quatro pontos de coleta de uma cidade, identificados pelos vértices A, B, C e D. A lista de adjacência informa, para cada vértice, os pontos diretamente conectados a ele: A: B, C; B: A, D; C: A; D: B. Cada conexão deve ser representada uma única vez, mesmo aparecendo nas listas dos dois vértices. Com base na lista de adjacência apresentada, qual das opções representa corretamente o conjunto de arestas desse grafo?
- A) Arestas: AC, BD, CD
- B) Arestas: AB, BC, BD
- C) Arestas: AB, AC, AD
- D) Arestas: AB, AC, CD
- E) Arestas: AB, AC, BD
✅ Resposta correta: alternativa E
Resolução passo a passo
- Entenda o que a lista de adjacência significa. Cada vértice lista os vizinhos diretamente ligados a ele. Em um grafo não direcionado, se X aparece na lista de Y, então Y aparece na lista de X, e essa ligação é uma única aresta.
- Monte as arestas a partir da lista de A. A: B, C gera as arestas AB e AC.
- Passe para a lista de B. B: A, D traz a ligação com A, que já é AB, e a ligação com D, que gera a aresta BD.
- Verifique as listas de C e D. C: A confirma a aresta AC já obtida, e D: B confirma a aresta BD já obtida. Não surge nenhuma nova aresta.
- O conjunto de arestas é AB, AC e BD, que corresponde à alternativa E. Nenhuma outra ligação aparece na lista, e cada aresta foi contada uma única vez, como o enunciado pede.
- Por que as outras estão erradas. A inventa a aresta CD, que não aparece em nenhuma lista. B inventa BC, que não está na lista de B nem na de C. C inventa AD, que não está em nenhuma lista. D inventa CD, e ainda omite BD.
- Conclusão. O gabarito oficial E está correto e coincide com a resolução feita independentemente.
💡 Dica: Compare cada lista de adjacência e registre cada conexão apenas uma vez.
Alternativa por alternativa
Aceita a ligação CD, que não existe em nenhuma lista, e não reconhece a ligação AB que aparece na lista de A. Provavelmente leu a lista de D de forma deslocada.
Inventa a aresta BC, possivelmente lendo a lista de B como se incluísse C, quando C aparece apenas na lista de A.
Acredita que A e D estão conectados porque A liga a B e B liga a D. Confunde adjacência direta com caminho indireto, o que é um erro conceitual sobre o que significa ser vizinho em um grafo.
Inventa a aresta CD, provavelmente por confundir a linha de C com a de D ou por supor que C e D são vizinhos. Além disso, deixa de registrar a aresta BD, que está clara na lista de B e na de D.
Por que engana: O aluno pode registrar conexões repetidas ou criar arestas entre vértices que não aparecem como diretamente conectados nas listas.
O vértice A está conectado a B e C, formando as arestas AB e AC. O vértice B está conectado a A e D; como a aresta AB já foi registrada, acrescenta-se apenas BD. As listas de C e D apenas confirmam AC e BD, respectivamente. Portanto, o conjunto de arestas é AB, AC e BD.
Raio-X da questão
Arestas em grafo não direcionado
avaliacao
Vértices e arestas de grafos · Lista de adjacência
Revise como interpretar listas de adjacência e eliminar duplicidades em grafos não direcionados.
O aluno pode registrar conexões repetidas ou criar arestas entre vértices que não aparecem como diretamente conectados nas listas.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Dada a lista de vértices A, B e C, quais são as possíveis arestas que podem conectar esses vértices?
- Considere a lista de objetos: A, B, C, D. Se A está conectado a B, B a C e C a D, como isso é representado em um grafo?
- Texto curto: grafo com vértices {A,B,C,D} e arestas AB, BC, CD. Aplicando definição de caminho, qual sequência é um…
- Em uma atividade de Computação, Júlia registrou um grafo não orientado usando uma lista de adjacência: A: B e C; B: A e…
- Em um grafo não direcionado e simples, os vértices A, B, C e D têm graus 1, 2, 2 e 3, respectivamente. Qual é o número…
- Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog