grafos:raioediametro [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

==== Uma relação entre raios e diâmetros ====
<WRAP round box 60%>
=== Teorema ===
//Seja $G$ um grafo, e sejam $rad(G)$ e $diam(G)$ o [[.defraiograf|raio]] e o [[.diametro|diâmetro]] de $G$, respectivamente, vale que://

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

</WRAP>

<WRAP round box 100%>
//**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.

<wrap right>$\square$</wrap>
</WRAP>