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
.
O coeficiente binomial corresponde a
O coeficiente binomial
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 é
Resposta
Grafo completo não orientado:
. Grafo completo orientado (sem laços):
.