Em um grafo não dirigido com vértices {A, B, C} e arestas {AB, BC}, se adicionarmos a aresta AC, o grafo…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um grafo não dirigido com vértices {A, B, C} e arestas {AB, BC}, se adicionarmos a aresta AC, o grafo resultante terá um ciclo? Fundamente usando o conceito de grafo.
- A) Sim — haverá o ciclo A-B-C-A.
- B) Não — permanece apenas um caminho simples, não há ciclo.
- C) Sim — haverá um ciclo de comprimento 4.
- D) Não — um grafo com 3 vértices não pode ter ciclo.
- E) Sim — haverá o ciclo A-B-A.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Antes de adicionar a aresta AC, o grafo tem vértices A, B, C e arestas AB e BC. Ele é um caminho simples A-B-C, pois não existe nenhum percurso que comece e termine no mesmo vértice sem repetir arestas. Passo 2: Ao adicionar a aresta AC, surgem as conexões A-B, B-C e C-A. Partindo de A, passamos por B, chegamos a C e voltamos para A pela aresta AC, sem repetir vértices nem arestas intermediárias. Isso caracteriza um ciclo de comprimento 3, que é o triângulo A-B-C-A. Passo 3: Portanto, a resposta é sim, e a alternativa A está correta, pois descreve exatamente esse ciclo. Passo 4: A alternativa B está errada porque confunde o grafo antes da adição com o grafo depois dela; a aresta AC fecha o caminho e cria o ciclo. Passo 5: A alternativa C está errada porque o ciclo tem 3 arestas e 3 vértices distintos, portanto comprimento 3, e não 4; contar o vértice inicial repetido no fim não muda o número de arestas. Passo 6: A alternativa D está errada porque o número de vértices não impede a existência de ciclos; um grafo com 3 vértices pode ter ciclo, como o triângulo mostra. Passo 7: A alternativa E está errada porque percorrer A-B-A usa a mesma aresta AB duas vezes, o que é um retorno e não um ciclo; em grafos simples, um ciclo exige arestas distintas e pelo menos 3 vértices.
💡 Dica: Analise a definição de ciclo em grafos.
Alternativa por alternativa
As arestas AB, BC e AC conectam os três vértices formando um caminho fechado (triângulo) que inicia e termina no mesmo vértice, caracterizando um ciclo.
O aluno considera apenas a estrutura original AB e BC, sem perceber que a aresta AC fecha um percurso de volta ao vértice inicial. Assim, acredita que continuar sendo um caminho significa não haver ciclo.
Por que engana: Confundir a definição de ciclo, acreditando que a presença de um caminho simples é suficiente para caracterizar um ciclo.
O aluno conta vértices em vez de arestas ou inclui o vértice inicial repetido na contagem, achando que o ciclo A-B-C-A tem 4 elementos e, por isso, comprimento 4.
O aluno acredita que um grafo pequeno, com apenas 3 vértices, não pode formar um ciclo, o que confunde o tamanho do grafo com a possibilidade de fechar um percurso.
O aluno considera qualquer percurso que volta ao vértice inicial como ciclo, mesmo quando usa a mesma aresta de ida e de volta. Não percebe que, em grafos simples, um ciclo exige arestas distintas e pelo menos três vértices.
Raio-X da questão
ciclo em grafo
diagnostico
definição de grafo · ciclos em grafos
Revisar a definição de ciclos em grafos não dirigidos.
Confundir a definição de ciclo, acreditando que a presença de um caminho simples é suficiente para caracterizar um ciclo.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Um grafo não direcionado tem 4 vértices. Suas arestas são AB e BC. O grafo é conexo?
- Analise o seguinte grafo: A—B, A—C, A—D. O que se pode concluir sobre ele?
- Um grafo possui um laço no vértice A e duas arestas paralelas entre B e C. Esse grafo é simples?
- Texto curto: grafo com vértices {A,B,C,D} e arestas AB, BC, CD. Aplicando definição de caminho, qual sequência é um…
- Considere um grafo que representa salas A, B, C e D com arestas A–B, B–C, C–D e B–D. Qual aresta deve ser removida para…
- Considere a lista de objetos: A, B, C, D. Se A está conectado a B, B a C e C a D, como isso é representado em um grafo?
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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