Uma equipe de estudantes está analisando uma rede simples de quatro estações de monitoramento. Cada estação…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma equipe de estudantes está analisando uma rede simples de quatro estações de monitoramento. Cada estação pode estar ligada diretamente a outra, sem laços de uma estação para si mesma e sem ligações repetidas entre o mesmo par de estações. A equipe utiliza uma busca em profundidade (DFS), iniciada em uma das estações, para examinar a rede. Nesta situação, considera-se que uma aresta é visitada quando é examinada pelo algoritmo, contando cada ligação não direcionada apenas uma vez. A rede pode ser escolhida de modo que todas as estações sejam alcançadas. Considerando as características da rede e o critério de contagem apresentado, qual é o número máximo de arestas que podem ser visitadas pela busca em profundidade?
- A) 8 arestas
- B) 6 arestas
- C) 10 arestas
- D) 4 arestas
- E) 3 arestas
✅ Resposta correta: alternativa B
Resolução passo a passo
- Com 4 estações, o número de pares possíveis de ligação é 4 x 3 / 2 = 6, pois não há laços nem ligações repetidas. Passo 2: O máximo de arestas da rede é, portanto, 6, obtido quando todas as estações estão ligadas entre si (grafo completo com 4 vértices). Passo 3: Nessa rede, a rede é conexa, então a DFS alcança todas as estações. Contando cada ligação não direcionada apenas uma vez, a busca visita as 6 arestas. Passo 4: Alternativas erradas: A (8) excede o total de pares possíveis, que é 6; C (10) é o número de pares de 5 estações, não de 4; D (4) corresponde a um ciclo de 4 estações, que não é a configuração com mais arestas; E (3) é o mínimo necessário para conectar 4 estações por meio de uma árvore, e não o máximo. Passo 5: Concluo que a alternativa correta é B, 6 arestas, o que coincide com o gabarito oficial.
💡 Dica: Considere a estrutura do grafo e a definição de busca em profundidade.
Alternativa por alternativa
Conta cada aresta duas vezes, uma em cada extremidade, ou supõe que a rede pode ter mais ligações do que pares de estações existentes.
Em uma rede simples não direcionada com quatro nós, o número máximo de arestas ocorre quando cada nó está ligado aos outros três. Como cada par de nós forma uma única aresta, o total é dado por 4 × 3 ÷ 2 = 6. Como a rede pode ser escolhida para ser completa e todas as estações são alcançadas, a DFS pode examinar as seis arestas.
Calcula o número de pares como se houvesse 5 estações, ou confunde o número de vértices com o número de arestas possíveis.
Por que engana: O aluno pode confundir o número máximo de arestas com o número de nós, pensando que cada nó corresponde a uma aresta.
Acredita que a rede de maior número de arestas é um ciclo de 4 estações, ignorando as ligações diagonais possíveis.
Supõe que a DFS percorre apenas as arestas da árvore de busca (n - 1 arestas), desconsiderando as arestas de retorno que também são examinadas.
Raio-X da questão
busca em profundidade
avaliacao
noções de grafos · tipos de algoritmos
Revisar o funcionamento de algoritmos de busca em grafos.
O aluno pode confundir o número máximo de arestas com o número de nós, pensando que cada nó corresponde a uma aresta.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Num grafo que é uma árvore com 7 vértices, quantas arestas o algoritmo precisa considerar para percorrer todos os nós…
- Em uma atividade, uma rede é representada por um grafo usando listas de adjacência. Um algoritmo de busca em…
- Uma equipe de estudantes está modelando, como um grafo dirigido, as conexões entre estações de bicicletas de uma cidade…
- Em um desenho, 5 paradas ficam em fila. Cada parada é um nó, e cada caminho entre paradas vizinhas é uma aresta. Quantos…
- Na tabela de arestas: A-B, B-C, C-D, E-F, aplique o algoritmo de busca em largura (BFS) para determinar quantos nós…
- Considere uma árvore com 5 nós. Qual a quantidade máxima de arestas que ela pode ter?
🔎 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