Arbol

Capitulo 3 ARBOLES
________________________________________

INTRODUCCIÓN
Los árboles forman una de las subclases de gráficas que más se utilizan. La ciencia de la computación hace uso de losárboles ampliamente, especialmente para organizar y relacionar datos en una base de datos. Los árboles surgen en problemas teóricos como el tiempo óptimo para ordenar.

TERMINOLOGÍA Y CARACTERIZACIÓNDE LOS ÁRBOLES
Un árbol T (libre) es una gráfica simple que satisface lo siguiente; si v y w son vértices en T, existe una trayectoria simple única de v a w. Se muestra un ejemplo:



Un árbolcon raíz es un árbol en el que un vértice específico se designa como raíz, se presenta un ejemplo:


Como la trayectoria simple de la raíz a cualquier vértice dado es única, cada vértice esta en unnivel determinado de manera única. Así, el nivel de la raíz es el nivel 0, los vértices que están debajo de la raíz están en el nivel 1, y así sucesivamente. Por lo tanto podemos decir que: el nivelde un vértice v es la longitud de la trayectoria simple de la raíz a v.
La altura de un árbol con raíz es el número máximo de nivel que ocurre.
Ejemplo:
Tomando como referencia el gráfico del árbolcon raíz determine el nivel del vértice a, b, g y determine también la altura del árbol.
Para el vértice a su nivel es 0
Para el vértice b su nivel es 1
Para el vértice g su nivel es 2
La alturadel árbol es de 2.
Ejercicio:
Construya dos árboles libres uno de 7 vértices y el otro de 5 vértices, luego determine cuantas aristas tiene cada árbol.

ÁRBOLES DE EXPANSIÓN
Un árbol T es unárbol de expansión de una gráfica G si T es una subgráfica de G que contiene a todos los vértices de G. Una grafica G tiene un árbol de expansión si y solo si G es conexa.
El árbol de expansión para lagrafica G que se presenta, se muestra con línea seguida.


Existen dos métodos para encontrar el árbol de expansión de una grafica G:
1. Por búsqueda a lo ancho: permite procesar todos los...