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

• Um sistema de uma estufa analisa cinco leituras de umidade do solo: 19, 22, 24, 27 e 20. O algoritmo conta as leituras…
• Na montagem de um boletim digital da escola, as seções estão nesta ordem: capa, entrevista, fotos e agenda. A equipe…
• Em um aplicativo da escola, a lista de representantes da turma aparece nesta ordem: Ana, Bia, Caio, Davi e Elisa. Caio…
• Enquanto agentes de manutenção acompanham pedidos de reparo de bicicletas públicas, o painel registra os chamados em uma…
• — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
• — O kit 47 já foi devolvido? — perguntou a técnica responsável pela campanha itinerante de vacinação. Antes do uso de…

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