Qual propriedade deve ter um grafo dirigido para que seja possível executar um algoritmo de ordenação…
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
Qual propriedade deve ter um grafo dirigido para que seja possível executar um algoritmo de ordenação topológica sobre seus vértices?
- A) Ser acíclico, sem ciclos dirigidos (DAG).
- B) Deve ser um grafo completo para realizar a ordenação.
- C) Ter todos os vértices com o mesmo número de conexões diretas.
- D) Ser um grafo não dirigido, pois facilita a ordenação.
- E) Deve ter pelo menos um ciclo para a ordenação ser possível.
✅ Resposta correta: alternativa A
Resolução passo a passo
- A ordenação topológica consiste em listar os vértices de um grafo dirigido de modo que, para toda aresta de u para v, u apareça antes de v na lista.
- Para que essa lista exista, não pode haver ciclos dirigidos. Se houvesse um ciclo, cada vértice do ciclo deveria vir antes de si mesmo, o que é impossível.
- Por isso, a propriedade necessária é ser acíclico, ou seja, um DAG (Directed Acyclic Graph, grafo dirigido acíclico). A alternativa A está correta e coincide com o gabarito oficial.
- A alternativa B está errada, pois o grafo não precisa ser completo; grafos esparsos são os casos mais comuns nessa aplicação.
- A alternativa C está errada, pois o grau dos vértices pode ser qualquer e não influencia a existência da ordenação.
- A alternativa D está errada, pois a ordenação topológica se define justamente para grafos dirigido; em grafos não dirigidos o conceito não se aplica.
- A alternativa E está errada, pois a presença de ciclo impede a ordenação topológica, sendo exatamente o contrário do que ela afirma.
💡 Dica: Verifique qual condição permite ordenar vértices respeitando as direções das arestas.
Alternativa por alternativa
A ordenação topológica organiza os vértices de modo que as relações direcionadas sejam respeitadas. Isso só é possível quando o grafo não contém ciclos dirigidos.
O aluno acredita que a ordenação exige um grafo com todas as arestas possíveis, confundindo a ideia de ordem com completude do grafo.
O aluno supõe que a regularidade dos graus dos vértices é necessária para organizar uma sequência, o que não tem relação com a propriedade topológica.
O aluno imagina que a ausência de direção simplifica a ordenação, desconsiderando que a noção de antes e depois depende da orientação das arestas.
O aluno inverte a condição, pensando que ciclos ajudam a ordenar os vértices, quando na verdade eles tornam a ordenação impossível.
Por que engana: Confundir a condição de aciclicidade com propriedades como ser completo ou não dirigido, ou acreditar que a presença de ciclos facilita a ordenação topológica.
Raio-X da questão
Ordenação topológica em grafos
avaliacao
Conceito de grafo dirigido · Ciclos em grafos dirigidos
Revise grafos dirigidos acíclicos e a condição necessária para a ordenação topológica.
Confundir a condição de aciclicidade com propriedades como ser completo ou não dirigido, ou acreditar que a presença de ciclos facilita a ordenação topológica.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa pré-requisitos…
- Qual a principal característica de um grafo não direcionado?
- Para que o algoritmo de Dijkstra retorne corretamente caminhos mínimos em um grafo (dirigido ou não) com pesos nas…
- Qual é a principal característica de um grafo?
- Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é…
- Identifique a propriedade de um grafo não direcionado que garante que não existem caminhos repetidos entre vértices.
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