Arboles, tipos y sus propiedades (Matematicas)

Apuntes de matemáticas discretas, elaborado por mi para un trabajo de la universidad.


Arboles, tipos y sus propiedades (Matematicas)


https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B7MPhsRofpBiZWJhYWE2ZmMtN2YzNy00MmMxLTkzNjUtYzZlMWI1ODk5NjMx&hl=en_US
Documento online en pdf con imagenes, lo de abajo es el contenido sin formato y sin imagenes




Los árboles son una clase de grafos. 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. El siguiente grafo muestra la propagación del chisme:

Un árbol es un grafo no dirigido conexo que no contiene circuitos, es decir que no existen 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.
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 árbol con 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 está en un nivel 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 nivel de 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 árbol con 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 altura del á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 gráfica G tiene un árbol de expansión si y solo si G es conexa.
El árbol de expansión para la gráfica G que se presenta, se muestra con línea seguida.


Existen dos métodos para encontrar el árbol de expansión de una gráfica G:
1. Por búsqueda a lo ancho: permite procesar todos los vértices en un nivel dado antes de moverse al nivel más alto que lo sigue; primero se selecciona un orden de los vértices, considerando el primer vértice de ese orden como raíz.
2. Por búsqueda en profundidad: o conocido también como de regreso.
Ejemplo
Utilice la búsqueda a profundidad con el orden h, g, f, e, d, c, b, a de los vértices para determinar un árbol de expansión de la gráfica G.
Tomado h como vértice raíz tenemos:



Árboles de expansión mínimo
Un árbol de expansión comprende un grafo que posee nodos, arcos cada uno con longitud (peso) no negativa. Para encontrar el árbol de expansión mínima se debe recorrer todos los vértices del árbol en el que la suma de los pesos de sus aristas sea mínima, no se incluyen ciclos en la solución.
Un árbol de expansión mínima de G es un árbol de expansión de G con peso mínimo.
Algoritmo de la ruta más corta en un árbol
Se lo obtiene aplicando el algoritmo de Dijkstra, al recorrer el árbol se lo hace desde un Vo a un Vf por las aristas cuyos pesos sean menores y la suma del recorrido sea menor, no es necesario que se abarque todos los vértices.
Ejemplo:
Determine el árbol de expansión mínimo para la gráfica de la página 405 del texto base ejercicio 4. Utilizando el algoritmo de la ruta más corta.
Luego de haber recorrido las diferentes alternativas de la gráfica propuesta en el texto básico obtenemos como resultado la que se muestra:



Si realizamos la suma de sus pesos es de 35; sumatoria mínima.
ÁRBOLES BINARIOS
Están entre los tipos de árboles binarios especiales con raíz, su característica es que todo vértice tiene cuando mucho dos hijos. Donde cada hijo se designa como un hijo izquierdo o un hijo derecho, además, su posición en el árbol los identifica.
Formalizando se dice que un árbol binario es un árbol con raíz en el que cada vértice tiene ningún hijo, un hijo o dos hijos. Si el vértice tiene un hijo se designa como un hijo izquierdo o como derecho (pero no ambos). Si un vértice tiene dos hijos, un hijo se designa como hijo izquierdo y el otro como hijo derecho.
Un árbol binario completo es un árbol binario en el que cada vértice tiene dos o cero hijos.
Ejemplo


La altura de este árbol es de 2.
Ejercicio
Realice el ejercicio 6 de la página 389 del texto base.
RECORRIDO DE UN ÁRBOL
Existen tres métodos extras que permiten recorrer un árbol, ellos son:
 Recorrido pre orden: considera para el recorrido del árbol el siguiente orden (raíz - izquierda - derecha)
 Recorrido entre orden: considera para el recorrido del árbol el siguiente orden (izquierda -raíz - derecha)
 Recorrido postorden: considera para el recorrido del árbol el siguiente orden (izquierda – derecha - raíz)


Respuesta:
PREORDEN: * - + A B - * C D / E F A
ENTREORDEN: A + B – C * D – E / F * A
POSTORDEN: A B + C D * E F / - - A *

ISOMORFISMOS DE ÁRBOLES
Dos graficas simples G1 y G2 son isomorfas si y solo si existe una función f uno a uno y sobre del conjunto de vértices de G1 al conjunto de vértices de G2 que preserva la relación de adyacencia en el sentido de que los vértices vi y vj son adyacentes en G1 si y solo si los vértices f(vi) y f(vj) son adyacentes en G2.
Ejemplos
a)


Existe isomorfismo porque:
f(a) = 1, f(b) = 3, f(c) = 2 , f(d) = 4, f(e) = 5
b)

Fuentes de Información - Arboles, tipos y sus propiedades (Matematicas)

El contenido del post es de mi autoría, y/o, es un recopilación de distintas fuentes.

Dar puntos
35 Puntos
Votos: 6 - T!score: 6/10
  • 1 Seguidores
  • 22.608 Visitas
  • 8 Favoritos

4 comentarios - Arboles, tipos y sus propiedades (Matematicas)

@lelilolu Hace más de 3 años +1
MUY BIEN EXPLICADO. A FAV
@Valeryc Hace más de 1 año +2
Dentro de poco rindo esto.
@Manu_182 Hace más de 1 año
Hola! no tendrías por casualidad algunos teoremas demostrados no? Por ejemplo: necesito probar que un árbol T con raíz Vo es irreflexivo, asimétrico, y no cumple la propiedad transitiva. Saludos!
@luise15 Hace 15 días +1
Graciaaas... lo quería para hacer una presentación sobre esto :3