Processing math: 100%

sexta-feira, 27 de março de 2015

Teoria de Grafos



Mostre que , para qualquer grafo G tem-se \delta(G)\leq d(G)\leq \Delta(G).

Seja G um grafo no qual   v_1,v_2\cdots,v_n
são seus vértices e d_1,d_2,\cdots,d_n são seus respectivos graus.

Sabemos que o grau médio de um  grafo é dado por :
d(G)=\frac{\sum_{v\in G} d(v)}{n}

Como d(G)=\frac{d_1+d_2+\cdots+d_n}{n}




Como  \delta(G)\leq d_i para 1\leq 1\leq n

e \Delta(G)\geq d_i para 1\leq 1\leq n.

Assim
\frac{ n \delta(G)}{n}\leq d(G)=\frac{d_1+d_2+\cdots+d_n}{n}\leq \frac{n \Delta(G)}{n}.


\delta(G)\leq d(G)=\frac{d_1+d_2+\cdots+d_n}{n}\leq  \Delta(G).


\delta(G)\leq d(G)\leq \Delta(G).\blacksquare



                                                                   

Nenhum comentário:

Postar um comentário