Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como identificá-lo inspecionando a estrutura de dados?
- A) Um vértice isolado tem grau 2; isso é visualizado por sua lista de adjacência conter dois adjacentes.
- B) Vértice isolado é aquele cuja lista de adjacência tem apenas um laço.
- C) Um vértice isolado tem grau 1; sua lista de adjacência contém um único vizinho.
- D) Um vértice isolado é representado por uma lista de adjacência com três elementos.
- E) Vértice isolado tem grau zero; sua lista de adjacência está vazia (nenhum vizinho).
✅ Resposta correta: alternativa E
Resolução passo a passo
- Um vértice isolado é um vértice que não possui nenhuma aresta incidente, ou seja, ele não está ligado a nenhum outro vértice. Portanto, seu grau é zero. Passo 2: Em uma lista de adjacência, cada vértice tem associada a lista dos seus vizinhos, isto é, dos vértices com os quais ele compartilha uma aresta. Passo 3: Se o vértice não tem arestas, essa lista não contém elementos, ou seja, fica vazia. Assim, para identificar um vértice isolado basta inspecionar a estrutura e verificar se a lista de adjacência dele está vazia. Passo 4: A alternativa E está correta, pois une as duas ideias: grau zero e lista vazia. Passo 5: A alternativa A está errada, porque grau 2 significa que o vértice tem dois vizinhos, portanto ele não é isolado. Passo 6: A alternativa B está errada, porque em grafo simples não existem laços, e um laço ainda assim seria uma aresta incidente ao vértice, o que o tornaria não isolado. Passo 7: A alternativa C está errada, porque grau 1 caracteriza um vértice pendente (folha), que possui um vizinho. Passo 8: A alternativa D está errada, porque o número de elementos de uma lista indica o grau do vértice e não há relação fixa com ser isolado; três elementos significariam grau três. Conclusão: o gabarito oficial E está correto.
💡 Dica: Identifique a lista de adjacência do grafo.
Alternativa por alternativa
Confunde vértice isolado com vértice de grau 2, acreditando que isolado é aquele com dois vizinhos, sem perceber que grau zero significa ausência total de arestas.
Acredita que um laço caracteriza o vértice isolado e não percebe que grafos simples não possuem laços, além de que qualquer aresta incidente torna o vértice não isolado.
Confunde vértice isolado com vértice pendente (folha), que tem grau 1, esquecendo que o isolado não possui nenhum vizinho.
Por que engana: Confundir vértice isolado com vértice de grau 1, acreditando que ele pode ter um vizinho.
Supõe que o tamanho da lista de adjacência define o isolamento, quando na verdade o número de elementos da lista corresponde ao grau do vértice e o isolado é justamente a lista sem elementos.
O grau de um vértice é o número de vizinhos; na representação por lista de adjacência isso equivale ao comprimento da lista. Se o comprimento é 0, o grau é 0 e o vértice é isolado.
Raio-X da questão
vértice isolado em grafo
diagnostico
grafo simples não direcionado · lista de adjacência
Revisar a definição de vértice isolado e lista de adjacência.
Confundir vértice isolado com vértice de grau 1, acreditando que ele pode ter um vizinho.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete um algoritmo em linguagem descritiva que, dada uma lista de adjacência de um grafo qualquer, retorne uma lista…
- Em um grafo simples não direcionado, defina o termo "grau" de um vértice e explique como obtê-lo a partir da lista de…
- Em um grafo não direcionado representado por lista de adjacência, que variável e que operação um algoritmo deve usar…
- Em um grafo, qual é a diferença entre um nó isolado e um nó conectado?
- Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
- Ao representar um grafo com listas de adjacência em um programa, que vantagem traz manter uma variável 'grau' para cada…
Todas as questões de Organização e representação da informação
🔎 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