Calcule, em função da variável n (número de vértices), quantas arestas existem em um grafo simples não…
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
Calcule, em função da variável n (número de vértices), quantas arestas existem em um grafo simples não direcionado completo K_n.
- A) Em K_n, o número de arestas é dado por V!(fatorial de V).
- B) K_n tem n-1 arestas, pois é uma árvore.
- C) O número de arestas em K_n é dado por n².
- D) n·(n-1)/2
- E) K_n contém apenas n arestas, uma para cada vértice.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Em um grafo simples não direcionado, cada aresta liga dois vértices distintos e não há arestas repetidas. Em K_n, o grafo é completo, então todo par de vértices distintos é ligado por exatamente uma aresta. Passo 2: Portanto, contar as arestas de K_n equivale a contar quantos pares não ordenados de vértices distintos existem entre os n vértices. Passo 3: Escolher 2 vértices entre n, sem considerar a ordem, é a combinação de n tomados 2 a 2, que vale n(n-1)/2. Passo 4: Verificação: em K_3 (triângulo) há 3 arestas, e 3·2/2 = 3; em K_4 há 6 arestas, e 4·3/2 = 6, o que confirma a fórmula. Passo 5: Por que as outras estão erradas: A usa fatorial, que conta permutações e cresce muito mais rápido que o número de pares; B confunde K_n com uma árvore, que tem n-1 arestas mas não possui todas as ligações; C conta pares ordenados e não divide por 2, superestimando o total; E supõe que cada vértice tem só uma aresta, ignorando que em K_n cada vértice está ligado a todos os outros. Passo 6: Conclusão: o número de arestas de K_n é n·(n-1)/2, alternativa D, que coincide com o gabarito oficial.
💡 Dica: Utilize a fórmula para calcular arestas em grafos completos.
Alternativa por alternativa
Aplica fatorial, que conta ordenações ou permutações de vértices, em vez de contar pares de vértices conectados. Não percebe que o número de arestas cresce de forma quadrática, não fatorial.
Associa K_n a uma árvore, que é conexa e acíclica com n-1 arestas. Não entende que o grafo completo possui todas as ligações possíveis entre pares de vértices.
Por que engana: Confundir o número de arestas em um grafo completo com o número de arestas em uma árvore, levando a uma resposta incorreta.
Calcula n·n, contando pares ordenados de vértices e esquecendo que a aresta entre u e v é a mesma que entre v e u, além de não excluir a ligação de um vértice consigo mesmo. Assim, obtém o dobro do número real de pares, sem dividir por 2.
Em K_n cada par distinto de vértices está ligado por uma aresta; o número de pares é C(n,2)=n(n-1)/2.
Imagina que cada vértice precisa de apenas uma aresta, como em uma intuição do dia a dia de ligar pontos em sequência. Não considera que, em K_n, cada vértice se conecta a todos os outros n-1 vértices.
Raio-X da questão
arestas em grafos completos
avaliacao
número de vértices em grafos · propriedades de grafos completos
Revisar a fórmula de arestas em grafos completos K_n.
Confundir o número de arestas em um grafo completo com o número de arestas em uma árvore, levando a uma resposta incorreta.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Um grafo completo não direcionado tem 6 vértices. Qual é o número de arestas?
- Quantas arestas possui um grafo completo com 5 vértices?
- Em um grafo não direcionado representado por lista de adjacência, como se relaciona a soma dos graus de todos os…
- Uma rede escolar com 6 computadores é modelada por um grafo não direcionado. Em um grafo completo com 6 vértices…
- Numa rede de sensores, um algoritmo registra o número de conexões de cada nó (grau). Qual alternativa identifica…
- Em um grafo com 5 vértices, quantas arestas são necessárias para conectar todos os vértices de forma que todos estejam…
🔎 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