Arboles y lenguaje (Matematica discreta)

Objetivos


Generales

1. Entender el uso de las estructuras de árbol y grafos concierne a la necesidad de la materia.
2. Conocer cuáles son los tipos de estructura de árbol existente y cuál es su complejidad



Especifico

1. Ver algunas estructuras de árbol y saber su uso y su complejidad para poder ponerlas en practica


Árboles y Lenguajes.

Árboles

Los árboles son una clase degrafos. Un claro ejemplo de un árbol es el siguiente:
Consideremos cuatro parejas de chismosos {a, A, b, B, c, C, d, D} donde a, b, c y d son los esposos y A, B, C y D son sus esposas respectivamente. Supongamos que a llama a su esposa para contarle algún chisme, entonces ella llama a las otras señoras para difundir el chisme, y cada una de ellas a su vez llama a su esposo para comunicárselo. Elsiguiente grafo muestra la propagación del chisme:


Un árbol es un grafo no dirigido conexo que no contiene circuitos, es decir que no existan dos o más paseos sobre un par de vértices.
Un conjunto de árboles disjuntos es llamado bosque. Un vértice de grado 1 en un árbol se llama hoja o un nodo terminal, y un vértice de grado mayor que 1 recibe el nombre de rama o nodo interno. Por ejemplo, son hojas:b, c, d y los vértices a, A, B, C, D son nodos rama.

Las propiedades de los árboles son:

Existe un único paseo entre dos vértices cualesquiera de un árbol.
El número de vértices es mayor en uno al número de aristas de un árbol.
Un árbol con dos o más vértices tiene al menos dos hojas.
Entre las propiedades más importantes de los árboles está la presencia de un paseo entre cualquiera de dosvértices del árbol; segundo, que el número de vértices no es menor al número de aristas del árbol y que un árbol con más de dos vértices tiene por lo menos dos hojas.

Un ejemplo claro de los árboles en la vida cotidiana son los árboles genealógicos. Para este caso, los vértices representan a los miembros de la familia y los arcos representan la relación de parentesco. Conforme los conocimientosadquiridos con anterioridad, el árbol no deja de ser un grafo, pero es del tipo no dirigido.

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.
El siguiente grafo es un ejemplo de árbol libre o árbol T:













ÁRBOLES DE EXPANSIÓN

Un árbol T es un árbol de expansión de una gráfica G si T es unasubgráfica de G que contiene a todos los vértices de G. Una gráfica G tiene un árbol de expansión si y sólo si G es conexa.
El árbol de expansión para la gráfica G que se presenta, se muestra con línea seguida.



ARBOLES ETIQUETADOS
Cuando se asocia una etiqueta, o valor, a cada nodo del árbol, a éste se le denomina árbol etiquetado.
La etiqueta de un nodo no es el nombre del nodo, sino que es informaciónque está incluida en el nodo. Es posible cambiar la etiqueta del nodo sin modificar su nombre.
Un caso particular de los árboles etiquetados lo constituyen los árboles de expresiones, utilizados para la representación de expresiones aritméticas. Las reglas para representar una expresión mediante un árbol etiquetado son:
1.- Cada hoja está etiquetada con un operando y sólo consta de ese operando.2.- Cada nodo interior está etiquetado con un operador



ARBOLES BINARIOS

Es un árbol donde cada nodo tiene como máximo dos hijos.
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que noalmacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda



ARBOLES MULTICAMINO
Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.
Existen muchas aplicaciones en las que el volumen de la...