O grau médio de um grafo (V, A) é definido como 1|V| sumv in V g(v). Mostre que o grau médio de qualquer grafo G é igual a 2 rho, sendo rho a densidade de G(|A(G)| /|V(G)|).

Passo 1

Vamos entender o que a questão está pedindo. Estamos trabalhando com teoria dos grafos, especificamente com o conceito de grau médio de um grafo. Precisamos mostrar que o grau médio de qualquer grafo é igual a , onde é a densidade de . Para isso, vamos precisar entender como calcular o grau médio e a densidade de um grafo.

Passo 2

Primeiro, vamos lembrar o que é o grau de um vértice. O grau Grau Médio = 1|V| sumv in V g(v) de um vértice é o número de arestas que estão conectadas a ele. O grau médio do grafo é a média desses graus para todos os vértices, ou seja:
é
onde é o número de vértices no grafo.

Passo 3

Agora, vamos entender o que é a densidade rho = |A(G)||V(G)| de um grafo. A densidade é definida como o quociente entre o número de arestas e o número de vértices :

Passo 4

Sabemos que em qualquer grafo, a soma dos graus de todos os vértices é igual a duas vezes o número de arestas. Isso porque cada aresta contribui para o grau de dois vértices. Portanto:
sumv in V g(v) = 2 |A(G)|

Passo 5

Substituindo essa relação na fórmula do grau médio:
Grau Médio = 1|V| times 2 |A(G)| = 2 times |A(G)||V| é
Perceba que é exatamente a definição de .

Resposta

Portanto, o grau médio de qualquer grafo é igual a .

Exercícios relacionados