REPUBLICA BOLIVARIANA DE VENEZUELA

REPUBLICA BOLIVARIANA DE VENEZUELA

UNIVERSIDAD BICENTENARIA DE ARAGUA

ESCUELA DE INGENIERIA DE SISTEMAS

NUCLEO - APURE

PROFESORA: ALUMNA:Ana Virginia Padrino. Rodriguez Yudesky.

C. I 19.816.752.

III Semestre K.

BIRUACA, FEBRERO DE 2008.

TABLA DE CONTENIDO

INTRODUCCIN.

Grafos. Composicin de los grafos.

Grafos no dirigibles.

Trminos bsicos de los grafos no dirigibles: adyacente, ciclo, rbol libre, camino, grafos conectados.

Grafos dirigibles

Mtodos para representar un grafo como una estructura de datos

Representacin en conjunto

Tablas de adyacencias

Aplicaciones de grafos

rboles generales

rboles binarios

Formas de almacenamiento de un rbol binario

Recorrido de rboles

Tipos de recorridos: post-orden, pre-orden

rboles de bsqueda binaria

Ejemplo de bsqueda de un elemento

Aplicaciones de rboles rbol binario heap CONCLUSIN.

BIBLIOGRAFIA.

INTRODUCCIN

Hoy en da podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, lneas telefnicas, lneas de televisin por cable, el transporte colectivo metro, circuitos elctricos de nuestras casas, automviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemticas se denomina como grafos.

En este trabajo se tratar de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, as como su representacin grfica y en algunos casos, su representacin en algn programa informtico, as como en la memoria. Tambin estudiaremos los rboles, tipos, sus aplicaciones, entre otros.En el mismo, se ha explicando de manera muy sencilla los conceptos y algunas metodologas con un lenguaje no tan rebuscado para su mayor entendimiento.

GRAFOS

Un grafo es un objeto matemtico que se utiliza para representar circuitos, redes, etc. Los grafos son muy utilizados en computacin, ya que permiten resolver problemas muy complejos.

Tambin se puede decir que son la representacin natural de las redes, en las que estamos cada vez ms incluidos.

Ejemplo:

En la figura, V = {a, b, c, d, e, f}, y A = {ab, ac, ae, bc, bd, df, ef}.

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vrtices, y A es el conjunto de aristas, este ltimo es un conjunto de subconjuntos de la forma (u,v) tal que , tal que . Para simplificar, notaremos la arista {a,b} como ab.

COMPOSICION DE LOS GRAFOSUn grafo est compuesto por dos conjuntos:

Un conjunto V de puntos llamados vrtices o nodos.

Un conjunto de pares de vrtices que se llaman aristas o arcos y que indican qu nodos estn relacionados.

De una manera ms informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.

GRAFOS NO DIRIGIBLESUn grafo no dirigido de define como un grafo donde los pares de vrtices estn desordenados. Por desordenados, se entiende que las aristas en un grafo no dirigido no tienen un vrtice origen ni un vrtice destino.

Grafos no dirigidos En estos grafos, las aristas que comunican dos nodos tienen dos sentidos. Si una arista va de x a y, la misma arista va de y a x. Se expresa grficamente por lneas. La representacin grfica de un grafo se define con un crculo o rectngulo para los nodos y las relaciones con lneas o flechas segn sea un grafo no dirigido o un dgrafo, respectivamente.

GRAFOS DIRIGIBLESUn grafo dirigido es definido como aquel donde los pares de vrtices son ordenados. Por ordenados, se entiende que cada arista en un grafo dirigido tiene un vrtice origen y un vrtice destino.Ejemplos:

V = {v1,v2,v3,v4,v5} E = { {v1,v2}, {v1,v3}, {v1,v5}, {v2,v3}, {v3,v4}, {v4,v5} } V = {v1,v2,v3,v4} E = { (v1,v2), (v2,v2), (v2,v3), (v3,v1), (v3,v4), (v4,v3) }

Adems de esto, los grafos pueden ser extendidos mediante la adicin de rtulos (labels) a los arcos. Estos rtulos pueden representar costos, longitudes, distancias, pesos, etc.

TERMINOS BASICOS DE LOS GRAFOS NO DIRIGIBLES:

Adyacente: Si existe una arista entre dos vrtices, por ejemplo, p y q, entonces se dice que son vrtices adyacentes. Ciclo: un ciclo se define como un camino que contiene un nmero n de vrtices, colocados de forma que el vrtice 1 es adyacente al vrtice 2, el vrtice 2 es adyacente al vrtice 3, el vrtice n-1 es adyacente al vrtice n y finalmente el vrtice n es adyacente al vrtice 1. rbol libre: un rbol libre es grafo no dirigido que no tiene ciclos. Camino: un camino es un conjunto de una secuencia de vrtices adyacentes distintos. Grafos conectados: un grafo conectado es aquel donde existe un camino de cualquier vrtice en el grafo hacia cualquier otro vrtice.LOS METODOS PARA REPRESENTAR UN GRAFO COMO UNA ESTRUCTURA DE DATOSExisten diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las caractersticas del grafo y el algoritmo usado para manipularlo. Tericamente se pueden distinguir las estructuras de listas y las de matrices, pero usualmente, lo mejor es una combinacin de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rpido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista:

Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido) de vrtices que conecta esa arista.

Lista de adyacencia - Cada vrtice tiene una lista de vrtices los cuales son adyacentes a l. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las bsquedas son ms rpidas, al costo de almacenamiento extra.

Estructuras matriciales: Matriz de incidencia - El grafo est representado por una matriz de A (aristas) por V (vrtices), donde [arista, vrtice] contiene la informacin de la arista (1 - conectado, 0 - no conectado)

Matriz de adyacencia - El grafo est representado por una matriz cuadrada M de tamao n, donde n es el nmero de vrtices. Si hay una arista entre un vrtice x y un vrtice y, entonces el elemento mx,y es 1, de lo contrario, es 0. DENTRO DE LO METODOS (mas comunes)

Representacin en conjunto: Un mtodo para representar un grafo es usando conjuntos, es mantener dos conjuntos diferentes., como ya se menciono anteriormente. Otro mtodo es tener solo un conjunto, que en efecto, proporciona la misma informacin que los dos conjuntos diferentes.

Tablas de adyacencias: La primera forma es por medio de una matriz de adyacencias tambin llamada listas de adyacencias, con este mtodo se tiene una matriz de tamao nxn, donde n es el numero de vrtices o nodos en el grafo. Una forma simple de ver la informacin guardada en dicha matriz es que los renglones de las mismas representan el origen y las columnas el destino de cada arista o arco en el grafo. Si el grafo es no ponderado se acostumbra poner un cero en el (rengln i, columna j) de la matriz cuando no existe dicho arco y un uno cuando dicho arco existe en el grafo. En el caso de grafos ponderados, se acostumbra poner una bandera (normalmente el valor de infinito) en las posiciones donde no existe un arco y el peso correspondiente en las posiciones donde si existe.

Ejemplos:

APLICACIONES DE GRAFOSLos grafos se pueden usar para representar redes de camino. En general, se pueden usar para representar cualquier ruta de viaje, ya sea por tierra, mar, o aire. Los algoritmos de grafos se pueden usar para determinar si un camino de viaje existe desde un origen a un destino, Adems, se puede calcular el camino mas corto desde un origen a un destino usando algoritmos grafos.RBOLES GENERALES

Un rbol general (a veces es llamado rbol) se define como un conjunto, finito no vaci T de elementos, llamados nodos, tales que: 1. T contiene un elemento distinguido R, llamado raz de T.

2. Los restantes elementos de T forman una coleccin ordenada de cero o mas rboles disjuntos T1, T2,.., Tm...

Ejemplo:

RBOLES BINARIOSUn rbol binario es un rbol con raz en el que cada nodo tiene como mximo dos hijos.

En ciencias de la computacin, un rbol binario es una estructura de datos en el cual cada nodo:

No tiene hijos (hoja).

Tiene un hijo izquierdo y un hijo derecho.

Tambin se puede decir que Un rbol binario es una estructura recursiva. Cada nodo es la raz de su propio subrbol y tiene hijos, que son races de rboles llamados los subrboles derecho e izquierdo del nodo, respectivamente. Un rbol binario se divide en tres subconjuntos disjuntos:

{R} Nodo raiz.

{I1, I2,. . ., IN} Subrbol izquierdo de R.

{D1, D2,. . ., DN} Subrbol derecho de R.

Un rbol binario sencillo de tamao 9 y altura 3, con un nodo raz cuyo valor es 2.

Ventajas:

Se necesita uso de pilas para el recorrido.

Sencillez de mantenibilidad y reusabilidad.

Desventajas:

Es difcil construir un rbol binario de bsqueda perfectamente equilibrado.

El nmero de consultas aumenta rpidamente con el nmero de registros a ordenar

FORMA DE ALMACENAMIENTO DE UN ARBOL BINARIOLos rboles binarios pueden ser construidos a partir de lenguajes de programacin de varias formas. En un lenguaje con registros y referencias, los rboles binarios son construidos tpicamente con una estructura de nodos Y punteros en la cual se almacenan datos, cada uno de estos nodos tienen una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos. En ocasiones, tambin contiene un puntero a un nico nodo. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden ser definidos como nulos para indicar que no dispone de dicho nodo.RECORRIDO DE RBOLESEn todos estos casos deben hacerse cdigo para imprimir por pantalla el contenido de los nodos y para guardarlo en una lista, que ser impresa posteriormente. En el ltimo caso los elementos de la lista deben corresponder, secuencialmente, al recorrido del rbol.

Realizar recorridos en preorden, inorden y postorden de un rbol

Realizar un recorrido en anchura (por niveles) de un rbol, empezando por el nivel superior.

Realizar un recorrido en anchura (por niveles) de un rbol, empezando por el nivel inferior.

TIPOS DE RECORRIDO: inorden, pos orden, preorden, ejemplos de cada uno:

El recorrido en preorden, tambin llamado orden previo consiste en recorrer en primer lugar la raz y luego cada uno de los hijos en orden previo.

El recorrido en inorden, tambin llamado orden simtrico (aunque este nombre slo cobra significado en los rboles binarios) consiste en recorrer en primer lugar A1, luego la raz y luego cada uno de los hijos en orden simtrico.

El recorrido en postorden, tambin llamado orden posterior consiste en recorrer en primer cada uno de los hijos en orden posterior y por ltimo la raz.

Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o a nivel. Puesto que los rboles no son secuenciales como las listas, hay que buscar estrategias alternativas para visitar todos los nodos.

- Recorridos en profundidad:

* Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave del nodo por pantalla), y despus visitar el subrbol izquierdo y una vez visitado, visitar el subrbol derecho.Si se hace el recorrido en preorden del rbol de la figura 1 las visitas seran en el orden siguiente: a,b,d,c,e,f.

void preorden(tarbol *a)

{

if (a != NULL) {

Visitar(a);

Preorden(a->izq);

Preorden(a->der);

}

}

* Recorrido en inorden u orden central: se visita el subrbol izquierdo, el nodo actual, y despus se visita el subrbol derecho. En el ejemplo de la figura 1 las visitas seran en este orden: b,d,a,e,c,f.void inorden(tarbol *a)

{

if (a != NULL) {

Inorden(a->izq);

Visitar(a);

Inorden(a->der);

}

}

* Recorrido en postorden: se visitan primero el subrbol izquierdo, despus el subrbol derecho, y por ltimo el nodo actual. En el ejemplo de la figura 1 el recorrido quedara as: d,b,e,f,c,a.

void postorden(arbol *a)

{

if (a != NULL) {

Postorden(a->izq);

Postorden(a->der);

Visitar(a);

}

}

La ventaja del recorrido en postorden es que permite borrar el rbol de forma consistente. Es decir, si visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrar el rbol o subrbol que se pasa como parmetro. La razn para hacer esto es que no se debe borrar un nodo y despus sus subrboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la regla de manipular una estructura de datos inexistente. Una alternativa es utilizar una variable auxiliar, pero es innecesario aplicando este recorrido.RBOLES DE BUSQUEDA BINARIADefinicin:Un rbol es una estructura de datos recursiva que se puede caracterizar en forma inductiva:

El rbol vaco es un rbol.

Un nodo del cual cuelgan uno ms rboles es un rbol.

Esta seccin discute una de las estructuras de datos ms importantes de la informtica, el rbol binario de bsqueda. Esta estructura permite buscar y encontrar un elemento con una media de tiempo de ejecucin f (n) = 0 ( log2 n), tambin permite insertar y borrar elementos fcilmente. Esta estructura contrasta con las siguientes estructuras:

a. Array lineal ordenado. Aqu se puede buscar y encontrar un elemento con un tiempo de ejecucin f(n) = (log2n), pero es costoso el insertar y borrar elementos.

b. Lista enlazada. Aqu se puede insertar y borrar elementos fcilmente, pero es costoso el buscar y encontrar un elemento, ya que se debe usar una bsqueda secuencial.

Aunque cada nodo de un rbol binario de bsqueda puede contener un registroentero de datos, la definicin del rbol binario depende de un campo dado cuyos valores son distintos y deben estar ordenados.

Supongamos que T es un rbol binario. Entonces T se dice que es un rbol binario de bsqueda ( o rbol binario ordenado) si cada nodo N de T tiene la siguiente propiedad: el valor de N es mayor que cualquier valor del subrbol izquierdo de N y es menor que cualquier valor del subrbol derecho de N. ( no es difcil ver que esta propiedad garantiza el recorrido inorden de T dar una lista ordenada de los elementos de T) .

EJEMPLO DE BUSQUEDA DE UN ELEMENTO

La bsqueda binaria es un algoritmo de bsqueda.

Para realizarla, es necesario contar con un array o vector ordenado. Luego tomamos un elemento central, normalmente el elemento que se encuentra a la mitad del arreglo, y lo comparamos con el elemento buscado. Si el elemento buscado es menor, tomamos el intervalo que va desde el elemento central al principio, en caso contrario, tomamos el intervalo que va desde el elemento central hasta el final del intervalo.

Procedemos de esta manera con intervalos cada vez menores hasta que lleguemos a un intervalo indivisible, en cuyo caso el elemento no est en el vector, o el elemento central sea nuestro elemento.

De esta forma la complejidad computacional se reduce a O (ln N).

El algoritmo se puede implementar con o sin recursin, a continuacin se presenta una versin iterativa en Lenguaje C:

) Inicio = medio+1; else final = medio-1;}return -1;}

Y aqu mostramos una versin recursiva del mismo algoritmo:

) Return bbin (dato, v, medio+1, final) ;}.

APLICACIONES DE RBOLES

Supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situacin es bastante til en el manejo de las bases de datos, para evitar un problema que se llama redundancia.

Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene elementos, se deben hacer comparaciones, claro, no es mucho problema si es un nmero pequeo, pero el problema se va complicando ms a medida que aumenta.

Si usamos un rbol binario, el nmero de comparaciones se reduce bastante, veamos cmo.

El primer nmero del arreglo se coloca en la raz del rbol (como en este ejemplo siempre vamos a trabajar con rboles binarios, simplemente diremos rbol, para referirnos a un rbol binario) con sus subrboles izquierdo y derecho vacos. Luego, cada elemento del arreglo se compara son la informacin del nodo raz y se crean los nuevos hijos con el siguiente criterio:

Si el elemento del arreglo es igual que la informacin del nodo raz, entonces notificar duplicidad.

Si el elemento del arreglo es menor que la informacin del nodo raz, entonces se crea un hijo izquierdo.

Si el elemento del arreglo es mayor que la informacin del nodo raz, entonces se crea un hijo derecho.

Una vez que ya est creado el rbol, se pueden buscar los elementos repetidos. Si x el elemento buscado, se debe recorrer el rbol del siguiente modo:

Sea k la informacin del nodo actual p. Si entonces cambiar el nodo actual a right(p), en caso contrario, en caso de que informar una ocurrencia duplicada y en caso de que cambiar el nodo actual a left(p).

El siguiente algoritmo

Leer numero buscado >> n

tree=makeTree(n)

while(hay numeros en el arreglo){

leeSiguienteNumero >> k

p=q=tree;

while(k!=info(p)&&q!=NULL){

p=q

if(k