Em um grafo com n vétices e m arestas, qual a soma dos graus de todos os vértices? Observe que, em um grafo não orientado, cada aresta soma 1 ao grau de cada vértice em que incide e cada aresta incide somente sobre dois vértices. Em um grafo orientado, por outro lado, cada aresta soma 1 ao grau de cada vértice em que incide, porém, cada aresta incide somente sobre um vértice.

Passo 1

O enunciado pede para calcular a soma dos graus de todos os vértices em um grafo com n vértices e m arestas. O conteúdo aqui é Teoria de Grafos, especificamente a definição de grau de vértice e como cada aresta contribui para esse grau.

Passo 2

Num grafo não orientado, cada aresta incide exatamente em dois vértices e acrescenta 1 ao grau de ambos. Então cada aresta contribui com 2 para a soma total de graus. Logo,
sumvin V deg(v)=2m

Passo 3

Num grafo orientado, conforme o enunciado, cada aresta é considerada incidente em apenas um vértice (grau de saída ou de entrada, dependendo da definição). Assim, cada aresta soma exatamente 1 ao grau total. Logo,
sumvin V deg(v)=m

Resposta

Em um grafo não orientado sumdeg(v)=2m; em um grafo orientado sumdeg(v)=m.

Exercícios relacionados