Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Capítulo 7: Grafos Autor: José Alfredo Jiménez Murillo.

  • Published on
    25-Jan-2016

  • View
    247

  • Download
    4

Transcript

  • Captulo 7: GrafosAutor: Jos Alfredo Jimnez Murillo

  • Objetivos---Aplicar la teora de grafos a la solucin de problemas factibles de ser resueltos con esta metodologa.Aprender la simbologa y nomenclatura propia de la teora de grafos y distinguir las caractersticas de los grafos.Conocer las condiciones que debe cumplir un grafo que se considera que tiene circuitos importantes como Euler y Hamilton.

    Usar la tcnica de coloracin de grafos para iluminar un mapa con la cantidad mnima de colores sin que se junten dos colores iguales.-

  • Introduccin Uno de los primeros trabajos de teora de grafos que se llev a cabo fue el que realiz Leonhard Euler en el siglo XVIII sobre los puentes de Knigsberg (en la ciudad Rusa de Kaliningrado), en el cual pretenda hacer un recorrido a travs de 7 puentes que conectaban a 4 porciones de tierra como se muestra en la figura El objetivo era salir de un punto especfico y regresar al punto de partida despus de haber cruzado los 7 puentes, pero pasando solamente una vez por cada uno de ellos. Euler represent al problema por medio de una figura como la siguiente.

  • A esta figura Euler la llam Grafo, a las porciones de tierra representadas por un punto las llam Vrtices, a los puentes representados por lneas les dio el nombre de Aristas y a las lneas que salen o entran a un vrtice los llam Orden del vrtice, ms tarde al orden de un vrtice se le llam valencia. Despus de analizar el problema, Euler lleg a la conclusin de que es imposible obtener un itinerario que saliera de un vrtice y regresara a l, pasando por todas las aristas solamente una vez. Euler mencionaba que si el vrtice donde se inicia y termina el recorrido es el mismo, entonces dicho vrtice debe tener valencia par ya que por un puente sale y por otro diferente debe regresar. Lo mismo ocurre con todos los dems vrtices ya que debe estar contemplada la entrada y salida, por lo tanto Euler estableci que En un grafo solamente se puede establecer un ciclo que pase por todas las aristas de un grafo solamente una vez, si todos los vrtices tienen valencia par. Introduccin

  • Partes de un grafo Un grafo (G) es un diagrama que consta de un conjunto de vrtices (V) y un conjunto de lados (L). Sea el siguiente grafo.Vrtices (Nodos). Se indican por medio de un pequeo crculo y se les asigna un nmero o letra. En la figura anterior V={a, b, c, d}.Lados (ramas o aristas). Son las lneas que unen un vrtice con otro. Se les asigna una letra, nmero o combinacin de ambos: L={1, 2, 3, 4, 5, 6}.Lados paralelos . Son aquellas aristas que tienen relacin con un mismo par de vrtices: P={2, 3}.Lazo. Es aquella arista que sale de un vrtice y regresa al mismo vrtice. En la figura anterior A={6}.Valencia de un vrtice. Es el nmero de lados que salen o entran a un vrtice. En la figura anterior las valencias de los vrtices son:Valencia (a) = 2Valencia (b) = 4Valencia (c) = 2Valencia (d) = 3

  • Tipos de grafosGrafos simples. Son aquellos grafos que no tienen lazos ni lados paralelos. Ejemplo. Grafo completo de n vrtices (Kn). Es aquel grafo en donde cada vrtice est relacionado con todos los dems, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el nmero de vrtices del grafo. 654cd1123bacbaba123K2K3K4La valencia en cada uno de los vrtices es (n-1) y el nmero de lados est dado por la expresin:

  • Complemento de un grafo (G). Es aqul grafo que le falta al grafo G, para entre ambos formar un grafo completo de n vrtices. Dicho grafo no tiene lazos ni ramas paralelas. Ejemplo:98731fedcba654Geb15121110fdca1413G2Valencia de cada vrtice = (n-1)=(6-1) = 5No. de lados === 15Tipos de grafos

  • Grafo Bipartido. Es aquel que est compuesto por dos conjuntos de vrtices. Uno de ellos A = {a1, a2, a3, ... , an} y otro B = { b1, b2, ..., bm}, adems de que los vrtices del conjunto A se relacionan con los del B, pero entre los vrtices de un mismo conjunto no existe arista que los una. Ejemplo:Tipos de grafos

  • Grafo bipartido completo (Kn,m). Es aqul grafo que est compuesto por dos conjuntos de vrtices. Uno de ellos A = {a1, a2, a3, ..., an} y otro B = { b1, b2, ..., bm}, en donde cada vrtice de A est unido con todos los vrtices de B pero entre los vrtices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se indica como Kn,m. Ejemplo:136542No es grafo bipartido completo porque no cumple con la condicin, como se observa en el grafo equivalente de al ladoTipos de grafos

  • Representacin matricial Matriz de adyacencia (Ma). Es una matriz cuadrada en la cual los vrtices del grafo se indican como filas, pero tambin como columnas de la matriz Matriz de incidencia (Mi). En esta matriz se colocan los vrtices del grafo como filas y las aristas como columnas. 2 son aristas1 lazosValencias

    abcdea11101b10110Ma=c11110d01101e10010

    x1x2x3x4x5x6x7x8x9x10x11a000111001105b110100100004Mi=c001001110004d111000000014e00000000111322221221222

  • Caminos y circuitos En un grafo se puede recorrer la informacin de diferente manera, lo que implica seguir distintas rutas para llegar de un nodo del grafo a otro. Camino. Es una sucesin de lados que van de un vrtice x a un vrtice w (dichos lados se pueden repetir). Circuito (Ciclo). Es un camino del vrtice w al vrtice w. Esto es, un camino que regresa al mismo vrtice de donde sali. Camino simple de longitud n. Es una sucesin de lados que van de un vrtice x a un vrtice w, en donde los lados que componen dicho camino son distintos e iguales a n. Circuito simple de longitud n. Es aqul camino del vrtice w al vrtice w que solamente tiene un ciclo en la ruta que sigue.

  • EjemploEn la tabla siguiente se muestran distintos recorridos del grafo que se encuentra al lado.

    RecorridoCaminoCamino simpleCircuitoCircuito simple{a,c,d,f}**{c,b,a,h,a}*{b,c,d,e,e,c,b}**{c,e,d,c}***{e,e}***{a,c,e,e,g,e,d,c,a}**{h,a,c,e,d,b}**

  • Grafo conexo. Es aqul en el que para cualquier par de vrtices w, x, distintos entre s, existe un trayecto para ir de w a x. Ejemplo:En el grafo conexo (conectado) siempre existe un camino para ir de un vrtice a otro. Ejemplo

  • Camino de Euler. Es el camino que recorre todos los vrtices pasando por todas las ramas solamente una vez.Una caracterstica del camino de Euler es que el recorrido sale de un vrtice de valencia impar y termina tambin en un vrtice de valencia impar.Camino de Euler es {a, b, e, h, g, e, d, a, c, f, d, g, f, h} Ejemplo

  • Circuito de Euler. Es aquel ciclo que recorre todos los vrtices pasando por todos los lados solamente una vez.La firma del diablo es un juego que consiste en dibujar una figura sin levantar el lpiz del papel, partiendo de un punto y regresando nuevamente a l, sin pasar dos veces por una misma arista. Este problema se puede resolver por medio del circuito de Euler. Ejemplo

  • EjemploA partir del siguiente grafo, determinar un circuito de EulerUsando el algoritmo de FleurySeleccionar un vrtice arbitrario, por ejemplo {b} y llamarlo vrtice actual.2)Eliminar la arista seleccionada. El vrtice actual ahora es (d).4)

  • hEscoger una arista que no sea puente a partir del vrtice actual. {b,d,e,b,c,h). Observar cmo en este caso no puede ser la arista (c,a) ya que es puente y el grafo ya no sera conexo.3.4)Eliminar la arista seleccionada. El vrtice actual ahora es (h).4.4)Continuar hasta que todos los vrtices estn desconectados para obtener el circuito de Euler.Ejemplo

  • hCircuito de Hamilton. Es un problema similar al circuito de Euler, pero en lugar de pasar por todos los lados del grafo solamente una vez como lo hace el circuito de Euler, en el circuito de Hamilton se pasa por cada vrtice solamente una vez. En un grafo se sabe de antemano que tiene un circuito de Euler, si es conexo y todos sus vrtices tienen valencia par, pero no hay forma de saber con anticipacin si tiene o no un circuito de Hamilton.jifgdbaecRespuestaObservar como no es necesario que se pase por todas las aristas.Circuito de Hamilton: {a,b,h,g,e,j,i,f,d,c,a}Ejemplo

  • IsomorfismoSe dice que dos grafos G1 y G2 son isomorfos cuando, teniendo apariencia diferente, realmente son iguales porque coinciden en: Mismo nmero de lados. Mismo nmero de vrtices. Mismo conjunto de valencias. Ambos son o no conexos. Ambos tienen el mismo nmero de circuitos de longitud n. Ambos tienen o no circuito de Euler.Esto implica que todos los vrtices de G1 tienen un vrtice equivalente en G2 y que todas las aristas del grafo G1 tienen una arista equivalente en G2. Por otro lado, se sabe que dos grafos G1 y G2 son isomorfos si y slo si para alguna ordenacin de vrtices y sus aristas, sus matrices de incidencia son iguales.

  • Determinar si los grafos siguientes G1 y G2 son isomorfos, haciendo coincidir sus matrices de incidencia, manteniendo una matriz esttica y realizando intercambios de filas y/o columnas en la otra matriz.Ejemplo

  • Las matrices de incidencia son:1001000000f1110001000e0100110100d0011100001c=MG10000001111b0000010010ax10x9x8x7x6x5x4x3x2x110101000016010110010051000011100400010000103=MG20000010001201100010101r10r9r8r7r6r5r4r3r2r1Ejemplo

  • Solucin: Se deben hacer intercambios de filas por columnas hasta hacer que MG2=MG1Ejemplo

  • Demostrar que dos grafos son isomorfos haciendo intercambios de filas y/o columnas, hasta que las matrices de incidencia coincidan, es muy complicado y a medida que aumenta el nmero de vrtices y aristas es an ms complicado. En lugar de hacer coincidir las matrices lo que se realiza es una comparacin de las propiedades principales de los grafos; si coinciden en todas ellas se concluye que son isomorfos, pero si existe alguna diferencia ya sea en el nmero de vrtices, en el conjunto de valencias, o si uno de ellos es conexo y el otro no, o si uno tiene circuito de Euler y el otro no, o si uno de ellos tiene ms circuitos de longitud n que el otro, eso es causa suficiente para determinar que los grafos no son isomorfos.Ejemplo

  • La siguiente tabla muestra las propiedades en donde debe haber coincidencia entre G1 y G2 anteriores para que se consideren isomorfos.Ejemplo

    PropiedadG1G2ObservacinNo. de vrtices66No. de lados1010Valencias2,4,4,4,4,24,2,2,4,4,4Coinciden en el mismo nmero de vrtices de valencia 2 y de valencia 4ConexoSiSiYa que para cualquier par de vrtices se puede encontrar un camino.Camino de EulerNoNoYa que todos los vrtices tienen valencia parCircuito de EulerSiSiYa que todos los vrtices tienen valencia par y se trata de grafos conexos.Circuitos de longitud n (En este caso de longitud 3)6a,b,d,ab,e,c,bb,d,c,bb,d,e,bc,d,e,cc,e,f,c61,3,5,11,6,4,11,4,5,11,5,6,12,4,6,24,5,6,4En lugar de tener longitud 3, se pudo ver cuntos circuitos tienen longitud 4. Pero en cualquier caso debe coincidir.

  • Grafos planos. Un grafo plano es aqul que se puede dibujar en un solo plano y cuyas aristas no se cruzan entre s. Ejemplo:Euler establece que la ecuacin A = L V +2 es vlida para un grafo plano y conexo. En donde A: Numero de reas, L: Nmero de lados y V: Nmero de vrtices.A = L V +26 = 10 6 +2Observar cmo la parte que rodea al grafo tambin se cuenta como rea.Ejemplo

  • Existen grafos importantes que se vieron anteriormente, por ejemplo K4 es un grafo plano ya que se puede dibujar en forma plana sin que sus aristas se crucen. Pero K5 es un grafo no plano ya que no hay forma en que por lo menos un par de aristas se deje de cruzar.Otro grafo importante que no es plano, es el grafo bipartido completo K3,3. Tanto K5 como K3,3 se utilizan como patrones para demostrar que otros grafos ms grandes no son planos.Ejemplo

  • SolucinPor ms que se trate de dibujar el grafo en forma plana no va a ser posible, ya que tiene dentro de l un grafo no plano K3,3.De esta forma si se eliminan las aristas punteadas, los vrtices de valencia dos y los nodos que queden desconectados se descubrir un grafo K3,3.Dibujar en forma plana el siguiente grafo, o bien demostrar que no es plano encontrando dentro de l un grafo K3,3 o K5. En caso de ser plano probar que se cumple la ecuacin de Euler A=L-V+2.Ejemplo

  • Dibujar en forma plana el siguiente grafo o bien demostrar que no es plano encontrando dentro de l un grafo K3,3 o K5. En caso de ser plano probar que se cumple la ecuacin de Euler A=L-V+2.Tampoco este grafo es plano ya que dentro de l se puede encontrar:Ejemplo

  • Dibujar en forma plana el siguiente grafo o bien demostrar que no es plano encontrando dentro de l un grafo K3,3 o K5. En caso de ser plano probar que se cumple la ecuacin de Euler A=L-V+2.SolucinEn este caso se trata de un grafo plano como se muestra:En ste se cumple la Ecuacin de Euler:A = L V + 211 = 19 10 + 2Ejemplo

  • Los grafos de similaridad permiten agrupar informacin con caractersticas semejantes. Esto implica formar subgrafos en donde los vrtices de un subgrafo estn relacionados entre s pero no tienen relacin con los vrtices del otro subgrafo, ya que no son similares. Una utilidad de este tipo de grafos es en reconocimiento de patrones, en donde se agrupa informacin con propiedades muy parecidas. Grafos de similaridadEn este tipo de grafo se debe definir una funcin que permita determinar la similaridad que existe entre los vrtices, principalmente la distancia entre sus caractersticas. Una funcin muy usada para determinar la distancia esS(Px-Py) = Px,i-Py,i=Px,1-Py,1+Px,2-Py,2++Px,n-Py,men donde Px,n es la propiedad n del punto Px, y Py,m es la propiedad m del punto Py.

  • Con la funcin anterior es posible encontrar la distancia que existe entre las propiedades de los vrtices x y y. Un valor grande de S(Px-Py) indica que no existe similaridad entre los vrtices x y y, mientras que un valor pequeo significa que son muy parecidos o similares. Pero adems de la funcin anterior, es necesario un valor referencial para discriminar la informacin que en este caso se llamar coeficiente de inferencia C. El valor de C se puede seleccionar de acuerdo a la experiencia que se tenga en el campo o bien por medio de prueba piloto. Si C es grande la similaridad es poco exacta, sin embargo para un valor de C pequeo la similaridad es muy fuerte.Una vez que se tiene S(Px-Py) para todos los puntos (vrtices) en cuestin, se forman los grafos similares por medio del siguiente criterio:Si S(Px-Py) C se traza una arista entre los vrtices Px y Py, y se dice que Px y Py son similares. Los grafos similares forman un subgrafo y los no similares otro distinto. Grafos de similaridad

  • La siguiente tabla muestra las caractersticas que tienen las diferentes partes de tejido de igual seccin transversal de un anlisis de mama, de acuerdo a temperatura, Intensidad de color e inflamacin.Determinar los grafos de similaridad para un coeficiente de inferencia C=5.Ejemplo

  • RespuestaLo primero que se debe hacer es encontrar la distancia entre los puntos Px y Py por medio de la siguiente funcin:S(Px-Py) = Px,i-Py,i=Px,1-Py,1+Px,2-Py,2++Px,n-Py,mSi x = y.S(P1-P1) = P1,1-P1,1+P1,2-P1,2+P1,3-P1,3 = 39 - 39+48 - 48+7 - 7=0Si x y.S(P1-P2) = P1,1-P2,1+P1,2-P2,2+P1,3-P2,3 = 39 - 37+48 - 42+7 - 6= 9S(P1-P3) = P1,1-P3,1+P1,2-P3,2+P1,3-P3,3 = 39 - 40+48 - 47+7 - 8= S(P1-P4) = P1,1-P4,1+P1,2-P4,2+P1,3-P4,3 = 39 - 36+48 - 41+7 - 5= 12S(P1-P5) = P1,1-P5,1+P1,2-P5,2+P1,3-P5,3 = 39 - 39+48 - 49+7 - 9= 33

  • S(P2-P3) = P2,1-P3,1+P2,2-P3,2+P2,3-P3,3 = 37 - 40+42 - 47+6 - 8= 10S(P2-P4) = 37 - 36+42 - 41+6 - 5 = S(P2-P5) = 37 - 39+42 - 49+6 - 9 = 12S(P3-P4) = 40 - 36+47 - 41+8 - 5 = 13S(P3-P5) = 40 - 39+47 - 49+8 - 9 = S(P4-P5) = 36 - 39+41 - 49+5 - 9 = 15Si se considera que dos puntos son similares si S(Px-Py) C, en este caso S(Px-Py) 5 (valores con fondo azul) con lo cual se puede decir que el grafo est dividido en dos partes como se muestra a continuacin.Los lazos en cada uno de los vrtices significan la similaridad entre ellos mismos. Con los grafos anteriores se puede considerar que las partes de tejido P1, P3, P5 son similares y las partes P2 y P4 tambin lo son. 34Respuesta

  • Grafos ponderados En un grafo ponderado a las aristas se les asigna un valor. A ese valor se le llama ponderacin y podra representar la distancia que hay de un nodo a otro, o bien el costo de transportarse de una ciudad a otra.Determinar la ruta ms corta es un problema tpico de la teora de grafos y consiste en encontrar el camino ms corto para ir de una ciudad origen (w) a una ciudad destino (x). Pueden existir distintas rutas para ir de un nodo a otro, pero el objetivo es encontrar el ms corto o bien el ms econmico si es que la ponderacin representa un costo.Algoritmo de Dijkstra Seleccionar la ciudad origen (a).1.-

  • Colocar en la matriz la distancia que existe de la ciudad origen a ella misma. (Cuando se trata de encontrar la distancia de una ciudad a ella misma considerar que es 0). A todas las dems columnas se les coloca como distancia.3.-Grafos ponderados

  • Colocar en la columna actual el vrtice que tenga la distancia ms corta de entre todos los nodos. (Es obvio que en esta primera iteracin es el nodo origen.) En la columna seleccionados registrar dicho nodo escogido para ya no volverlo a elegir. (En nuestro caso le colocamos a esta distancia en negrita y subrayado.)4.-Registrar en la columna de cada uno de los nodos la distancia ms corta que resulta de sumar la distancia registrada en el nodo actual + distancia a los vrtices adyacentes a l y seleccionar la distancia ms corta cuyo nodo an no est seleccionado de esa fila de la matriz. Suponer que d1 > d2, por lo tanto la matriz ser:5.-Grafos ponderados

    Iteracin a b c d.actualseleccionados00.aa

    Iteracin a b c d.actualseleccionados00.aa10d1d2.

  • Si el nodo seleccionado tiene una distancia diferente de que es menor o igual a la que se obtiene de sumar la distancia registrada en la columna del nodo actual + la distancia de ese nodo actual a los nodos adyacentes a l dejarla tal como est, en caso contrario cambiarla por la nueva suma.Registrar en la columna actual el vrtice que tenga la distancia ms corta de entre todos los nodos y que no haya sido seleccionado hasta ahora. Adems de anotar en la columna seleccionados dicho nodo para ya no volverlo a elegir. 6.-Si ya estn todos los vrtices seleccionados finalizar. En caso contrario regresar al paso 5.7.-Grafos ponderados

    Iteracin a b c d.actualseleccionados00.aa10d1d2.ca,c

  • kEncontrar la ruta ms corta para ir de la ciudad origen (a) a las ciudades restantes. EjemploEjemplo: Para ir de a a j la distancia mnima es 6. Para ir de a a k la distancia es 8.

    Iteabcdefghijkactseleccionados00aa10413ea,e20341533ba,e,b30341533ga,e,b,g40341533ha,e,b,g,h503414335ca,e,b,g,h,c6034514335fa,e,b,g,h,c,f70345143356da,e,b,g,h,c,f,d803451433568ia,e,b,g,h,c,f,d,i903451433568ja,e,b,g,h,c,f,d,i,j1003451433568ka,e,b,g,h,c,f,d,i,j,k

  • Sea G(V,A) un grafo y sea C un conjunto de colores. La coloracin de los vrtices V del grafo usando un color del conjunto C se encuentra dada por la funcin.Coloracinf: VC Si v1,v2 V adyacente entonces f(v1) f(v2)Esto implica que cuando se lleva a cabo la coloracin en vrtices de un grafo, cada par de vrtices adyacentes v1 y v2 del grafo debern estar iluminados con un color diferente.Nmero cromticoEs el nmero mnimo de colores con que se puede colorear un grafo G cuidando que los vrtices adyacentes no tengan el mismo color. El nmero cromtico se indica de la siguiente manera:X (G)

  • La coloracin de grafos es un problema NP-Computable, esto significa que no hay procedimientos eficientes para llevar a cabo esta tarea, sin embargo existen mtodos aproximados que pueden dar buenos resultados. Uno de ellos es:Se recomienda colorear del mismo color tantos vrtices como sea posible e iluminar al mismo tiempo los vrtices que compartan nodos vecinos.Coloracin

  • Encontrar el nmero cromtico del siguiente grafo G. EjemploeePaso 1:Paso 2:Paso 3:e

  • Ejemplo

  • Caractersticas del nmero cromticoUn grafo G tiene nmero cromtico X(G) = 1 si y slo si no tiene aristas. c,1Ya que un vrtice slo puede iluminarse de un solo color1)El nmero cromtico para un camino o un ciclo de longitud 2 es X(G) = 2 ya que siempre se podrn alternar los colores.2)

  • Aplicaciones de los grafos Redes (carreteras, telefnicas, elctricas, de computadoras, etc.) Optimizacin de los recursos. Sistemas de informacin. Reconocimiento de patrones.

Recommended

View more >