Arboles

17 de junio de 2009
17 de junio de 2009

UNIVERSIDAD DE GUADALAJARA
17 de junio de 2009
ÁRBOLES
CENTRO UNIVERSITARIO DE LOS ALTOS (CUALTOS)
MATEMÁTICAS DISCRETAS
LIC. EN MAT.: NANCY ULLOA FIGUEROA
ING. EN COMPUTACIÓN
2° SEMESTRE
FÁTIMA CABRERA SALAS
FÁTIMA SANDOVAL ISLAS

TEPATITLAN DE MORELOS, JALISCO

Contenido
INTRODUCCIÓN 2
PROPIEDADES DE LOS ÁRBOLES 4
TEOREMAS. 5
ÁRBOLES CONTERMINAL. 7
LONGITUD DE PASEO. 7
PREFIJOS CODIFICADOS. 9
ÁRBOLES CON BUSQUEDA BINARIA. 11
ÁRBOLES GENERADORES. 13
ÁRBOLES GENERADORES MINIMOS. 14



INTRODUCCIÓN
A partir de 1920 se despertó el interés por la teoría de gráficas. Sin duda, una de las razones de este reciente interés en la teoría de gráficas es su capacidad de aplicación en campos muy diversos, incluyendo las ciencias de lacomputación, la química, la investigación de operaciones, la ingeniería eléctrica, la lingüística y la economía.

El gráfico tiene varios sentidos en matemáticas. Hemos usado el término gráfica en el sentido de una relación o de una función.
En muchas partes de la ciencia de las computadoras y de la informática aparecen los grafos, especialmente los grafos de árbol.
Uno de los tipos de grafos másimportantes son los árboles que forman una de las subclases de gráficas que mas se utilizan, también llamados arboles arraigados, debido a la apariencia de sus grafos dirigidos, tienen muchas utilidades en distintos campos de aplicación, como por ejemplo en las ciencias de la Computación hacen uso de los arboles ampliamente, especialmente para organizar y relacionar información en una base de datos detal forma que sea posible efectuar eficientemente operaciones que involucren a esa información, y para compiladores de lenguajes. Los arboles surgen en problemas teóricos como el tiempo optimo para ordenar.
Definimos un árbol como un grafo ordenado aplicado sobre una colección de elementos llamados nodos, uno de los cuales es conocido como raíz, en dicho grafo están conectados 2 vértices porexactamente un camino también es un grafo no dirigido conexo que no contienen circuitos y ya que hablamos de que es un grafo conexo damos por hecho que existe un paseo entre cualesquiera de sus 2 vértices. No obstante si hubiera 2 o mas paseos entre un par de vértices entonces diríamos que existe un circuito.
Una colección de arboles disjuntos es nombrada bosque que es un grafo en el que dos vérticescualquiera están conectados por como máximo un camino. Un vértice de grado 1 en un árbol es llamado hoja o un nodo terminal, y un vértice de grado mayor que 1 se le da el nombre de un nodo rama o nodo interno.
Los arboles surgen en redes que se modelan mediante grafos, en una red de comunicaciones, por ejemplo, puedes ser necesario que toda pareja de nodos de la red este conectada con el mínimocoste posible, y la solución de este problema implica la construcción de otra clase de árbol denominada árbol de expansión.

ÁRBOLES
Como ya dijimos en ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijosconectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Formalmente, podemos definir un árbol de la siguiente forma:
* Casobase: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
* Un nuevo árbol a partir de un nodo nr y k árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces de los k árboles.
El árbol resultante de

Tiene como raíz el nodo nr, los nodos son los hijos de nr y el conjunto de nodos hoja está formado por la...