Dado um grafo não direcionado fornecido como matriz de adjacência, qual condição sobre os graus dos vértices e…
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
Dado um grafo não direcionado fornecido como matriz de adjacência, qual condição sobre os graus dos vértices e a conectividade garante a existência de um ciclo Euleriano?
- A) Para haver ciclo Euleriano o grafo deve ser dirigido e regular.
- B) Basta que o grafo seja conectado; os graus dos vértices não importam.
- C) Se há exatamente dois vértices de grau ímpar, então existe um ciclo Euleriano.
- D) Se todos os vértices têm grau ímpar, existe um ciclo Euleriano.
- E) O grafo é conectado (desconsiderando vértices isolados) e todos os vértices têm grau par.
✅ Resposta correta: alternativa E
Resolução passo a passo
- Lembre o teorema de Euler para grafos não direcionados: existe ciclo Euleriano (circuito que usa todas as arestas exatamente uma vez e volta ao vértice inicial) se, e somente se, o grafo é conexo (desconsiderando vértices isolados) e todos os vértices têm grau par. Passo 2: A alternativa E enuncia exatamente essa condição, por isso está correta. Passo 3: A alternativa A está errada, pois ciclo Euleriano em grafo dirigido exige que cada vértice tenha grau de entrada igual ao de saída, e não que o grafo seja regular; além disso, a questão trata de grafo não direcionado. Passo 4: A alternativa B está errada, pois a conectividade sozinha não basta, já que vértices de grau ímpar impedem o ciclo. Passo 5: A alternativa C está errada, pois dois vértices de grau ímpar caracterizam a existência de um caminho Euleriano (que não fecha ciclo), e não de um ciclo. Passo 6: A alternativa D está errada, pois ter todos os vértices de grau ímpar é justamente o que impede a existência de ciclo Euleriano. Passo 7: Portanto o gabarito oficial E está correto e coincide com a resolução feita de forma independente.
💡 Dica: Revise as condições para a existência de um ciclo Euleriano em grafos.
Alternativa por alternativa
Acredita que a regularidade do grafo é a condição necessária e que a orientação das arestas é exigida para o ciclo Euleriano, confundindo com a condição de grau de entrada igual ao de saída em grafos dirigidos.
Supõe que, sendo o grafo conectado, todas as arestas podem ser percorridas em um ciclo, ignorando que vértices de grau ímpar bloqueiam o retorno ao ponto inicial.
Confunde a condição de caminho Euleriano (exatamente dois vértices de grau ímpar, que são os extremos do caminho) com a de ciclo Euleriano, que exige todos os graus pares.
Por que engana: Confundir as condições para a existência de um ciclo Euleriano, acreditando que um grafo com vértices de grau ímpar pode ter um ciclo Euleriano.
Imagina que a paridade ímpar uniforme dos graus favorece o fechamento do ciclo, quando na verdade cada vértice de grau ímpar torna impossível fechar o circuito.
Pelo teorema de Euler, um circuito que percorre todas as arestas existe somente se o grafo for conexo e cada vértice tiver grau par; vértices de grau ímpar impedem um ciclo Euleriano.
Raio-X da questão
ciclo Euleriano
avaliacao
grafo e suas propriedades · matriz de adjacência
Estudar as propriedades de grafos e condições para ciclos Eulerianos.
Confundir as condições para a existência de um ciclo Euleriano, acreditando que um grafo com vértices de grau ímpar pode ter um ciclo Euleriano.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um grafo não direcionado, qual condição sobre o grau dos vértices garante a existência de um circuito Euleriano…
- Proponha um algoritmo para decidir se um grafo simples não direcionado possui circuito Euleriano. Indique que…
- Dado um grafo simples não direcionado com V vértices e E arestas, qual condição necessária e suficiente (usando V, E e…
- Qual propriedade deve ter um grafo dirigido para que seja possível executar um algoritmo de ordenação topológica sobre…
- Qual a principal característica de um grafo não direcionado?
- Em um grafo não direcionado simples, qual propriedade a matriz de adjacência A (n×n, entradas 0/1) satisfaz em relação à…
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