miércoles, 13 de julio de 2011

Grafos

Aquí un poco de información acerca de los grafos!

Empezamos con la definición… Un grafo se define como un conjunto de puntos, o vértices, que están conectados por un conjunto de líneas, o aristas. Los vértices son objetos que contienen información y las aristas son las conexiones entre esos vértices. Son muy utilizados en computación por que permiten resolver problemas muy complejos.

Hay dos tipos de grafos, los dirigidos y no dirigidos:

  • No dirigidos:son aquellos en los cuales los lados no están orientados, o sea, no son flechas. Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (Vi,Vj)=(Vj,Vi).

            

  • Dirigidos:son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice origen, se conoce como la cola del lado y B, el cual es el vértice destino, se conoce como cabeza del lado.

           

Grafos bipartitos:un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro:  

  • V_1 \cup V_2 = V
  • V_1 \cap V_2 = \empty
  • \forall x_1,x_2 \in V_1, \forall y_1,y_2 \in V_2

Ejemplo de grafos Bipartitos:

Un grafo bipartido completo si V=V1yV2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,s al grafo bipartido completo donde V1 tiene r vértices yV2 tiene s vértices.

Los grafos bipartitos suelen representarse gráficamente con dos columnas (o filas) de vértices y las aristas uniendo vértices de columnas (o filas) diferentes.

Gafos bipartitos completos:

****************************************************************************************************

Árboles

Los árboles son estructuras de datos que se pueden definir de forma recursiva como una estructura vacía o un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, llamados subárboles.

En cuanto a grafos, un árbol es un grafo acíclico, conexo y no dirigido, o sea un grafo no dirigido en el que existe un camino entre cualquier par de nodos.

En los árboles: la raíz es aquel elemento que no tiene antecesor; una rama es una arista entre dos nodos; un nodo x es antecesor de un nodo y si por alguna de las ramas de x se puede llegar a y; un nodo x es sucesor de un nodo y si por alguna de las ramas de y se puede llegar a x; el grado de un nodo es el número de descendientes directos que tiene; una hoja es un nodo que no tiene descendientes; el nivel es el número de ramas que hay que recorrer para llegar a la raíz de un nodo; la altura es el nivel más alto del árbol;  por último, la anchura es el mayor valor del número de nodos que hay en un nivel.

Así se ve un árbol binario:

A es la raíz; G, H, I, K, son hojas.

Un árbol binario de búsqueda auto-balanceable es un árbol de búsqueda binaria que que intenta mantener su altura, tan pequeña como sea posible en todo momento de forma automática. Esto se realiza por lo general realizando transformaciones en el árbol, como la rotación de árboles.

Aquí una lista de tiempos asintóticos en términos de nodos en algún árbol n:

  • Para búsqueda, O(log n)
  • Para inserción, O(log n)
  • Para eliminación, O(log n)
  • Para iteración en orden, O(n)

Una liga para un código en C de árbol binario: http://www.elrincondelc.com/nuevorincon/index.php?pag=codigos&id=4

Hay dos estructuras de datos populares que implementan este tipo de datos:

  • Árbol AVL: es un árbol binario de búsqueda que cumple con la condición de que la diferencia en las alturas de los subárboles de cada uno de sus nodos es máximo 1. El nombre viene de sus creadores, Adelson-Velskii y Landis. La propiedad de equilibrio que debe cumplir un árbol para ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las  operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. El tiempo de ejecución de las operaciones sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.

     Este es un árbol binario no equilibrado, o sea que no es AVL                

 

 

 

        Este es un árbol binario equilibrado, o sea que si es AVL.

Un ejemplo de operación que se pueden hacer con estos árboles son las rotaciones, en las cuales el reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden ser simples o dobles, y a la derecha o a la izquierda.

Aquí muestro un ejemplo de rotación simple a la derecha:

  • De un árbol de raíz (y) y de hijos izquierdo (x) y derecho (c), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de x (a) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (y), el hijo derecho de x (b) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (c).

Así se vería gráficamente:

Aquí unos ejemplos de árboles AVL en C: http://c.conclase.net/edd/?cap=008e

  • Árbol rojo-negro: es un tipo de árbol que está balanceado de tal manera que el tiempo de realizar operaciones sea O(log n) en el peor de los casos. En estos el nodo contiene un campo extra el cual llamamos color, y el árbol se recorre ya sea por color rojo o negro. Cada nodo puede tener uno de estos colores. Cada apuntador de hoja es de color negro, y cada camino desde cualquier nodo hasta una hoja contiene el mismo numero de nodos negros.

Un ejemplo:

El método de rotación es básicamente el mismo que se usa en los árboles AVL.

Aquí una página con diferentes operaciones en código C que se pueden hacer en con el árbol rojo-negro. Está en inglés.

Referencias: 

Publicado por en

1 comentario:

Suscribirse a: Enviar comentarios (Atom)