grafos:raioediametro

Teorema

Seja $G$ um grafo, e sejam $rad(G)$ e $diam(G)$ o raio e o diâmetro de $G$, respectivamente, vale que:

$$rad(G) \leq_{(i)} diam(G) \leq_{(ii)} 2rad(G).$$

Demonstração:

A primeira desigualdade $(i)$ é direta pela definição de raio e diâmetro, uma vez que o raio é a menor distância maxima entre todos os vértices, enquanto que o diâmetro é a maior distância entre dois vértices.

Para a segunda desigualdade $(ii)$ vamos tomar $diam(G) = d(v_1,v_2)$, com $v_1,v_2 \in V(G)$. Vamos agora fixar uma das extremidades do raio, resultando em $rad(G) = d(v_3,v)$, sendo $v$ um vértice genérico de $G$. Vamos agora fazer uma desigualdade triangular com o diâmetro:

$$diam(G) = d(v_1,v_2) \leq d(v_1,v_3) + d(v_3,v_2) = rad(G) + rad(G) = 2rad(G)$$ $$\Downarrow$$ $$diam(G) \leq 2rad(G)$$

Portanto, segue a prova do teorema.

$\square$

  • grafos/raioediametro.txt
  • Última modificação: 2023/08/10 14:19
  • por 127.0.0.1