Arboles

Introducción

El árbol es una abstracción matemática de una estructura no lineal que modela una estructura jerárquica. El árbol juega un papel central en el diseño y análisis de algoritmos ya que se utilizan para describir propiedades dinámicas de los algoritmos y porque se construyen. Los árboles se encuentran frecuentemente en la vida diaria: en árboles genealógicos y representación detorneos. En computación los encontramos en los compiladores, en la organización de sistemas de archivos la estructura de herencia de las clases de Java es un árbol, la invocación de los métodos en tiempo de ejecución en Java es un árbol; procesamiento de textos y algoritmos de búsqueda.

Supongamos que se quiere comunicar n nodos utilizando una red de interconexión que tenga el menor número posible deenlaces. Para permitir la comunicación entre dos nodos cualesquiera, el grafo G correspondiente a esta red tendrá que ser conexo y, por otra parte, no podrá contener ciclos, porque si tuviese y uv fuese una arista perteneciente a un ciclo, entonces el grafo G–uv sería aún conexo y tendría menor número de aristas que G. Por ejemplo, el grafo “estrella” de la siguiente figura muestra la soluciónal problema planteado que tiene diámetro mínimo D = 2.

[pic]

La solución encontrada corresponde a un tipo de grafo conexo particularmente simple y con muchas aplicaciones: un árbol.
Propiedades de los Árboles

Un árbol es un grafo conexo y sin ciclos. La figura muestra, por ejemplo, un árbol con orden 7. Este tipo de estructura combinatoria aparece en muchas aplicaciones de naturaleza[pic]
distinta. Por ejemplo, en el diseño de algoritmos y estructuras de datos se utilizan los llamados árboles de decisión y, en particular, los árboles binarios, en los cuales existe un único vértice r, llamado raíz, que tiene grado 2 y los vértices restantes tienen grado 1 o 3. Así, en el árbol binario de la figura 6.3, los vértices v y w representan posibles alternativas a partir de u.[pic]

El teorema siguiente da diversas caracterizaciones de los árboles. Si u;v son vértices independientes de un grafo G=(V;E), representaremos por G+uv el grafo resultante de añadir a G la arista uv, es decir, G+uv = (V;E U{uv})

Teorema: Dado un grafo G, las proposiciones siguientes son equivalentes:

(a) G es un árbol.
(b) G es conexo y no tiene ciclos.
(c) Entre cada par de vértices de Gexiste un único camino.
(d) G es conexo con orden n y tamaño n-1.
(e) G es conexo, pero G – e es no conexo para toda arista e Є E(G).
(f) G es acíclico, pero G+uv contiene un ciclo para todo par u.v de vértices independientes.

Tipos de Árboles

Árboles binarios
Conjunto finito de nodos el cual puede ser vacío o tener un par de árboles llamados izquierdo y derecho. Cuando un nodo no tienehijos se le llama hoja o nodo terminal. La Altura de un árbol es el número de niveles que tiene. Un árbol es
completo cuando contiene el número máximo de nodos para su altura.

[pic]

Árboles Ternarios
Un árbol ternario es una estructura similar a un árbol, tiene una raíz y cada nodo tiene máximo tres hijos.

[pic]

Árboles libres
Es una colección de vértices y lados que satisfacenciertos requerimientos. Un vértice es un objeto que tienen un nombre y puede contener otra información asociada. Un lado es una conexión entre dos vértices.
[pic]

Árboles con raíz
En este árbol un nodo es designado como la raíz del árbol, en computación se usa a este concepto se le conoce simplemente como árbol.

[pic]

BOSQUES

Un bosque representa un conjunto normalmente ordenado de unoo más árboles generales.
Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.
[pic]

ÁRBOLES CON PESOS
Se llama árbol ponderado a un árbol en el que cada arista tiene asignado un número llamado peso.
1. Peso Nodo Externo: El identificador asociado al nodo externo.
2. Longitud Paso Externo Ponderado:...