Em um grafo não direcionado, qual condição sobre o grau dos vértices garante a existência de um circuito…
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
Em um grafo não direcionado, qual condição sobre o grau dos vértices garante a existência de um circuito Euleriano (ciclo que percorre cada aresta exatamente uma vez)?
- A) Todos os vértices devem ter grau ímpar para ter um circuito.
- B) O grafo deve ser desconectado.
- C) O grafo é conectado e todos os vértices têm grau par.
- D) O grafo deve ter pelo menos um vértice com grau ímpar.
- E) O grafo precisa conter um número ímpar de arestas.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Lembre a definição: um circuito Euleriano é um ciclo que passa por cada aresta exatamente uma vez, podendo repetir vértices.
- Pelo teorema de Euler para grafos não direcionados, um grafo conexo (considerando apenas os vértices com arestas) possui circuito Euleriano se, e somente se, todos os seus vértices têm grau par.
- Justificativa intuitiva: ao percorrer um circuito, cada vez que entramos num vértice por uma aresta saímos por outra, consumindo duas arestas incidentes a ele; logo o número de arestas incidentes a cada vértice deve ser par.
- Verificação das alternativas erradas:
- A) Está errada porque exigir grau ímpar é justamente o oposto da condição; graus ímpares impedem o circuito.
- B) Está errada porque o grafo precisa ser conexo, não desconectado; um grafo desconectado com arestas em componentes separadas não admite um único circuito que percorra todas as arestas.
- D) Está errada porque basta um vértice de grau ímpar para impedir o circuito Euleriano, e a condição exigida é a oposta.
- E) Está errada porque o número de arestas não determina a existência do circuito; o que importa é a paridade do grau de cada vértice.
- Conclusão: a alternativa C é a correta e coincide com o gabarito oficial.
💡 Dica: Reveja as condições para a existência de circuitos Eulerianos.
Alternativa por alternativa
O aluno pode ter confundido a condição do circuito Euleriano com a do caminho Euleriano aberto, que admite exatamente dois vértices de grau ímpar, ou ter invertido a paridade exigida.
Por que engana: Confundir as condições para a existência de um circuito Euleriano, acreditando que vértices com grau ímpar são necessários.
O aluno pode imaginar que separar o grafo em partes ajuda a formar o ciclo, ignorando que todas as arestas precisam estar num único percurso fechado.
Teorema de Euler: um grafo não direcionado conexo possui circuito Euleriano se, e somente se, todos os vértices têm grau par.
O aluno pode ter lido a condição de forma invertida, pensando que a presença de vértice ímpar favorece o circuito, quando na verdade ela o impede.
O aluno pode ter associado a paridade ao número total de arestas, em vez da paridade do grau de cada vértice, que é a propriedade relevante.
Raio-X da questão
circuito Euleriano
avaliacao
grafo e suas propriedades · grau dos vértices
Estudar as condições para a existência de circuitos Eulerianos em grafos.
Confundir as condições para a existência de um circuito Euleriano, acreditando que vértices com grau ímpar são necessários.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Dado um grafo não direcionado fornecido como matriz de adjacência, qual condição sobre os graus dos vértices e a…
- Proponha um algoritmo para decidir se um grafo simples não direcionado possui circuito Euleriano. Indique que…
- Em um grafo não dirigido, o termo 'grau' de um vértice refere-se a qual quantidade?
- Qual a principal característica de um grafo não direcionado?
- Em um grafo não direcionado representado por lista de adjacência, como se relaciona a soma dos graus de todos os…
- Identifique a propriedade de um grafo não direcionado que garante que não existem caminhos repetidos entre vértices.
🔎 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