trabajo escrito sobre grafos

Upload: yesid-cortes

Post on 14-Oct-2015

21 views

Category:

Documents


0 download

TRANSCRIPT

TRABAJO ESCRITO SOBRE GRAFOS

EDGAR YESID CORTES INSUASTYDAVID ENRIQUE MAECHA

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDASFACULTAD INGENIERIASISTEMASVI SEMESTRECONSULTABOGOTA2014

TRABAJO ESCRITO SOBRE INDICE DE GRAFOS

EDGAR YESID CORTES INSUASTYDAVID ENRIQUE MAECHA

DOCENTEJULIO FLOREZ SANCHEZ

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDASFACULTAD INGENIERIASISTEMASVI SEMESTRECONSULTABOGOTA2014ContenidoINTRODUCCION8DEFINICION GRAFO9DEFINICION MULTIGRAFO9DEFINICION MATRIZ DE INCIDENCIA10DEFINICION MATRIZ DE ADYACENCIA10Aristas11Vrtices12Caminos12Grado de un grafo.13Grado de incidencia positivo13Grado de incidencia negativo.13Grado de un nodo13Ciclo de un grafo.13Ciclo.13Ciclo simple13Grafo regular13Grafo bipartito13Grafo completo.13Un grafo bipartito regular14Grafo nulo14Grafos Isomorfos14Grafos Platnicos14Grafos Eulerianos.14Grafos Conexos.14rboles.15Bosques de rboles.15Recorrido de un grafo.15Recorrido en anchura15Recorrido en profundidad15Representacin mediante matrices.16Representacin mediante listas16Representacin mediante matrices dispersas16Dgrafo (grafo dirigido).16Aplicaciones de los dgrafos16Aplicaciones de grafos y rboles17GRAFO DE EULER18CIRCUITO DE EULER18CAMINO HAMILTONIANO Y CIRCUITO HAMILTONIANO18REPRESENTACION EN MEMORIA18ISOMORFISMO DE GRAFOS19EJERCICIOS PROPUESTOS19BIBLIOGRAFIA21

INTRODUCCIONUn grafo en el mbito de las ciencias de la computacin es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (tambin llamados vrtices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemtico de grafo.Informalmente se define como G = (V, E), siendo los elementos de V los vrtices, y los elementos de E, las aristas (edges en ingls). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de VLa teora de grafos (tambin llamada teora de las grficas) es un campo de estudio de las matemticas y las ciencias de la computacin, que estudia las propiedades de los grafos (tambin llamadas grficas, que no se debe confundir con las grficas que tienen una acepcin muy amplia) estructuras que constan de dos partes, el conjunto de vrtices, nodos o puntos; y el conjunto de aristas, lneas o lados (edges en ingls) que pueden ser orientados o no.La teora de grafos es una rama de la Matemtica discreta y de las aplicadas, y es un tratado que usa diferentes conceptos de diversas reas como Anlisis combinatorio, lgebra abstracta, probabilidad, geometra de polgonos, aritmtica y topologa.Actualmente ha tenido mayor preponderancia en el campo de la informtica, las ciencias de la computacin y telecomunicaciones.Los grafos son solo abstracciones matemticas, pero son tiles en la prctica porque nos ayudan a resolver numerosos problemas importantes. Estas notas describen algunos de los algoritmos y mtodos ms conocidos para resolver problemas de procesamiento de grafos, as como proponen alternativas para la representacin de los mismos en el computador. Cada algoritmo o mtodo est acompaado de figuras que ilustran su funcionamiento y de una breve descripcin terica que incluye el estudio de la complejidad en tiempo del mismo. En adicin se incluye la descripcin de una taxonoma de clasificacin de problemas de procesamiento de grafos, basada en el grado de dificultad de lo mismos.

DEFINICION GRAFOUn grafo es un conjunto de nodos unidos por un conjunto de lneas o flechas. Por lo general, los nodos son entes de procesamiento o estructuras que contienen algn tipo de informacin y las lneas o flechas son conexiones o relaciones entre estos entes. Si se utilizan flechas para conectar los nodos decimos que el grafo es dirigido (tambin llamado digrafo) porque las relaciones entre los nodos tienen una direccin. En caso contrario el grafo es no dirigido. En cualquiera de los dos casos, bien sea que se utilicen lneas o flechas, a estas relaciones se les puede llamar simplemente aristas. Frecuentemente las aristas tambin tienen algn tipo de informacin asociada (distancia, costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado.DEFINICION MULTIGRAFOUn Multgrafo es cuando se acepta ms de un arco uniendo dos vrtices. En trminos formales, no son grafos. Un multgrafo es un grafo que consta de segmentos mltiples y lazos.Otra definicin similar es que un multgrafo es un grafo en el que hay pares de vrtices unidos por ms de una arista, es decir, que tiene aristas mltiples.Un multgrafo M se dice que es finito si tiene un nmero finito de nodos y de aristas. Observe que un grafo G con un nmero finito de nodos debe automticamente un nmero finito de aristas y por tanto debe ser finito. Pero esto no es cierto para un multgrafo M, ya que M puede tener mltiples aristas.vA menos que se indique lo contrario, los grafos y multgrafos de este texto siempre sern finitos. Un multgrafo es un grafo dirigido que est diseado para tener aristas mltiples, es decir, para tener aristas con los mismos nodos iniciales y finales. Un multgrafo G es un par ordenado de G = (V,A) donde: V es un conjunto de vrtices o nodos A es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas.Un pseudografo es un grafo en el que hay aristas o lazos que tienen el mismo extremo.Un dgrafo es un grafo donde a cada arista se le indica un sentido mediante una flecha. Los multidigrafos o pseudomultidigrafos son combinaciones de los otros tipos de grafos. Un multidigrafo mixto G = (V, E, A) tiene la misma definicin que un grafo mixto, es decir, tiene la capacidad de poseer al mismo tiempo las aristas dirigidas A y las aristas no dirigidas E.DEFINICION MATRIZ DE INCIDENCIAUna matriz de incidencia representa las relaciones binarias entre dos elementos,en nuestro caso entre un vrtice y una arista del grafo. Para construir la matriz de incidencia a partir de un grafo debemos realizar una matriz de n x a donde n es el n de nodos o vrtices y a es el n de aristas.En esta matriz las columnas representan las aristas y las filas los vrtices.Para cada A[i][j] ,ntese que A es la matriz de Incidencia, puede valer: 0 si vrtice i no es incidente con arista j 1 si vrtice i es incidente con arista jEjemplo:

DEFINICION MATRIZ DE ADYACENCIAUn grafo se puede representar mediante una matriz. Es la forma ms sencilla de representar un grafo. A esta matriz se le denomina matriz de adyacencia.Esta matriz consiste en un arreglo bidimensional de tamao n, donde n es la mxima cantidad de nodos en el grafo. Cada casilla de la matriz se carga con valores verdadero V o falso F en caso de que posea un camino de un nodo o fila con columna. En caso de los grafos no dirigidos la matriz ser simtrica.Esto no ocurre en los dgrafos, donde se considera la direccin de cada uno de los arcos. Para el caso de los grafos ponderados, la matriz podr ser cargada con el peso asociado a cada uno de los arcos.La ventaja principal es su simplicidad, dado que facilita las operaciones que puedan realizarse sobre el grafo. La desventaja es que se limita a un nmero mximo de nodos en el grafo, lo que provoca que sea imposible almacenar ms informacin en la matriz.Si la matriz es muy grande para representar un grafo pequeo, se desperdicia el espacio de almacenamiento de la matriz y de la memoria. Para un grafo no dirigido, el desperdicio ser mayor porque al ser simtrica la matriz, su informacin se duplicara.

AristasSon las lneas con las que se unen las aristas de un grafo y con la que se construyen tambin caminos.Si la arista carece de direccin se denota indistintamente {a, b} o {b, a}, siendo a y b los vrtices que une.Si {a ,b} es una arista, a los vrtices a y b se les llama sus extremos.Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vrtice.Aristas Paralelas: Se dice que dos aristas son paralelas si vrtice inicial y el final son el mismo.Aristas Cclicas: Arista que parte de un vrtice para entrar en el mismo.Cruce: Son dos aristas que cruzan en un punto.VrticesSon los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vrtice al nmero de aristas de las que es extremo. Se dice que un vrtice es `par' o `impar' segn lo sea su grado.Vrtices Adyacentes: si tenemos un par de vrtices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vrtices adyacentes y se dice que U es el vrtice inicial y V el vrtice adyacente.Vrtice Aislado: Es un vrtice de grado cero.Vrtice Terminal: Es un vrtice de grado 1.CaminosSean x, y " V, se dice que hay un camino en G de x a y si existe una sucesin finita no vaca de aristas {x,v1}, {v1,v2},..., {vn,y}. En este casox e y se llaman los extremos del caminoEl nmero de aristas del camino se llama la longitud del camino.Si los vrtices no se repiten el camino se dice propio o simple.Si hay un camino no simple entre 2 vrtices, tambin habr un camino simple entre ellos.Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.Llamaremos ciclo a un circuito simpleUn vrtice a se dice accesible desde el vrtice b si existe un camino entre ellos. Todo vrtice es accesible respecto a si mismoGrado de un grafo.Grado de incidencia positivo: El grado de incidencia positivo de un nodonjes el nmero de arcos que tienen como nodo inicial anj. Ejemplo: El grado de incidencia de 1 es igual a 3.Grado de incidencia negativo: El grado de incidencia negativo de un nodo es el nmero de arcos que terminan ennj. Ejemplo: El grado de incidencia negativo de 1 es igual a 1.Grado de un nodo: Paradigrafoses el grado de incidencia positivo menos el grado de incidencia negativo del nodo. Ejemplo: El grado de 1 es igual a 3 1 = 2, el grado del nodo 4 es 2 2 = 0. Para grafos no dirigidos es el nmero de lneas asociadas al nodo.Ciclo de un grafo.Ciclo: Es una cadena finita donde el nodo inicial de la cadena coincide con el nodo terminal de la misma.Ciclo simple: Es el ciclo que a su vez es una cadena simple.Grafo regular: Aquel con el mismo grado en todos los vrtices. Si ese grado es k lo llamaremos k-regular. Grafo bipartito: Es aquel con cuyos vrtices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vrtices pertenecientes al mismo conjuntoGrafo 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.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.Grafos Platnicos: Son los Grafos formados por los vrtices y aristas de los cinco slidos regulares (Slidos Platnicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.Grafos Eulerianos.Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera ms sencilla como un camino que contiene todos los arcos del grafo.Teniendo esto definido podemos hablar de los grafos eulerianos describindolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imgenes:El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.Grafos Conexos.Un grafo se puede definir como conexo si cualquier vrtice V pertenece al conjunto de vrtices y es alcanzable por algn otro. Otra definicin que dejara esto ms claro sera: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une". rboles.Un rbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo tambin acclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos).Bosques de rboles.Los bosques de rboles son un caso similar a los rboles, son acclicos, pero no son conexos. Como ejemplo tenemos la siguiente figura.Recorrido de un grafo.Recorrer un grafo significa tratar de alcanzar todos los nodos que estn relacionados con uno que llamaremos nodo de salida. Existen bsicamente dos tcnicas para recorrer un grafo: el recorrido en anchura; y el recorrido en profundidad.Recorrido en anchura: El recorrido en anchura supone recorrer el grafo, a partir de un nodo dado, en niveles, es decir, primero los que estn a una distancia de un arco del nodo de salida, despus los que estn a dos arcos de distancia, y as sucesivamente hasta alcanzar todos los nodos a los que se pudiese llegar desde el nodo salida.Recorrido en profundidad: el recorrido en profundidad trata de buscar los caminos que parten desde el nodo de salida hasta que ya no es posible avanzar ms. Cuando ya no puede avanzarse ms sobre el camino elegido, se vuelve atrs en busca de caminos alternativos, que no se estudiaron previamente.Hay tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.Representacin mediante matrices: La forma ms fcil de guardar la informacin de los nodos es mediante la utilizacin de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver como relaciones entre los ndices. Esta relacin entre ndices se puede guardar en una matriz, que llamaremos de adyacencia.Representacin mediante listas: En las listas de adyacencia lo que haremos ser guardar por cada nodo, adems de la informacin que pueda contener el propio nodo, una lista dinmica con los nodos a los que se puede acceder desde l. La informacin de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinmica.Representacin mediante matrices dispersas: Para evitar uno de los problemas que tenamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta informacin como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, slo representaremos aquellos enlaces que existen en el grafo.Dgrafo (grafo dirigido).A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso. Aplicaciones de los dgrafos Una de las aplicaciones mas importantes es de hallar el camino mas corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, para el recorrido de rboles, sirve para la representacin de algoritmos, etc. Un ejemplo de esto es la tarea de frer un huevo.

Aplicaciones de grafos y rboles Gracias a la teora de grafos se pueden resolver diversos problemas como por ejemplo la sntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes reas por ejemplo, Dibujo computacional, en toda las reas de Ingeniera. Los grafos se utilizan tambin para modelar trayectos como el de una lnea de autobs a travs de las calles de una ciudad, en el que podemos obtener caminos ptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. Para la administracin de proyectos, utilizamos tcnicas como PERT en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos. La teora de grafos tambin ha servido de inspiracin para las ciencias sociales, en especial para desarrollar un concepto no metafrico de red social que sustituye los nodos por los actores sociales y verifica la posicin, centralidad e importancia de cada actor dentro de la red. Esta medida permite cuantificar y abstraer relaciones complejas, de manera que la estructura social puede representarse grficamente. Por ejemplo, una red social puede representar la estructura de poder dentro de una sociedad al identificar los vnculos (aristas), su direccin e intensidad y da idea de la manera en que el poder se transmite y a quines. Los grafos son importantes en el estudio de la biologa y hbitat. El vrtice representa un hbitat y las aristas (o "edges" en ingls) representa los senderos de los animales o las migraciones. Con esta informacin, los cientficos pueden entender cmo esto puede cambiar o afectar a las especies en su hbitat. Por ejemplo, supongamos que unas lneas areas realizan vuelos entre las ciudades conectadas por lneas como se ve en la figura anterior (ms adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relacin recibe el nombre de grafo.

GRAFO DE EULERUn camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. El problema de encontrar dichos caminos fue discutido por primera vez por Leonhard Euler, en el famoso problema de los puentes de Knigsberg.CIRCUITO DE EULERUn ciclo euleriano o circuito euleriano es aquel camino que recorre todas las aristas de un grafo tan solo una nica vez, siendo condicin necesaria que regrese al vrtice inicial de salida (ciclo = camino en un grafo donde coinciden vrtice inicial o de salida y vrtice final o meta). Una definicin ms formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez". Se debe tener en cuenta que no importa la repeticin de vrtices mientras no se repitan aristas.CAMINO HAMILTONIANO Y CIRCUITO HAMILTONIANOUn camino hamiltoniano, en el campo matemtico de la teora de grafos, es un camino de un grafo, una sucesin de aristas adyacentes, que visita todos los vrtices del grafo una sola vez. Si adems el ltimo vrtice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo.Los caminos y ciclos hamiltonianos se llaman as en honor de William Rowan Hamilton, inventor de un juego que consista en encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvi este problema usando cuaterniones, aunque su solucin no era generalizable a todos los grafos.REPRESENTACION EN MEMORIALos grafos se representan en memoria enlazada mediante listas de adyacencia.Una lista de adyacencia, se define de la siguiente manera: Para un verticei es una lista en cierto orden formada por todos los vrtices adyacentes [a,i]. Se puede representar un grafo por medio de un arreglo donde cabeza de i es un apuntador a la lista de adyacencia al vrtice i.Ejemplo:

La lista de adyacencia, que se obtuvo a partirdel grafo anterior es la siguiente:

ISOMORFISMO DE GRAFOSDos grafos G1 y G2 son isomorfos si existe una funcin biyectiva f entre los vrtices de G1 y G2, y una funcin biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vrtices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo.EJERCICIOS PROPUESTOS1. Realice la matriz de adyacencia del siguiente grafo:

SOLUCION:

2. Recorra el siguiente grafo en profundidad

Solucin

3. Sean los siguientes grafosG1yG2. Demuestre que son isomorfos

Un isomorfismo para los grafos anterioresG1yG2esta definido por:f(a) = Af(b) = Bf(c) = Cf(d) = Df(e) = Eyg(Xi) = Yi,i= 1, ... , 5Los grafosG1yG2son isomorfos si y solo si para alguna ordenacin de vrtices y lados sus matrices de incidencia son iguales. Veamos las matrices de incidencia de los grafos anteriores:

BIBLIOGRAFIAhttp://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafoshttp://oskasuki.blogspot.com/2011/06/un-grafo-se-puede-representar-mediante_1131.htmlhttp://www.monografias.com/trabajos16/grafos/grafos.shtml#GRADO#ixzz2y97VZxughttp://matematicasparacomputadora.weebly.com/66-aplicaciones-de-grafos-y-aacuterboles.htmlhttp://es.wikipedia.org/wiki/Ciclo_eulerianohttp://es.wikipedia.org/wiki/Camino_hamiltonianohttp://www.gayatlacomulco.com/tutorials/estru1/74.htm