Árboles matemáticas discretas misti. introducción el tratamiento de grafos puede resultar una...

ÁRBOLESMatemáticas Discretas

MISTI

Introducción• El tratamiento de grafos puede resultar una tarea

complicada ya que estos tienen las siguientes características :• No guardan una estructura establecida• No respetan reglas• Y la relación entre los nodos puede llegar a ser muy compleja

Introducción(II)• Por lo tanto aplicarlos en ciertas tareas, como el

tratamiento y organización de la información, puede ser muy complicado.

• Por ello en lugar de usar grafos que están estructurados sin regla alguna, se utilizan grafos con características particulares llamados árboles.

Definición • Un árbol es un grafo

• no dirigido(las aristas no tienen sentido),• conexo en donde existe un camino entre cualquier par de

vértices(v,w) y • Sin ciclos • Sin aristas múltiples

¿Cuál de estos son árboles?

Respuesta= Ambos son árboles ya que son grafos conexos y acíclicos

¿Cuál de estos grafos son arboles?

Respuesta= El primero no es un árbol, ya que e,b,a,d,e es un ciclo del grafo

¿Cuál de estos grafos son arboles?

Respuesta= El segundo no es un árbol, ya que no es conexo

Árbol con raíz • Es un árbol dónde uno de los ha sido designado como la

raíz y todas las aristas están orientadas a alejarse de la raíz

T

Con raíz en a Con raíz en c

Nodos y ramas• Los vértices de un árbol se llaman nodos y los lados

reciben el nombre de ramas

Padres e hijos• El padre de un nodo es un nodo de mayor nivel con el

que se encuentra relacionado el nodo.• Si v es el padre u, debe existir una arista dirigida de v a u.• Cualquier nodo puede tener nodos relacionados en un

nivel más bajo a los cuales se les reconoce como hijos.• Dos nodos que tienen el mismo padre se dice que son

hermanos.

v es el padre de u y de yu y y son hijos de vu y y son hermanos

Antecesores y Descendientes • Los antecesores de un vértice diferente de la raiz son

todos los vértices que aparecen desde el camino desde la raíz hasta ese vértice( excluyendo a este último e incluyendo la raíz).

• Los descendientes de un vértice v son aquellos para los que v e es un antecesor .

Los antecesores de f son b, a y c Los descendientes de a son b, f y g

Hojas y vértices internos• Un vértice se llama hoja si no tiene hijos. • Los vértices que tienen hijos se llaman vértices internos.

Árboles m-narios• Un árbol con raíz se llama árbol m-ario si todos sus

vértices internos tienen, a lo sumo, m hijos.• El árbol se llama árbol m-ario completo si todo vértice

interno tiene exactamente m hijos.

Niveles en un árbol• El nivel de un vértice v en un árbol con raíz es la longitud

del único camino desde la raíz a dicho vértice. • El nivel de la raíz por definición es 0.

Altura • La altura de un árbol con raíz es el máximo de los niveles

de sus vértices. En otras palabras, la altura de un árbol es la longitud del camino más largo desde la raíz a cualquier vértice.

Puesto que el mayor nivel es 4, el árbol tiene altura 4.

Árboles balanceados • Un árbol con raíz m-ario de altura h está equilibrado o

balanceado si todas sus hojas están en los niveles h o h-1

Árbol balanceadoÁrbol no balanceado

Balanceo de un árbol • Para balancear un árbol con una cantidad constante de

hijos de los nodos padres, se llenan empezando por la raíz y descendiendo con un avance de izquierda a derecha.

Árbol no balanceadoÁrbol balanceado como ternario

Bosques• Un bosque es un grafo acíclico pero no necesariamente

conexo. Además tienen la propiedad de que cada una de sus componentes conexas es un árbol.

Ejemplo de bosque

Árboles generadores • Sea G un grafo simple. Un árbol generador de G es un

subgrafo de G que es un árbol y contiene todos los vértices.

• Es decir, es un subgrafo conexo con el mínimo de aristas y con todos los vértices del grafo original.

Grafo simple G Árbol generador de G

Ejemplo• Considere un sistema de carreteras representadas por el

grafo simple G. En invierno estas carreteras se llenan de nieve. El departamento de mantenimiento quiere limpiar el menor número de carreteras (ya que limpiarlas todas lleva mucho tiempo) de modo que dos ciudades cualesquiera queden siempre conectadas.

Obtención de un árbol generador• Existen dos formas en que es posible obtener el árbol

generador de un grafo simple:• Búsqueda a profundidad• Búsqueda a lo ancho

Búsqueda a lo ancho• Se comienza a buscar en la raíz • Después se examinan todos los hijos de la raíz de

izquierda a derecha • Si la información no se encuentra en ese nivel, se

procede a buscar en el siguiente nivel de izquierda a derecha

• Si se recorrió todo el árbol y la información no se encontró se manda el mensaje correspondiente

Este tipo de búsqueda es efectiva cuando el árbol está balanceado y hay pocos niveles

Ejemplo búsqueda a lo ancho • Se busca la letra ‘j’• Se busca en la raíz • Se busca en el nivel 1 de izquierda a derecha• Se busca en el nivel 2 de izquierda a derecha

El recorrido para encontrar el nodo elegido es (a,b,c,d,e,f,g,h,i,j)

Búsqueda en profundidad• Se comienza a buscar en la raíz. • Después se busca en el hijo de la izquierda y si este nodo

tiene hijos se continúa con el de la izquierda y así sucesivamente hasta llegar a la parte más baja.

• Si este nodo ya no tiene hijo izquierdo , se continúa con el nodo de la derecha.

• Cuando se llega nuevamente a la hoja, se regresa hasta el nodo inmediato anterior que tenga hijos sin inspeccionar, y así sucesivamente.

• Si no se encuentra se manda el mensaje correspondiente

Este tipo de búsqueda es efectiva cuando el árbol está balanceado y hay pocos niveles

Ejemplo búsqueda a profundidad• Se busca la letra ‘j’• Se busca en la raíz • Se busca en los hijos de b• Se busca en los hijos de c

El recorrido para encontrar el nodo elegido es (a,b,e,f,g,c,h,l,m,n,i,j)

Generación de árbol por búsqueda a lo ancho

• Elegimos, de modo arbitrario, un nodo inicial a• Se añaden todos los nodos adyacentes a al nodo raíz

Generación de árbol por búsqueda a lo ancho

• Se analiza el siguiente nodo que alfabéticamente sigue y se añaden los nodos adyacentes que aún no están en el árbol

Generación de árbol por búsqueda a lo ancho

• Cómo a y b ya no tienen nodos adyacentes se inspecciona el nodo que sigue alfabéticamente (c) y se agregan los nodos adyacentes necesarios

Generación de árbol por búsqueda a lo ancho

• Se analizan d y e pero ambos no tienen nodos adyacentes que agregar.

• Se analiza f y se agrega como nodo adyacente a i

Generación de árbol por búsqueda a profundidad

• Se elige un nodo arbitrario a como raíz• Construimos un camino tan largo como sea

posible(cuando un nodo tiene 2 hijos se elige el de menor valor)

• Verificamos si d tiene nodos no visitados que sean adyacentes

• Regresamos a e y vemos que tiene un nodo adyacente no visitado f

Generación de árbol por búsqueda a profundidad

Generación de árbol por búsqueda a profundidad

• Verificamos si f tiene nodos adyacentes no visitados y construimos el camino más largo posible

Generación de árbol por búsqueda a profundidad

• Verificamos si g no tiene adyacentes• Regresamos a f y como tiene otro adyacente no visitado

se construye el camino

Recorrido de un árbol • Los árboles con raíz se utilizan frecuentemente para

almacenar información. Por lo tanto se necesitan procedimientos que permitan visitar cada uno de los nodos.

• Existen tres maneras de recorrer un árbol (según la manera en que se coloca el padre con respecto a los hijos):• Recorrido en orden primero• Recorrido en orden segundo• Recorrido en orden final

Orden primero • Primero se toma el padre, luego el hijo izquierdo y al final

demás hijos • Se comienza por la raíz, después sigue el nodo de la

izquierda, si este nodo tiene hijos se sigue por el nodo de la izquierda hasta llegar a la hoja

• Después se continua con el siguiente hermano de la derecha y así sucesivamente

Orden segundo• Primero se toma el hijo izquierdo,luego el padre y al final

demás hijos • Se comienza por la raíz, después sigue el nodo de la

izquierda, si este nodo tiene hijos se sigue por el nodo de la izquierda hasta llegar a la hoja

• Después se continua con el siguiente hermano de la derecha y así sucesivamente

Orden final• En este recorrido se toma primero el hijo izquierdo,

después los demás hermanos y al final el padre.

Búsquedas• El árbol binario de búsqueda es aquel dónde cada hijo se

designa como un vértice izquierdo o derecho.• Cada vértice está etiquetado con una clave de modo de

modo que la clave es mayor de su subárbol izquierdo y menor que todos sus vértices de su subárbol derecho.

Ejemplo• Construye un árbol binario de búsqueda para las palabras

matemáticas, paleontología, geografía, zoología, meteorología, geología, psicología y cosmología

• Paso 1: Se toma la primera palabra como raíz • Paso2: Se compara la siguiente palabra con la raíz y si es

mayor se coloca como nodo derecho y si es menor como nodo izquierdo

Ejemplo

RecorridosPrimero: 30,-10,3,-7,4,3,9,7,6,68,50,30,31,56,58,72,98Segundo: -10,-7,3,3,4,6,7,9,30,30,31,50,56,58,68,72,98Final: -7,3,6,7,9,4,3,-10,31,30,58,56,50,98,72,68,30

Ejemplo• Crea un árbol de búsqueda binaria con la siguiente

información: 30, -10,3,4,9,68,50,30,3,7,6,72,98,-7,56,31,58

Referencias

• Kenneth H. Rosen, Matemática Discreta y sus Aplicaciones, Quinta Edición, McGrawHill

• Jiménez , José A, Matemáticas para la Computación , Primer Edición, Alfaomega Grupo Editor

Gracias!!!

ÁRBOLESMatemáticas Discretas

MISTI