Em um grafo com 5 vértices, quantas arestas são necessárias para conectar todos os vértices de forma que todos…
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
Em um grafo com 5 vértices, quantas arestas são necessárias para conectar todos os vértices de forma que todos estejam interligados?
- A) 5 arestas
- B) 4 arestas
- C) 3 arestas
- D) 2 arestas
- E) 1 aresta
✅ Resposta correta: alternativa B
Resolução passo a passo
- Um grafo conexo com n vértices precisa de pelo menos n - 1 arestas para que todos os vértices fiquem interligados. Esse é o número mínimo de arestas de uma árvore, que é um grafo conexo sem ciclos.
- Como o grafo tem 5 vértices, o mínimo é 5 - 1 = 4 arestas. Por exemplo, as arestas 1-2, 2-3, 3-4 e 4-5 ligam os cinco vértices em sequência, sem sobrar nenhum vértice isolado.
- Com 4 arestas o grafo já fica conectado, então a resposta correta é a alternativa B, que coincide com o gabarito oficial.
- A alternativa A (5 arestas) não está errada como possibilidade de conexão, mas não é a quantidade necessária: sobra uma aresta, que forma um ciclo. A pergunta pede o necessário, e não o máximo ou um valor qualquer que também funcione.
- A alternativa C (3 arestas) é insuficiente, pois com 3 arestas um grafo de 5 vértices fica desconectado, sobrando pelo menos dois componentes.
- A alternativa D (2 arestas) é insuficiente, pois com 2 arestas só é possível ligar no máximo 3 vértices, e dois vértices ficariam de fora.
- A alternativa E (1 aresta) é insuficiente, pois uma única aresta conecta apenas 2 vértices e deixa os outros 3 isolados.
💡 Dica: Lembre-se da fórmula para conectar vértices em um grafo.
Alternativa por alternativa
O aluno pode achar que todo vértice precisa de sua própria aresta, ou que é preciso fechar um ciclo com os 5 vértices. Assim, confunde conexão mínima com um circuito completo.
Por que engana: Confundir o número mínimo de arestas para conectar todos os vértices com o número total de vértices, levando a respostas maiores que o necessário.
Para 5 vértices é necessário conectar com 4 arestas.
O aluno pode subtrair 2 em vez de 1 do número de vértices, ou imaginar que 3 arestas bastam para espalhar a conexão pelos 5 vértices. Não percebe que cada aresta acrescenta no máximo um vértice novo à árvore.
O aluno pode pensar que cada aresta liga um par de vértices e que, por isso, poucas arestas bastam para interligar tudo. Não considera que os vértices precisam formar uma única componente conexa.
O aluno pode ter a intuição cotidiana de que um único conector já 'liga tudo', como um único cabo. Ignora que uma aresta conecta apenas dois vértices e deixa os demais isolados.
Raio-X da questão
arestas em grafos
avaliacao
conceito de grafo conexo · noção de vértices e arestas
Revisar conceitos de grafos e suas propriedades.
Confundir o número mínimo de arestas para conectar todos os vértices com o número total de vértices, levando a respostas maiores que o necessário.
pensamento_critico
abstrato
Questões parecidas com resolução
- Na mesa há duas garrafas azuis de 500 mL e dois moletons cinza. As garrafas têm adesivos diferentes, e os moletons têm…
- 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…
- Em uma praça há cinco bancos identificados B1, B2, B3, B4 e B5 ligados por caminhos entre: B1–B2, B2–B3, B3–B4 e B4–B5…
- Descreva como representar a rede de amizades de uma turma como um grafo e detalhe um procedimento passo a passo para…
- Em um grafo ponderado que modela ruas de uma cidade, como representar na aresta tanto a distância quanto o tempo de…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
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