¿Qué es un Árbol?

Se entiende por árbol al grafo G= que cumple con las propiedades de ser simple, conexo y sin ciclos.

Otra definición equivalente sería:

Sea un grafo G= 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.

O la siguiente de carácter constructiva:

Un árbol es un grafo G definido recursivamente por las siguientes proposiciones:

•          Un árbol es un solo nodo.
•    Un árbol es un nodo conectado mediante sendas aristas a varios árboles denominados ramas.

Normalmente se identifica a un vértice como raíz  padre de la cual deriva aristas a otros nodos que se llaman hijos de dicho padre o raíz. A los nodos que no tienen descendencia se les llama hojas.

Ejemplo de Árbol (Click para ampliar)

Propiedades:

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

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

·         En cualquier árbol T = (V,E),  │V│= │E│+ 1.

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

Arboles 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 v0 en A con la propiedad de que existe una única trayectoria de vo hacia cualquier otro vértice de A pero no existe una trayectoria de vo a vo.

      En los gráficos, el grafo G1 es un Árbol, pero G2 no lo es, porque contiene un ciclo {a,b}, {b,c}{c,a}. El grafo G3 no es conexo, por lo que no puede ser un árbol. Sin embargo, cada componente de G3 es un árbol; en este caso G3 es un bosque.      Si un grafo es un árbol, escribimos T en vez de G, para enfatizar esta estructura.

     En el grafico podemos observar que G1 es un subgrafo de G2, que G1 contiene todos los vértices de G2 y que G1 es un árbol. En este caso, G1 es un árbol recubridor de G. por lo tanto, un árbol recubridor de un grafo conexo es un subgrafo recubridor que también es un árbol.

      Un árbol recubridor es aquel que proporciona una conectividad minimal para el grafo y como un esqueleto minimal que une los vértices. El grafo G3 es un bosque recubridor para el grafo G4.

Al contrario de los arboles naturales, cuyas raíces se localizan abajo, en teoría de graficas los arboles con raíces suelen dibujarse con la raíz hacia arriba.

Árbol Natural

Invertido para la comparación

Bosques

Un bosque es un conjunto de árboles o de otra manera podemos decir que un bosque es un grafo acíclico, se dice que el grafo es acíclico si no se tiene ningún ciclo simple.

La figura muestra un bosque, el cual está compuesto por tres árboles.

Las siguientes son las características y propiedades más importantes de los árboles en general:

1.    Todo árbol que no es vacío, tiene un único nodo raíz.

2.    Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y en este caso es común utilizar la expresión X es hijo de Y.

3.    Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en este caso es común utilizar la expresión X es padre de Y.

4.    Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

5.    Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.

6.    Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

7.    Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.

8.    Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

9.    Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

A continuación, se presenta un ejemplo para clarificar estos conceptos:

1.- 8 es la raíz del árbol. 2.- 3   es hijo de 8.   10  es hijo de 8.      1   es hijo de 3.     14  es hijo de 10.     13 es hijo de 14. 3.-8    es padre de 3.     3    es padre de 6.     6    es padre de 7.    10   es padre de 14.    14   es padre de 13.  4.- 3 y 10  son hermanos.      1 y 6    son hermanos.      4 y 7    son hermanos.  5.- 1, 4, 7, 13  son nodos terminales u hojas.  6.- 6, 14, 10,3  son nodos interiores. 7.- El grado del nodo 8   es 2.      El grado del nodo 3   es 2.      El grado del nodo 6   es 2.      El grado del nodo 14 es 1.      El grado del nodo 1   es 0.      El grado del árbol es 3.  8.- El nivel del nodo 8   es 1.      El nivel del nodo 3   es 2.      El nivel del nodo 6   es 3.      El nivel del nodo 10 es 2.      El nivel del nodo 13 es 4.