Definición

ARBOLES

Un árbol es una colección de elementos llamados nodos, uno de los cuales se distingue como raíz, junto con una relación (de “paternidad”) dada por una estructura jerárquica sobre los nodos. A menudo se representa un nodo por medio de una letra, una cadena de caracteres o un círculo con un número en su interior.

Los árboles forman una de las subclases de gráficas que más se utilizan. Sea un grafo G=<V,A> las siguientes propiedades son equivalentes entre sí:

· G es un árbol.

· G es simple, conexo y sin ciclos.

· G es conexo y |V|=n entonces |A|=n-1

Al contrario de los árboles naturales, cuyas raíces se localizan abajo, en teoría de gráficas los árboles con raíces suelen dibujarse con la raíz hacia arriba

Árbol, figura 9.1.2

Ejemplo, comparando con un árbol

Como la trayectoria simple de la raíz a cualquier vértice dado es única, cada vértice está en un nivel determinado de manera única. El nivel de la raíz es el nivel 0. Se dice que los vértices abajo de la raíz están en el nivel 1, y así sucesivamente. Entonces el nivel de un vértice v es la longitud de la trayectoria simple de la raíz a v. La altura de un árbol con raíz es el número máximo de nivel que ocurre.

Ejemplo

Propiedades de los arboles:

· Si ab son vértices distintos en un árbol T = (V, E), entonces hay un único camino que conecta estos vértices.

· Al quitar de A cualquier arista resulta un bosque con 2 árboles

· Si G = (V, E) es un grafo no dirigido, entonces G es conexo si y sólo si G tiene un árbol recubridor.

· Para cualquier árbol T=(V,E), sí |V| ≥ 2, entonces T tiene al menos dos vértices colgantes

· Un solo nodo es, por sí mismo, un árbol. Por lo tanto, también es la raíz de ese árbol.

· Supongamos que n es un nodo y que A1, A2 … Ak son árboles con raíces n1, n2 … nk, respectivamente. Podemos construir un nuevo árbol, haciendo que n sea el padre de los nodos. En este nuevo árbol, n es la raíz y A1, A2 … Ak son los subárboles de la raiz. Los nodos n1, n2 … nk, reciben el nombre de hijos del nodo n.

· |A| = |V| -1

Árboles con raíz

Sea A un conjunto y T una relación en A.

Se dice que T es un árbol si posee un vértice v_o en A con la propiedad de que existe una única trayectoria de v_o hacia cualquier otro vértice de A pero no existe una trayectoria de v_o a v_o.Siendo v_ola raiz del árbol.

Padre: Si v es un vértice en T, que no necesariamente es la raíz, el padre de v es el vértice único u tal que existe un arco directo, v es un hijo de u.

Hermanos, son vértices que tiene el mismo padre.

Los ancestros de un vértice, son los vértices en la ruta desde la raíz hasta ese vértice, excluyendo el vértice mismo e incluyendo la raíz.

Un vértice de un árbol enraizado es llamado hoja, si esta no tiene hijos.

Los vértices que tienen hijos son llamados vértices internos. La raíz es un vértice interno a menos que está sea el único vértice en el grafo, en cuyo caso es una hoja.

Si a es un vértice en un árbol, el subárbol con a como raíz es el subgrafo del árbol que consiste de a y sus descendientes y todos los arcos incidentes a esos descendientes.

Explicación visual

Orden de los nodos:

A menudo los hijos de un nodo se ordenan de izquierda a derecha. Así, los dos árboles presentados a continuación son diferentes, porque los dos hijos del nodo a aparecen con distintos órdenes en ambos árboles. Si se desea ignorar en su totalidad el orden de los hijos, entonces estamos hablando de un árbol no ordenado.

El orden de izquierda a derecha de los hermanos (hijos del mismo nodo) se puede extender para comparar dos nodos cualesquiera, entre los cuales no exista una relación de antecesor o descendiente. Entonces, si c y b son hermanos y a está c la izquierda de b, entonces todos los descendientes de c están a la izquierda de todos los descendientes de b.

Tipos de árboles

Los árboles se clasifican según la cantidad máxima de hijos que produce cada nodo

Árboles binarios: cada nodo padre tiene uno o dos hijos máximo.
Árboles trinarios: cada nodo padre tiene máximo tres hijos.
Árboles cuaternarios: cada nodo padre tiene como máximo cuatro hijos
Árbol binario completo. Es aquél en el que cada nodo tiene dos ramas o ninguna. Un árbol binario completo con i nodos internos tiene (i + 1) hojas y (2i +1) vértices en total.