MAESTRO:

PRESENTAN:

MATERIA: ESTRUCTURA DE DATOS

TRABAJO:
UNIDAD 4 ESTRUCTURAS NO LINEALES

FECHA DE ENTREGA:

INDICE Contenido
INDICE.................................................................................................................................................. 2 INTRODUCCION ................................................................................................................................... 2 OBJETIVO ............................................................................................................................................. 3 ESTRUCTURAS NO LINEALES ARBOLES Y GRAFOS ............................................................................... 5 ESTRUCTURAS NO LINEALES: ARBOLES............................................................................................... 5 CLASIFICACIN DE ARBOLES ............................................................................................................... 9 RBOL BINARIO DE BSQUEDA ...................................................................................................... 9 APLICACIONES DE RBOLES BINARIOS.............................................................................................. 10 ESTRUCTURAS NO LINEALES: GRAFOS .............................................................................................. 11 CLASIFICACIN DE GRAFOS............................................................................................................... 12 OPERACIONES SOBRE GRAFOS.......................................................................................................... 13 IMPLEMENTACIN DE EL TDA GRAFO. ............................................................................................. 14 LISTA DE PRIMITIVAS. ................................................................................................................ 14 IMPLEMENTACIN DE LAS PRIMITIVAS. ................................................................................... 15 CONCLUSIONES ................................................................................................................................. 21 GLOSARIO .......................................................................................................................................... 22 REFERENCIAS ..................................................................................................................................... 22

INTRODUCCION
2

El siguiente trabajo trata sobre la estructura de datos no lineales llamada rbol. Esta estructura se usa principalmente para representar datos con una relacin jerrquica entre sus elementos, como por ejemplo registros, rboles genealgicos, y tablas de contenidos. Vamos a profundizar en un tipo especial de rbol llamado rbol binario, la cual puede ser implementada fcilmente en la computadora; aunque en un rbol puede parecer muy restrictivo. Entre estos tenemos a la terminologa, los rboles binarios complementos, rboles binarios de bsqueda, bsqueda e insercin en rboles binarios de bsqueda, rboles generales, representacin de rboles generales en la computadora y correspondencia entre los rboles generales y rboles binarios. 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.

OBJETIVO

El objetivo del siguiente trabajo es definir el concepto de las estructuras no lineales los arboles y grafos. Para que el concepto de cada uno de ellos quede resuelto, as como para que se usen y de que forma pueden aplicarse en la vida cotidiana, tambin se va a ampliar sobre rboles ms generales y puntos con relacin a los rboles binarios; y la relacin que tienen los arboles con los grafos.

ESTRUCTURAS NO LINEALES ARBOLES Y GRAFOS ESTRUCTURAS NO LINEALES: ARBOLES

En ciencias de la computacin, un rbol es una estructura de datos ampliamente usada que emula la forma de un rbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el rbol y puede tener cero o mas nodos hijos conectados a l. Se dice que un nodo a es padre de un nodo b, si existe un enlace desde a hasta b (en ese caso, tambin decimos que b es hijo de a). Slo puede haber un nico nodo sin padres, que llamaremos raz. Un nodo que no tiene hijos se conoce como hoja. El rbol Tambin se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relacin jerrquica entre sus elementos, como por ejemplo registros, rboles genealgicos y tablas de contenidos. Entre otros tenemos un tipo especial de rbol que es, llamado rbol binario, que puede ser implementado fcilmente en la computadora. Un rbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. Tambin se suele dar una definicin recursiva: un rbol es una estructura en compuesta por un dato y varios rboles. Esto son definiciones simples. Pero las caractersticas que implican no lo son tanto.

Definiremos varios conceptos. En relacin con otros nodos:

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del rbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
5

Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Los rboles con los que trabajaremos tienen otra caracterstica importante: cada nodo slo puede ser apuntado por otro nodo, es decir, cada nodo slo tendr un padre. Esto hace que estos rboles estn fuertemente jerarquizados, y es lo que en realidad les da la apariencia de rboles. En cuanto a la posicin dentro del rbol:

Nodo raz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al rbol. En el ejemplo, ese nodo es el 'A'. Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'. Nodo rama: aunque esta definicin apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categoras anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Otra caracterstica que normalmente tendrn nuestros rboles es que todos los nodos contengan el mismo nmero de punteros, es decir, usaremos la misma estructura para todos los nodos del rbol. Esto hace que la estructura sea ms sencilla, y por lo tanto tambin los programas para trabajar con ellos. Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo. Un rbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama rbol completo. En una cosa, los rboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raz de un rbol completo. Existen otros conceptos que definen las caractersticas del rbol, en relacin a su tamao:

Orden: es el nmero potencial de hijos que puede tener cada elemento de rbol. De este modo, diremos que un rbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres ser de orden tres, etc. Grado: el nmero de hijos que tiene el elemento con ms hijos dentro del rbol. En el rbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con ms de tres hijos.

Nivel: se define para cada elemento del rbol como la distancia a la raz, medida en nodos. El nivel de la raz es cero y el de sus hijos uno. As sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. Altura: la altura de un rbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un rbol puede considerarse a su vez como la raz de un rbol, tambin podemos hablar de altura de ramas. El rbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

Los rboles de orden dos son bastante especiales, de hecho les dedicaremos varios captulos. Estos rboles se conocen tambin como rboles binarios. Frecuentemente, aunque tampoco es estrictamente necesario, para hacer ms fcil moverse a travs del rbol, aadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en direccin a la raz, y no slo hacia las hojas. Es importante conservar siempre el nodo raz ya que es el nodo a partir del cual se desarrolla el rbol, si perdemos este nodo, perderemos el acceso a todo el rbol. El nodo tpico de un rbol difiere de los nodos que hemos visto hasta ahora para listas, aunque slo en el nmero de nodos. Veamos un ejemplo de nodo para crear rboles de orden tres: struct nodo \{ int dato; struct nodo *rama1; struct nodo *rama2; struct nodo *rama3; }; O generalizando ms: #define ORDEN 5 struct nodo \{ int dato; struct nodo *rama[ORDEN]; };

Para C, y basndonos en la declaracin de nodo que hemos visto ms arriba, trabajaremos con los siguientes tipos: typedef struct _nodo \{ int dato; struct _nodo *rama[ORDEN]; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Arbol; Al igual que hicimos con las listas que hemos visto hasta ahora, declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo para es el tipo para declarar punteros a un nodo. Arbol es el tipo para declarar rboles de orden ORDEN.

El movimiento a travs de rboles, salvo que implementemos punteros al nodo padre, ser siempre partiendo del nodo raz hacia un nodo hoja. Cada vez que lleguemos a un nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al siguiente nodo. En general, intentaremos que exista algn significado asociado a cada uno de los punteros dentro de cada nodo, los rboles que estamos viendo son abstractos, pero las aplicaciones no tienen por qu serlo. Un ejemplo de estructura en rbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de rboles con nodos de dos tipos, nodos directorio y nodos fichero, podramos considerar que los nodos hoja son ficheros y los nodos rama son directorios. Otro ejemplo podra ser la tabla de contenido de un libro, por ejemplo de este mismo curso, dividido en captulos, y cada uno de ellos en subcaptulos. Aunque el libro sea algo lineal, como una lista, en el que cada captulo sigue al anterior, tambin es posible acceder a cualquier punto de l a travs de la tabla de contenido.
8

Tambin se suelen organizar en forma de rbol los organigramas de mando en empresas o en el ejrcito, y los rboles genealgicos.

CLASIFICACIN DE ARBOLES
Clasificacin de arboles binarios: 1.-arbol binario distinto: Se dice que un rbol es distinto cuando su estructura grafica es diferente. 2.-arbol binario similar.- Se dice que un rbol es similar cuando su estructura grafica es idntica pero la informacin que contiene entre sus nodos es diferente. 3.-arbol binario equivalente.-Son aquellos que su estructura grafica es idntica pero adems la informacin entre sus nodos. 4.-arbol binario completo.-son aquellos que todos nos nodos excepto el ultimo nivel tienen sus dos hijos. 5.-arbol binario lleno: es aquel que tiene su nmero mximo de posibles nodos. Se define un rbol binario como un conjunto finito de elementos (nodos) que bien esta vaco o esta formado por una raz con dos arboles binarios disjuntos, es decir, dos descendientes directos llamados subarbol izquierdo y subarbol derecho. Los rboles binarios (tambin llamados de grado 2) tienen una especial importancia. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

RBOL BINARIO DE BSQUEDA.

Los rboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave nica. Si el rbol est organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subarbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este rbol es un rbol binario de bsqueda.

APLICACIONES DE RBOLES BINARIOS

Un rbol binario es una estructura de datos til cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, 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 subrbol es 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:
10

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

ESTRUCTURAS NO LINEALES: GRAFOS

Las estructuras de datos no lineales se caracterizan por no existir una relacin de adyacencia, entre sus elementos, es decir, un elemento puede estar relacionado con cero, uno o ms elementos. La estructura no lineal de datos ms general es el grafo donde sus nodos pueden relacionarse de cualquier manera sin una relacin de orden predefinida. Entre las mltiples aplicaciones que tienen estas estructuras podemos mencionar: Para modelar diversas situaciones tales como: sistemas de aeropuertos, flujo de trfico, y responder a preguntas como: Qu tiempo es ms corto?, Cmo es ms barato?, o Qu camino es ms corto? Los grafos tambin son utilizados para realizar planificacin de actividades, tareas del computador, planificar operaciones en lenguaje de mquinas para minimizar tiempo de ejecucin. Qu tarea debo hacer primero?. Para representar circuitos elctricos, de aguas etc... , y preguntar, estn todas las componentes conectadas Un grafo est formado por un conjunto de nodos(o vrtices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos. TERMINOLOGA 1. 2. 3. 4. 5. 6. 7. 8. Al nmero de nodos del grafo se le llama orden del grafo. Un grafo nulo es un grafo de orden 0 (cero). Dos nodos son adyacentes si hay un arco que los une. En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A Camino es una secuencia de uno o mas arcos que conectan dos nodos. Un grafo se denomina conectado cuando existe siempre un camino que une dos nodos cualesquiera y desconectado en caso contrario. Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los nodos restantes. El camino de un nodo as mismo se llama ciclo.

11

CLASIFICACIN DE GRAFOS
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vrtices que representa un arco no est ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco est representado por un par ordenado de vrtices, de forma que y representan dos arcos diferentes.

Ejemplos G1 = (V1, A1) V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)} G3 = (V3, A3) V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> } Grficamente estas tres estructuras de vrtices y arcos se pueden representar de la siguiente manera: Algunos de los principales tipos de grafos son los que se muestran a continuacin:

Grafo regular: Aquel con el mismo grado en todos los vrtices. Si ese grado es k lo llamaremos k-regular.

12

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2regular y el tercero no es regular

Grafo bipartito: Es aquel con cuyos vrtices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vrtices pertenecientes al mismo conjunto

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

Grafo completo: Aquel con una arista entre cada par de vrtices. Un grafo completo con n vrtices se denota Kn. Un grafo bipartito regular: se denota Km, n donde m, n es el grado de cada conjunto disjunto de vrtices.

A continuacin ponemos los dibujos de K1, 2, K3, 3, y K2, 5

Grafo nulo: Se dice que un grafo es nulo cuando los vrtices que lo componen no estn conectados, esto es, que son vrtices aislados. Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunvoca (uno a uno), entre sus vrtices de tal forma que dos de estos quedan unidos por una arista en comn.

OPERACIONES SOBRE GRAFOS

El algoritmo de dijkstra calcula la ruta ptima desde un vrtice (x, vrtice origen) a todos los dems vrtices del grafo. Tiene como requisito que no existan longitudes/costes negativos. Se basa en la idea de la relajacin de aristas (edge relajacin), en la cual se mantiene informacin de cul es la mejor distancia conocida de cualquier vrtice al origen, y a medida que se va conociendo una distancia mejor desde el vrtice j al origen, se actualizan las mejores distancias conocidas a todos los vrtices adyacentes a j. en su desarrollo utiliza un enfoque
13

voraz: en un momento dado hay un conjunto de vrtices, que llamaremos s, de los cuales se conoce la ruta ptima al origen y adems son los ms cercanos a l (cuando se hallen las rutas ptimas del resto de vrtices ninguna tendr una longitud menor que las de los vrtices que estn en s). Del resto de los vrtices (conjunto s) no conocemos la ruta ptima, sino la mejor ruta encontrada hasta el momento (no tiene porqu ser la ptima). Se puede visualizar el algoritmo imaginando que en cada momento tenemos un crculo centrado en el origen que contiene los vrtices ms cercanos. En cada paso ampliamos el crculo incluyendo el vrtice de fuera ms cercano (ampliamos por crculos concntricos). En cada paso se halla el vrtice de s a menor distancia del origen y se obtiene su ruta ptima. Ese vrtice se elimina de s y pasa a formar parte de s. en este punto aplicamos la relajacin de aristas y actualizamos las mejores rutas de los vrtices que quedan en s. La clave para que ste algoritmo obtenga la solucin ptima reside en que el vrtice (llammosle u) de s que se debe incorporar a s tiene que ser uno para el cual su ruta ptima vaya directamente de u a un vrtice de s (llammosle v), y su ruta ptima no puede ser una donde se vaya de u a un vrtice w s ya que entonces (al no existir longitudes negativas), la ruta de u al origen.

IMPLEMENTACIN DE EL TDA GRAFO.

LISTA DE PRIMITIVAS.

Lista de primitivas para los grafos dirigidos:

Crear: Funcin que se encarga de crear un grafo vacio. Etiqueta: Funcin que devuelve la etiqueta asociada a un nodo en un grafo. Label: Funcin que devuelve la Label de un nodo en el grafo. LocalizaLabel: Esta funcin recibe el entero l (el label asociado a un nodo que se supone pertenece al grafo y nos devuelve el nodo asociado con esa label. ExisteArco: Funcin que devuelve 1 si existe un arco entre el nodo o y el nodo d en el grafo g, si no existe dicho arco devuelve 0. PrimerArco: Devuelve el primer arco que sale del nodo n en el grafo g, si no existe dicho primer arco devuelve Nulo. SiguienteArco: Funcin que devuelve el arco siguiente al arco a en el nodo n si no existe dicho arco devuelve Nulo. PrimerArcoInv: Devuelve el primer arco que entra en el nodo n en el grafo g. Si no existe dicho arco devuelve Nulo.
14

SiguienteArcoInv: Devuelve el siguiente arco tras a que entra en el nodo n, si no existe dicho arco devuelve Nulo. PrimerNodo: Devuelve el primer nodo del grafo G, si no existe devuelve nulo. SiguienteNodo: Devuelve el nodo siguiente en orden al nodo n en el grafo g. Si no existe devuelve nulo. NodoOrigen: Devuelve el nodo origen del arco a. NodoDestino: Devuelve el nodo destino del arco a. presentarGrafo: Escribe el grafo g en pantalla. NumeroNodos: Devuelve el numero de nodos de un grafo g. grafoVacio: Devuelve Nulo si el grafo esta vacio. EtiqArco: Funcion que devuelve la etiqueta asociada a un arco, es decir el peso del arco. InsertarNodo: Funcion que inserta un nodo nuevo en un grafo. InsertarArco: Funcion que se encarga de insertar un arco entre el nodo org y el dest en el grafo g, asociado al arco le podemos dar un valor. BorrarArco: Funcion que borra el arco existente entre los nodos org y dest. DesconectarNodo: Funcin que devuelve el grafo que se obtiene al eliminar un nodo de un grafo G. Todos los arcos que entran o salen del nodo a eliminar tambin desaparecen. Destruir: Funcin que destruye el grafo g liberando la memoria que ocupa. CopiarGrafo: Funcin que hace una copia del grafo g.

IMPLEMENTACIN DE LAS PRIMITIVAS.

tgrafo Crear(void) { tnodo aux; aux = (tnodo)malloc(sizeof(struct nodo)); if (aux == NULL) { error(\"Error en Crear.\"); } else { aux->nodo = 0; aux->etiq = NULL; aux->ady = NULL; aux->inc = NULL; aux->sig = NULL; return aux; } } tetiq Etiqueta(tnodo n, tgrafo g) { return(n->etiq); } int Label(tnodo n, tgrafo g) { return(n->nodo);

15

} tnodo LocalizaLabel(int l, tgrafo g) { tnodo n; int enc=0; for (n=g->sig; n!=NULL && !enc; ) { if (n->nodo == l) enc = 1; else n = n->sig; } return n; } int ExisteArco(tnodo o, tnodo { tarco a; d, tgrafo g)

a=o->ady; while (a!=NULL) { if ((a->origen==o) && (a->destino==d)) return 1; else a = a->sig; } return 0; } tarco PrimerArco(tnodo n, tgrafo g) { return(n->ady); } tarco SiguienteArco(tnodo n, tarco a, tgrafo g) { return(a->sig); } tarco PrimerArcoInv(tnodo n, tgrafo g) { return(n->inc); } tarco SiguienteArcoInv(tnodo n, tarco a, tgrafo g) { return(a->sig); } tnodo PrimerNodo(tgrafo g) { return(g->sig); } tnodo SiguienteNodo(tnodo n, tgrafo g) { return(n->sig); } tnodo NodoOrigen(tarco a, tgrafo g) { return(a->origen); } tnodo NodoDestino(tarco a, tgrafo g) {

16

return(a->destino); } void PresentarGrafo(tgrafo g) { tnodo n; tarco a; n=PrimerNodo(g); while (n!=Nulo) { a=PrimerArco(n,g); while (a!=Nulo) { printf(\"%s -> %s \",a->origen->etiq,a->destino->etiq); printf(\" (%f)\\n\",a->valor); a=SiguienteArco(n,a,g); } n=SiguienteNodo(n,g); } } int NumeroNodos(tgrafo g) { return(g->nodo); } int GrafoVacio(tgrafo g) { return(g->sig == NULL); } float EtiqArco(tnodo o, tnodo d, tgrafo g) { tarco a; a=o->ady; while (a!=NULL) { if ((a->origen == o) && (a->destino == d)) return (a->valor); else a = a->sig; } return 0; } void InsertarNodo(tetq dato, tgrafo g) { tnodo aux,p; aux = (tnodo)malloc(sizeof(struct nodo)); if (aux == NULL) error(\"Error Memoria Insuficiente.\"); else { p=g; while(p->sig != NULL) p = p->sig; aux->etiq = (char *)malloc(sizeof (char)*TE);"+ if (aux->etiq == NULL) error(\"Error Memoria Insuficiente.\"); aux->nodo = p->nodo+1; strcpy(aux->etiq,dato);+ aux->ady = NULL; aux->inc = NULL; aux->sig = NULL;

17

p->sig = aux; g->nodo++; } } void InsertarArco (tnodo org,tnodo dest,tvalor valor,tgrafo g) { tarco aux; tarco aux_inv; aux = (tarco)malloc(sizeof(struct arco)); aux_inv= (tarco)malloc(sizeof(struct arco)); if ((aux==NULL) || (aux_inv==NULL)) error("Memoria Insuficiente."); else { aux->origen = org; aux->destino = dest; aux->valor = valor; aux-> sig= org->ady; org->ady = aux; aux_inv->origen = org; aux_inv->destino = dest; aux_inv-> valor= valor; aux_inv-> sig= dest->inc; des_inc-> = aux_inv; } } void BorrarArco(tnodo org, tnodo dest, tgrafo g) { tarco a,ant; int enc=0; if (org->ady==NULL) return; else if (org->ady->destino==dest) { a = org->ady; org->ady = a->sig; free(a); } else { ant = org->ady; a = ant->sig; while (!enc && (a!=NULL)) { if (a->destino==dest) enc=1; else { a = a->sig; ant = ant->sig; } } if (a==NULL) return; else { ant->sig = a->sig; free(a); } } enc=0; if (dest->inc==NULL) return;

18

else if (dest->inc->origen==org) { a = dest->inc; dest->inc = a->sig; free(a); } else { ant = dest->inc; a = ant->sig; while (!enc && (a!=NULL)) { if (a->origen == org) enc=1; else { a = a->sig; ant = ant->sig; } } if (a==NULL) return; else { ant->sig = a->sig; free(a); } } } void Destruir(tgrafo G) { tnodo n; tarco a_aux; while (g->sig != NULL) { n = g->sig; while (n->ady != NULL) { a_aux = n->ady; n->ady = a_aux->sig; free(a_aux); } while (n->inc != NULL) { a_aux = n->inc; n->inc = a_aux->sig; free(a_aux); } g->sig = n->sig; free(n->etiq); free(n); } free(g); } tgrafo DesconectarNodo(tnodo a_eliminar,tgeafo g) { tgrafo g_nd; tnodo n; tnodo org;dst; tnodo o,d; tarco a; g_nd = Crear(); for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g)) InsertarNodo(Etiqueta(n,g),g_nd);

19

for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g)) for (a=PrimerArco(n,g); a!=NULL; a=SiguienteArco(n,a,g)) { org = NodoOrigen(a,g); dst = NodoDestino(a,g); if ((org!=a_eliminar) && dst!=a_eliminar)) { o = LocalizaLabel(Label(org,g), g_nd); d = LocalizaLabel(Label(dst,g), g_nd); InsertarArco(o,d,g_nd); } } return g_nd; }

tgrafo CopiarGrafo(tgrafo g) { tgrafo g_nd; tnodo n; tnodo org;dst; tnodo o,d; tarco a; int lb; g_nd = Crear(); for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g)) InsertarNodo(Etiqueta(n,g),g_nd); for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g)) for (a=PrimerArco(n,g); a!=NULL; a=SiguienteArco(n,a,g)) { org = NodoOrigen(a,g); dst = NodoDestino(a,g); o = LocalizaLabel(Label(org,g), g_nd); d = LocalizaLabel(Label(dst,g), g_nd); InsertarArco(o,d,g_nd); } } return g_nd; }

20

CONCLUSIONES
De este trabajo se podra decir que un rbol binario se define como un conjunto finito de elementos llamados nodos. En estos casos se puede usar terminologa de relaciones familiares para descubrir las relaciones entre los nodos de un rbol; y que un rbol puede ser implementado fcilmente en una computadora. De aqu se podra deducir que un grafo es bsicamente un objeto geomtrico aunque en realidad sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de lneas tomado de entre el conjunto de lneas que une cada par de vrtices. Por otro lado, y debido a su generalidad y a la gran diversidad de formas que pueden usarse, resulta complejo tratar con todas las ideas relacionadas con un grafo.

21

GLOSARIO
Nodo: En informtica, un nodo es un punto de interseccin o unin de varios elementos que confluyen en el mismo lugar. Por ejemplo: en una red de ordenadores cada una de las mquinas es un nodo, y si la red es Internet, cada servidor constituye tambin un nodo. rbol: Es una estructura de datos ampliamente usada que imita la forma de un rbol (un conjunto de nodos conectados) El algoritmo de dijkstra: Tambin llamado algoritmo de caminos mnimos, es un algoritmo para la determinacin del camino ms corto dado un vrtice origen al resto de vrtices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describi por primera vez en 1959.

REFERENCIAS

22

Grimm, J.: Deutsche Mythologie, traducido al ingls por J. S. Stallybrass (1882), vol. I, p. 116-118. Diccionario enciclopdico popular ilustrado Salvat (1906-1914) http://sistemas.ing.ula.ve/pr3/unidad_3/tema6/pdf/grafos.pdf http://www.monografias.com/trabajos36/arboles/arboles.shtml http://www.monografias.com/trabajos16/grafos/grafos.shtml

23