6.1.1. Concepto de árbol
Un grafo G es un árbol, si cada dos puntos de G están unidos por un sólo camino (conexo) y p = q +1 (el número de puntos es igual al número de líneas más uno).
Un árbol es una estructura jerárquica aplicada a un conjunto de elementos llamados nodos, uno de los cuales es conocido como raíz. Además, se crea una relación o parentesco entre los nodos que da lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etcétera.
Se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárboles. Una forma particular de árbol puede ser la estructura vacía.
Los árboles tienen muchísimas aplicaciones. Se utilizan para representar fórmulas matemáticas, para organizar la información, para la investigación de operaciones y toma de decisiones, para el análisis de circuitos eléctricos, etcétera.
A los árboles ordenados de grado dos se les conocen como árboles binarios, ya que cada nodo del árbol no tendrá más de dos descendientes directos. Estos árboles tienen muy variadas aplicaciones, dado que se les puede utilizar para representar estructuras en las cuales se tomen decisiones con dos opciones en distintos puntos.
Ejemplo de árbol
Ejemplo de árbol binario
En ciencias de la computación, un árbol es una estructura de datos comúnmente usada, que emula la estructura de un árbol con un conjunto de nodos conectados.
Cada uno de los nodos de un árbol tiene cero o más nodos hijos, que están por debajo de él (en ciencias de la computación, al contrario que en la naturaleza, los árboles crecen hacia abajo, no hacia arriba). El nodo del cual otro es hijo, es llamado su nodo padre. Un hijo tiene como máximo un padre; un nodo sin padre es llamado nodo raíz (o simplemente raíz). Los nodos sin hijos son llamados hojas.
En Teoría de grafos, un árbol es un dígrafo conectado acíclico. Un árbol con raíz es como un grafo con un vértice seleccionado como la raíz. En ese caso, sólo dos vértices conectados con el lado heredan una relación de padre-hijo. Un grafo acíclico con múltiples componentes conectados, o un conjunto de árboles con raíz, recibe el nombre de bosque.
