grafos:difdmed

Geralmente, tanto a intuição quanto a matemática nos diz que o mínimo de um conjunto de elementos é sempre menor ou igual a média desses elementos.

Para os grafos, isso corresponde a dizer que o grau mínimo de um grafo $G$ é sempre menor ou igual ao grau médio de $G$. Ou seja,

$$\delta(G) \leq d_{med}(G)$$

onde:

$$d_{med}(G) = \frac{1}{|V|} \displaystyle \sum_{v \in V} d(v)$$

E como vimos no Lema do Aperto de Mão,

$$\sum_{v \in V} d(v) = 2|A|$$

Logo,

$$\delta(G) \leq \frac{2|A|}{|V|}$$

E isso está correto!

Mas repare que para o Teorema o que é tratado não é o grau médio do grafo $G$, mas sim a quantidade média de arestas por vértices desse dado grafo, que é dada por:

$$\varepsilon(G) = \frac{|A|}{|V|}$$

Veja que o coeficente que acompanha $|A|$ no numerador é 1 e não 2. Logo, a diferença entre os conceitos reside aqui, e, portanto;

$$\delta (H) > \varepsilon (H).$$

  • grafos/difdmed.txt
  • Última modificação: 2023/08/10 13:38
  • por 127.0.0.1