Unefa

En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.
Un arbol es un grafo conexo y aciclico (sin ciclos).
Un bosque es un grafo aciclico, o sea, una union disjunta de árboles.
Una hoja en un grafo es un vertice de grado 1.
Un arbolgenerador de un grafo G es un subgrafo generador de G que es un arbol.

Definiciones
Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos. Los árboles pueden serconstruidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dandolugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Formalmente 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.

Un árbol dirigido es un grafo dirigido que sería un árbol si no seconsideraran las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todos las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vértice particular.
Un árbol recibe el nombre de árbol con raíz si cada vértice ha sido designado raíz, en cuyo caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz, a menudocon estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática; véase árbol (programación).

Un árbol etiquetado es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente las etiquetas {1,2, ..., n}.
Un árbol regular u homogéneo es un árbol en el que cada vértice tiene elmismo grado.

Propiedades y característica

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 plano.
Las siguientes son las características y propiedades más importantes de los árboles en general:
a) Todo árbol que no es vacío, tiene un único nodo raíz.
b) Un nodo X es descendiente directo de un nodo Y, si el nodo X esapuntado por el nodo Y. en
este caso es común utilizar la expresión X es hijo de Y.
c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en es caso es
común utilizar la expresión X es padre de Y.
d) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre),
son hermanos.
e) Todo nodo que no tiene ramificaciones (hijos), se conoce con elnombre de terminal u hoja.
f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
g) 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.
h) Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Pordefinición la raíz tiene nivel 1.
i) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

BÚSQUEDA EN ÁRBOL
• Algoritmo más simple
• No detectan repetidos: si aparece un nodo ya expandido, se expande de nuevo (tiempo)

BÚSQUEDA EN GRAFO
• Algoritmo más complejo
• Almacenan nodos ya expandidos, para detectar repetidos (gastan memoria)

Preorden: Primero el...