Quantas arestas possui um grafo completo com n vértices? E um grafo orientado completo com n vértices?

Passo 1

O enunciado pede para encontrar o número de arestas de um grafo completo não orientado e de um grafo completo orientado, ambos com n vértices. Vamos usar conceitos de combinatória e definição de grafos para chegar às fórmulas.

Passo 2

Em um grafo completo não orientado cada par de vértices está ligado por exatamente uma aresta, sem considerar ordem. O número total de pares de vértices que podemos formar em um conjunto de n vértices é dado pelo coeficiente binomial binomn2.
O coeficiente binomial binomn2 corresponde a
binomn2=n!2!(n-2)!=n(n-1)2

Passo 3

Em um grafo completo orientado (sem laços) cada par de vértices distintos gera duas possíveis arestas orientadas (i→j e j→i) ou, de forma equivalente, cada vértice tem arcos para todos os outros n-1 vértices. Logo, o total de arcos é
n,(n-1)

Resposta

Grafo completo não orientado: tfracn(n-1)2. Grafo completo orientado (sem laços): n(n-1).

Exercícios relacionados