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 dando lugar 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 es un grafo simple en el cual existe un único camino entre cada par de vértices. 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 ser construidos 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. Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro
Ejemplo de árbol:
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo. Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R. En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A),
V= A+ 1.
Teorema:
Para cualquier árbol R = (V,A), si
A
›= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
G es un árbol.
G es conexo y no contiene circuitos.
G es conexo y tiene (n-1) lados.
G no contiene circuitos y tiene (n-1) lados.
Arboles con Raíz
Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, …, vn), es un camino en G.
V(n-1) es el padre de v(n).
V0, v1, …, v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.
Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si
V › 1, sean R1, R2, R3, …., Rk los subarboles de R según se va de izquierda a derecha.
El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.
El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,…., Rk en orden simétrico.
El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,…., Rk en orden posterior y a continuación por la raíz.
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.
Teorema:
Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.
Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.
Arboles generadores:
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
lunes, 7 de diciembre de 2009
Suscribirse a:
Enviar comentarios (Atom)
No hay comentarios:
Publicar un comentario