OIA-Wiki

En un árbol, ¿cuál es la longitud del camino más largo entre un par de nodos?

Lo que pide el enunciado se conoce como el diámetro del árbol.

Pensemos primero un poco qué pasa si tenemos un árbol que tiene una raíz. Cómo será el camino más largo del árbol? Bueno, una característica es que los extremos de este camino van a ser hojas. Ya que si alguno no lo fuera, podríamos seguir extendiendo el camino y obtener uno más largo.

El tema entonces está en ver qué dos hojas serán los extremos del camino.

Veamos que el camino entre dos hojas tiene como longitud la suma de las distancia desde las hojas en cuestión hasta el padre común de las hojas.

Ahora, supongamos que el camino más largo se tiene entre las hojas $h_1$ y $h_2$, cuyo padre común es $p$. Qué pasa si hay una hoja $H$ que tiene mayor altura que $h_1$ y $h_2$? El camino desde esta hoja $H$ hasta $h_1$ tendrá como longitud la suma de las distancias desde $H$ y $h_1$ hasta su padre común. Lo mismo para el camino de $H$ a $h_2$. Si el $H$ no está en el subárbol de $p$, entonces el padre común entre $H$ y cualquiera de $h_1$ y $h_2$ estará más arriba que $p$, y el camino desde $H$ hasta $h_1$ será la distancia entre $h_1$ y $p$, más la distancia de $p$ al padre común de $H$ y $h_1$, más la distancia desde este padre común hasta $H$. Pero este último sumando será mayor a la distancia entre $p$ y $h_2$, por lo que el camino entre $H$ y $h_1$ será mayor al de $h_1$ y $h_2$, absurdo porque este último camino es el más largo.

seguir explicacion, con dibujitos para las hojas!