Em um grafo dirigido, o que caracteriza uma componente fortemente conexa?
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 dirigido, o que caracteriza uma componente fortemente conexa?
- A) Conjunto máximo de vértices em que, para todo par u,v, existem caminhos dirigidos de u para v e de v para u.
- B) Conjunto de vértices onde há pelo menos um caminho entre u e v.
- C) Todos os vértices do grafo devem estar conectados diretamente.
- D) Qualquer par de vértices pode ser alcançado a partir de u ou v.
- E) Conjunto de vértices onde u e v estão em subgrafos distintos.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Uma componente fortemente conexa de um grafo dirigido é um subconjunto de vértices tal que, para quaisquer dois vértices u e v desse subconjunto, existe caminho dirigido de u até v e também caminho dirigido de v até u. Além disso, o conjunto é maximal: não se pode acrescentar nenhum outro vértice mantendo essa propriedade.
- Comparando com as alternativas, a alternativa A descreve exatamente essa definição: conjunto máximo em que a ida e a volta entre todo par de vértices são possíveis. Por isso, A está correta e coincide com o gabarito oficial.
- A alternativa B está errada porque basta um caminho em apenas um sentido, o que caracteriza conexão fraca e não forte.
- A alternativa C está errada porque exigir conexões diretas entre todos os vértices é uma condição de grafo completo, não de componente fortemente conexa.
- A alternativa D está errada porque alcançar um vértice a partir de outro em apenas um sentido não garante que haja caminhos nos dois sentidos.
- A alternativa E está errada porque vértices em subgrafos distintos não têm caminho entre si, o que é o oposto da conectividade pedida.
💡 Dica: Reveja a definição de componentes fortemente conexas em grafos.
Alternativa por alternativa
A definição formal de componente fortemente conexa exige que cada par de vértices no conjunto seja mutuamente alcançável por caminhos orientados.
O aluno entende que basta existir algum caminho entre os vértices, em qualquer direção, ignorando a orientação das arestas.
Por que engana: Confundir a definição de componente fortemente conexa com a de um grafo conexo, pensando que apenas a existência de caminhos é suficiente.
O aluno confunde conectividade forte com adjacência direta, achando que todos os vértices precisam ser ligados por arestas diretas entre si.
O aluno lê a condição como alcançabilidade em apenas um sentido, sem perceber que a componente exige ida e volta entre todos os pares.
O aluno confunde componente conexa com a separação em subgrafos distintos, pensando que vértices de componentes diferentes é que formam a componente.
Raio-X da questão
componentes fortemente conexas
avaliacao
grafos dirigidos · caminhos em grafos
Estudar as propriedades de grafos dirigidos e suas conexões.
Confundir a definição de componente fortemente conexa com a de um grafo conexo, pensando que apenas a existência de caminhos é suficiente.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…
- Qual é a principal característica de um grafo?
- Qual a principal característica de um grafo não direcionado?
- Descreva em pseudocódigo um algoritmo que, dado um grafo dirigido, identifica todas as componentes fortemente conexas…
- 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 em computaçã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