Arboles (Grafos)

Árboles
Un árbol es un grafo no dirigido en el que cualesquiera dos vértices están conectados por exactamente un camino (conexo), entonces:
- Es un grafo acíclico; así que si se añade alguna aristase forma un ciclo y si se le quita
alguna arista deja de ser conexo.
- Dos vértices cualesquiera de G están conectados por un único camino simple.
- G es conexo y tiene n − 1 aristas.Todo árbol es a su vez un grafo bipartito. Todo árbol con sólo un conjunto numerable de vértices es además un grafo lineal.

Tipos de Árboles
Árbol libre: Grafo no dirigido acíclico y conexo.
Elbosque y/o Foresta: Es menos restrictivo, es un grafo no dirigido acíclico. Es decir, da la posibilidad que sea no-conexo (se divide o separa ne conjuntos).Grafo donde cada componente conexa es un árbol,es decir que no tiene ciclos simples.

Árbol etiquetado o ponderado: Árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente lasetiquetas {1,2, ..., n}.

Árbol regular u homogéneo: Aquel en el que cada vértice tiene el mismo grado.

Árbol con raíz: Árbol libre en el cual un vértice se distingue del resto. Este vértice esla raíz, en cuyo caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz se representan de forma tal, que el vértice raíz se coloca encima de los restantes, loscuales se sitúan por niveles según su distancia a la raíz.
Los árboles con raíz, a menudo con estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática.En un Árbol con raíz o enraizado se tiene que:
* Ancestro: Cualquier nodo en el camino a la raíz de un nodo y es un ancestro de y.
* Descendiente: Si x es un ancestro de y, y es undescendiente de x.

* Si (x,y) es el último arco en el camino desde la raíz hacia y, entonces x es el padre de y & y es el hijo de x. La raíz es el único nodo sin padre.
* Si dos nodos tienen...