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
- Quantas arestas possui um grafo completo com 5 vértices?
- Um grafo completo não direcionado tem 6 vértices. Qual é o número de arestas?
- Considere uma árvore com 5 nós. Qual a quantidade máxima de arestas que ela pode ter?
- Em um jogo, você precisa conectar pontos em um mapa usando arestas. Se o mapa tem 5 pontos e cada ponto pode se conectar…
- Em uma rede social, cada perfil é um nó, e as conexões entre eles são arestas. Se 5 usuários se conectam, quantas…
- Se um grafo contém 8 vértices e é um ciclo, quantas arestas ele possui?
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