Considere o grafo não orientado representado pela lista de arestas [(1,2),(2,3),(3,1),(3,4)]. Construa a lista…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio da reutilização de partes de soluções existentes.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Considere o grafo não orientado representado pela lista de arestas [(1,2),(2,3),(3,1),(3,4)]. Construa a lista de adjacência (mapa vértice ? vizinhos) com os vizinhos em ordem crescente.
- A) {1: [3], 2: [1], 3: [2], 4: []}
- B) {1: [2,4], 2: [1,3], 3: [1,4], 4: [2]}
- C) {1: [2,3], 2: [3], 3: [], 4: []}
- D) {1: [2,3], 2: [1,3], 3: [1,2,4], 4: [3]}
- E) {1: [2], 2: [1,3,4], 3: [2], 4: [3]}
✅ Resposta correta: alternativa D
Resolução passo a passo
- Em um grafo não orientado, cada aresta (u,v) liga u a v e v a u, ou seja, o par aparece nas listas de adjacência dos dois vértices.
- Analisando a aresta (1,2), o vértice 1 recebe o vizinho 2 e o vértice 2 recebe o vizinho 1.
- Analisando a aresta (2,3), o vértice 2 recebe o vizinho 3 e o vértice 3 recebe o vizinho 2.
- Analisando a aresta (3,1), o vértice 3 recebe o vizinho 1 e o vértice 1 recebe o vizinho 3.
- Analisando a aresta (3,4), o vértice 3 recebe o vizinho 4 e o vértice 4 recebe o vizinho 3.
- Montando as listas em ordem crescente: 1: [2,3]; 2: [1,3]; 3: [1,2,4]; 4: [3]. Esse é exatamente o mapa da alternativa D, que coincide com o gabarito oficial.
- Por que as outras estão erradas: A trata o grafo como orientado e ainda omite a aresta 3-4; B inventa as arestas 1-4 e 2-4 e lista 4 com vizinho 2; C registra cada aresta apenas uma vez, sem a volta; E atribui ao vértice 2 a aresta com 4 e omite o vizinho 3 do vértice 1.
💡 Dica: Para cada aresta não orientada, registre cada vértice como vizinho do outro.
Alternativa por alternativa
Trata o grafo como orientado, registrando apenas a direção 1→3, 2→1 e 3→2, e desconsidera a aresta 3-4 por completo.
Lê mal os pares da lista, criando arestas inexistentes 1-4 e 2-4 e atribuindo ao vértice 4 o vizinho 2 em vez de 3.
Registra cada aresta só uma vez, na ordem em que aparece na lista, como se o grafo fosse orientado, sem devolver a ligação ao outro vértice.
Por que engana: O aluno pode registrar cada aresta em apenas um sentido, esquecer uma conexão ou incluir como vizinhos vértices que não compartilham uma aresta.
Cada aresta (u,v) adiciona v à lista de u e u à lista de v; ordenar os vizinhos em ordem crescente produz as listas apresentadas.
Troca o vértice 3 pelo vértice 2 ao ler a aresta (3,4), gerando a falsa aresta 2-4, e deixa o vértice 1 sem o vizinho 3.
Raio-X da questão
Lista de adjacência de grafo
fixacao
Vértices e arestas de grafos · Adjacência em grafos não orientados
Revise como representar as arestas de um grafo não orientado em listas de vizinhos.
O aluno pode registrar cada aresta em apenas um sentido, esquecer uma conexão ou incluir como vizinhos vértices que não compartilham uma aresta.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Um sistema portátil registra a corrente gerada em um eletrodo de trabalho durante um pulso de 4 segundos. Para comparar…
- Em um protótipo computacional que monitora a salinidade de um tanque, dois eletrodos ficam imersos na água e são usados…
- Em uma lavanderia, uma pessoa instala dois eletrodos próximos ao piso, ligados a uma entrada digital de um controlador…
- Em uma demonstração de interface cérebro-computador, eletrodos colocados sobre o couro cabeludo captam sinais elétricos…
- Em um protótipo de interface computacional controlada por sinais musculares, cada canal utiliza um eletrodo para captar…
- Em uma prótese controlada por sinais musculares, eletrodos na pele captam a atividade elétrica e a enviam ao sistema…
🔎 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