Quantas arestas possui um grafo completo com 5 vértices?

Questão

Quantas arestas possui um grafo completo com 5 vértices?

1. A) 5 arestas, pois cada vértice se conecta a apenas uma outra ligação no grafo.
2. B) 10 arestas, pois em um grafo completo com 5 vértices usamos n(n-1)/2: 5×4/2 = 10.
3. C) 8 arestas, porque basta contar as conexões principais sem repetir pares de vértices.
4. D) 12 arestas, já que em grafos completos o total costuma ser um pouco maior que o dobro dos vértices.
5. E) 15 arestas, pois cada vértice pode formar uma aresta com os outros quatro e isso multiplica o total.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. Um grafo completo é aquele em que todo par de vértices distintos está ligado por exatamente uma aresta (grafo simples, não orientado).
2. Para n vértices, cada um se liga a outros n-1 vértices. Como cada aresta conecta dois vértices, a contagem direta (n vezes n-1) conta cada aresta duas vezes, por isso dividimos por 2: número de arestas = n(n-1)/2.
3. Com n = 5, temos 5 x 4 / 2 = 20 / 2 = 10 arestas.
4. Conferindo pela listagem dos pares: com os vértices 1, 2, 3, 4 e 5, temos 4 arestas saindo do vértice 1, 3 do vértice 2 (sem contar a ligação com o 1), 2 do vértice 3 e 1 do vértice 4, totalizando 4+3+2+1 = 10.
5. Por que as outras estão erradas: A) 5 arestas ignora que cada vértice precisa se ligar a todos os demais, não a apenas um. C) 8 arestas parte de uma contagem arbitrária de conexões principais, o que não corresponde à definição de grafo completo. D) 12 arestas não segue a fórmula n(n-1)/2 e não há relação geral com o dobro dos vértices. E) 15 arestas conta cada ligação duas vezes ao multiplicar 5 x 4 x... sem dividir por 2, ou seja, ignora que a aresta entre dois vértices é uma só.
6. Portanto, a alternativa correta é a B, que coincide com o gabarito oficial.

💡 Dica: Use a fórmula de arestas para grafos completos: n(n-1)/2.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resoluçã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…
• 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?
• Uma rede escolar com 6 computadores é modelada por um grafo não direcionado. Em um grafo completo com 6 vértices…
• Em uma rede social, cada amigo é um nó e as conexões são as arestas. Se você tem 5 amigos e quer saber quantas conexões…
• Calcule, em função da variável n (número de vértices), quantas arestas existem em um grafo simples não direcionado…

Todas as questões de Programação - Algoritmos clássicos