Arboles

Los árboles corresponden a una de las subclases de grafos de uso más amplio, particularmente en computación. Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos. El árbol es una estructura grafoidea de gran aplicación dentro de varias ciencias dentro de las matemáticas y la computación, donde existen no pocas implementaciones de los mismos y usos; pero que sirve para modelar muchos otros aspectos en otros campos de la ciencia, la producción y la vida cotidiana

Árbol no dirigido: 

Sea G = (V,E) un grafo no dirigido sin lazos. El Grafo es un árbol, si G es conexo y no contiene ciclos.

            Si un grafo es un árbol, escribimos T en vez de G, para enfatizar esta estructura.

            Un árbol recubridor  de un grafo conexo es un subgrafo recubridor que también es un árbol. Podemos pensar en un árbol recubridor como aquel que proporciona una conectividad minimal para el grafo y como un esqueleto minimal que une los vértices.

Árbol dirigido

                   Si G es un grafo dirigido, entonces G es un árbol dirigido si el grafo  no dirigido asociado con G es un árbol. Si G es un árbol dirigido, G es un árbol con raíz si existe un único vértice r en G, llamado la raíz , tal que el grado de entrada de r   = ge( r ) = 0 y para todos los demás vértices V, el grado de entrada de V es ge ( V ) = 1

Propiedades de un Árbol

 En la ciencia de la computación definimos un árbol como un conjunto de nodos y líneas. Un nodo es un elemento de información que reside en el árbol. Una línea es un par de nodos ordenados, y a la secuencia de líneas se le denomina ruta. Además, los árboles tienen las siguientes propiedades: Tienen un nodo al que se le llama raíz del árbol. Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no tiene ninguna).  Existe una ruta única del nodo raíz a todos los demás nodos del árbol.Si hay una ruta <a,b>, entonces a.„b‟ se le denomina “hijo” de “a” y es el nodo raíz de un subárbol.

¿Para que se utilizan los árboles? 

Los árboles son modelos de gran utilidad pues su representación normalmente alude a una estructura jerárquica y este es una de sus principales usos. También se usan mucho en las modelación de búsquedas o problemas que dependan de la representación de una búsqueda en un espacio representable como un grafo. Computacionalmente aparecen representados como:Listas enlazadas, Matrices de adyacencia, Arreglo lineal.entre otras formas. En todos los casos tienen gran utilidad como por ejemplo las estructuración de los sistemas de archivo 

Datos importantes de los Árboles

Para comprender mejor que es un árbol comenzaremos explicando como está estructurado.

Nodos: Se le llama Nodo a cada elemento que contiene un Árbol.

Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un nodo del Árbol puede ser la Raíz.

Nodo Padre: Se utiliza este termino para llamar a todos aquellos nodos que tiene al menos un hijo.

Nodo Hijo: Los hijos son todos aquellos nodos que tiene un padre.

Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo padre en común dentro de la estructura.

Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran en los extremos de la estructura.

Nodo Rama: Estos son todos aquellos nodos que no son la raíz  y que ademas tiene al menos un hijo.

Ejemplos de utilización de Árboles

•  Los diccionarios. A partir de una palabra, se realiza una búsqueda en el árbol para saber si está incluida en el conjunto, y si existe, se obtienen sus datos asociados (por ejemplo, si es un verbo, un sustantivo, un artículo, etc.).
• Un árbol de definición jerárquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.
• Representación de fórmulas matemáticas.
• Registrar la historia de un campeonato de tenis.
• Construir un árbol genealógico.
• Análisis de circuito eléctrico

Tipos de recorrido de un Árbol 

En ciencias de la computación, el recorrido de árboles se refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles.

Árbol binario

• Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho

• Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo
2. Visite la raíz
3. Atraviese el sub-árbol derecho

• Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo
2. Atraviese el sub-árbol derecho
3. Visite la raíz

• En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
• En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
• En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho

Bibliografia: 

Mazzoleni, María Pía. (2014). Árbol (teoría de grafos). 30 de mayo , de Repositorio Institucional de la UNLP Sitio web: https://es.wikipedia.org/wiki/%C3%81rbol_(teor%C3%ADa_de_grafos)

Jhonlier, S. M. (30 de Noviembre de 2013). Árbol (Grafo). Obtenido de Ecured: https://www.ecured.cu/%C3%81rbol_(Grafo)https://es.wikipedia.org/wiki/%C3%81rbol_(teor%C3%ADa_de_grafos)

Johnsonbaugh Richard . (2005). Matemáticas Discretas . mx: Prentice Hall.

KENNETH H. ROSEN. (2004). Matemátoca Discreta y sus Aplicaciones. España: McGraw-Hill.