Em um grafo com
vétices e
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
vértices e
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,
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,
Resposta
Em um grafo não orientado
; em um grafo orientado
.