Identifique a propriedade de um grafo não direcionado que garante que não existem caminhos repetidos entre…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Identifique a propriedade de um grafo não direcionado que garante que não existem caminhos repetidos entre vértices.
- A) Grafo ponderado
- B) Grafo acíclico
- C) Grafo completo
- D) Grafo bipartido
- E) Grafo direcionado
✅ Resposta correta: alternativa B
Resolução passo a passo
- O enunciado pede a propriedade de um grafo não direcionado que garante que não existam dois caminhos diferentes ligando o mesmo par de vértices. Isso acontece quando o grafo não tem ciclos, pois, se existisse um ciclo, haveria duas rotas alternativas entre seus vértices. Passo 2: Um grafo acíclico é um grafo sem ciclos. Em um grafo não direcionado acíclico (uma floresta, e no caso conexo uma árvore), há no máximo um caminho simples entre quaisquer dois vértices, o que atende exatamente à condição descrita. Passo 3: A alternativa A está errada porque ponderado significa que as arestas têm pesos, o que não impede nem garante a unicidade de caminhos. Passo 4: A alternativa C está errada porque grafo completo é aquele em que todos os vértices são ligados entre si, o que gera muitos caminhos alternativos entre os vértices. Passo 5: A alternativa D está errada porque grafo bipartido é definido pela divisão dos vértices em dois conjuntos sem arestas internas a cada conjunto, e essa propriedade não restringe a existência de caminhos múltiplos. Passo 6: A alternativa E está errada porque direcionado trata da orientação das arestas, e a questão pede justamente um grafo não direcionado. Passo 7: Conclusão: a resposta correta é a letra B, grafo acíclico, que coincide com o gabarito oficial.
💡 Dica: Relacione a ausência de caminhos repetidos à ausência de ciclos no grafo.
Alternativa por alternativa
O aluno pode ter associado a palavra pesos das arestas a alguma restrição sobre caminhos, imaginando que o peso define quais rotas são válidas.
Em um grafo não direcionado sem ciclos, há no máximo um caminho entre quaisquer dois vértices conectados.
O aluno pode ter achado que, se todos os vértices estão ligados entre si, a estrutura é simples e organizada, logo com caminhos únicos, quando na verdade há muitas rotas alternativas.
O aluno pode ter confundido a organização em dois conjuntos de vértices com unicidade de caminhos, deduzindo que a separação em dois grupos elimina rotas repetidas.
Por que engana: Confundir a ausência de ciclos com outras propriedades, como ser completo ou bipartido, que não garantem por si só a ausência de caminhos repetidos entre vértices.
O aluno pode ter considerado que a orientação das arestas limita os percursos e, por isso, garante caminhos únicos, sem perceber que a questão exige grafo não direcionado.
Raio-X da questão
Grafo acíclico
avaliacao
Vértices e arestas de grafos · Caminhos e ciclos em grafos
Revise as propriedades de grafos e a relação entre ciclos e caminhos entre vértices.
Confundir a ausência de ciclos com outras propriedades, como ser completo ou bipartido, que não garantem por si só a ausência de caminhos repetidos entre vértices.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
- Técnicos instalam uma rede de comunicação por cabos entre os postos de uma reserva ambiental. Os postos são Riacho…
- Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
- Durante os preparativos para uma feira de ciências no bairro, a organização desenhou um mapa digital dos caminhos…
- Por que uma rede de aviso precisa continuar funcionando mesmo quando um ponto para de operar? Em uma cidade litorânea, a…
- — Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta…
🔎 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