{"id":153,"date":"2011-01-16T18:57:53","date_gmt":"2011-01-16T18:57:53","guid":{"rendered":"https:\/\/blogs.ua.es\/dar15\/?p=153"},"modified":"2011-01-16T19:05:31","modified_gmt":"2011-01-16T19:05:31","slug":"teoria-sesion-12","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dar15\/2011\/01\/16\/teoria-sesion-12\/","title":{"rendered":"Teoria sesi\u00f3n 12"},"content":{"rendered":"<p>Sesi\u00f3n correspondiente al d\u00eda (14\/12\/2010).<\/p>\n<p><strong>C\u00c1LCULO DE COMPONENTES CONEXAS<\/strong><\/p>\n<p>Diremos que una componente conexa (CC( asociada a un v\u00e9rtice vi es:<\/p>\n<p>Conjunto de v\u00e9rtices a los que alcanza vi:<\/p>\n<p>R(vi)<\/p>\n<p>Y que alcanza a vi:<\/p>\n<p>Q(vi)<\/p>\n<p>CC asociada a vi: R(vi) \u2229 Q(vi)<\/p>\n<p>Una componente conexa asociada a un v\u00e9rtice \u201cv\u201d es un conjunto de v\u00e9rtices alcanzables por\u201dv\u201d y que a su vez pueden alcanzar a \u201cv\u201d.<\/p>\n<p>Hay dos procedimientos o m\u00e9todos para calcular las componentes conexas de un grafo:<\/p>\n<p><strong>M\u00e9todo 1 \u2013 Procedimiento del algoritmo<\/strong><\/p>\n<p>Sea G=(V, A) un grafo dirigido:<\/p>\n<p>Etapa 1. Inicializar i&lt;-1, V<sup>(1) <\/sup>= V<\/p>\n<p>Etapa 2. Tomar vi E V<sup>(i)<\/sup><\/p>\n<p>Etapa 3. Calcular R(i) \u2229 Q(vi)<\/p>\n<p>-Hacer V<sup>(i+1)<\/sup> = V<sup>(i)<\/sup> \u2248 R(vi) \u2229 Q(vi)<\/p>\n<p>-Hacer i&lt;-i+1<\/p>\n<p>Etapa 4. Si V<sup>(i)<\/sup> = \u00f8 entonces STOP<\/p>\n<p>En otro caso, volvemos a la Etapa 2.<\/p>\n<p>EJEMPLO<\/p>\n<p>Vamos a calcular las componentes conexas del siguiente grafo, para ello necesitamos la <strong>matriz de accesibilidad<\/strong> y la <strong>matriz de acceso<\/strong> que es la traspuesta de la de accesibilidad:<\/p>\n<p><a href=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/Sin-t\u00edtulo-1-1024x308.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-158\" src=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/Sin-t\u00edtulo-1-1024x308-300x90.jpg\" alt=\"\" width=\"390\" height=\"101\" \/><\/a><\/p>\n<p>Ahora sigamos el algoritmo paso a paso:<\/p>\n<p>Debemos hacer dos conjuntos, R y Q.<\/p>\n<p>Inicialmente\u00a0 cogemos todo el conjunto de v\u00e9rtices que tenemos y de ah\u00ed cogemos un v\u00e9rtice.<\/p>\n<p>Una vez hecho vamos a la matriz de accesibilidad y buscamos la fila del v\u00e9rtice elegido, entonces vemos columna a columna si hay un uno o un cero, si hay un uno a\u00f1adimos el v\u00e9rtice al conjunto R. Una vez hecho debemos hacer lo mismo para el conjunto Q pero mirando en la matriz de acceso.<\/p>\n<p>Hacemos i&lt;-1, V<sup>(1) <\/sup>= V = {V1, V2, V3, V4, V5}<\/p>\n<p>Tomamos un v\u00e9rtice de V<sup>(1) <\/sup>, Por ejemplo V2.<\/p>\n<p>Primera componente conexa: R(V2) \u2229 Q(V2)<\/p>\n<p>R(V2) \u2229 Q(V2) = {V2, V4} \u2229 {V1, V2, V3, V4, V5} = {V2, V4}<\/p>\n<p>V<sup>(2)<\/sup> = V<sup>(1)<\/sup> \u2248 R(V2) \u2229 Q(V2) = {V1, V3, V5} es decir, restamos a V<sup>(i) <\/sup>lo que obtenemos de realizar la intersecci\u00f3n entre R(V2) y Q(V2).<\/p>\n<p>Tomamos lo que obtenemos que hemos denominado V<sup>(2) <\/sup>y elegimos un v\u00e9rtice de dicho conjunto, una vez hecho repetimos el procedimiento que expliqu\u00e9 al principio.<\/p>\n<p>Tomamos un v\u00e9rtice de V<sup>(2) <\/sup>, por ejemplo, V1.<\/p>\n<p>Segunda componente conexa: R(V1) \u2229 Q(V1).<\/p>\n<p>R(V1) \u2229 Q(v1) = {V1, V2, V3, V4, V5} \u2229 {V1, V3, V5} = {V1, V3, V5}<\/p>\n<p>V<sup>(3)<\/sup> = V<sup>(2)<\/sup> \u2248 R(V1) \u2229 Q(V1) = \u00f8<\/p>\n<p>Hemos obtenido el conjunto vac\u00edo, lo que nos indica que hemos terminado, por lo tanto las componentes conexas son las V<sup>(i)<\/sup> que hemos obtenido:<\/p>\n<p>{V2, V4}, {V1, V3, V5}<\/p>\n<p>Gr\u00e1ficamente quedar\u00eda de la siguiente forma:<\/p>\n<p><a href=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/a.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-159\" src=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/a-300x249.jpg\" alt=\"\" width=\"300\" height=\"249\" srcset=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/a-300x249.jpg 300w, https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/a.jpg 436w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p><strong>M\u00e9todo 2 \u2013 Multiplicaci\u00f3n de matrices<\/strong><\/p>\n<p>Este m\u00e9todo es f\u00e1cil de realizar si sabemos multiplicar matrices.<\/p>\n<p>El procedimiento es el siguiente:<\/p>\n<p>-Hayamos la <strong>matriz de <\/strong><strong>accesibilidad <\/strong>y la <strong>matriz de <\/strong><strong>acceso<\/strong>.<\/p>\n<p>-Multiplicamos ambas matrices t\u00e9rmino a t\u00e9rmino, es decir, R1,1 x Q1,1; R1,2 x Q1,2; etc\u2026Esto nos dar\u00e1 la matriz RxQ.<\/p>\n<p>Dentro de la matriz tendremos tantas filas como v\u00e9rtices y tendremos que ir fila a fila y columna a columna viendo si aparece un uno o un cero, si aparece un uno entonces ese v\u00e9rtice de la columna forma parte de una componente conexa. Es posible que aparezcan filas repetidas, esto se debe a que no tenemos por qu\u00e9 tener el mismo n\u00famero de componentes conexas que de v\u00e9rtices, las filas que se repiten hacen alusi\u00f3n a la misma componente conexa.<\/p>\n<p><strong>RECORRIDO DE ARISTAS<\/strong><\/p>\n<p>Es interesante averiguar si es posible recorrer un grafo pasando por cada arista una sola vez ya que en grafos complejos no es tan f\u00e1cil de ver.<\/p>\n<p>Para introducir los siguientes conceptos voy a contar una historia que puso las bases de los grafos.<\/p>\n<p>\u201cProblema de los puentes de K\u00f6nigsberg\u201d: K\u00f6nigsberg era una ciudad que estaba separada en 4 partes y conectadas dichas partes unas con otras por 7 puentes. Pero surgi\u00f3 una pregunta, \u00bfes posible salir de un punto de la ciudad y, pasando por todos los puentes una \u00fanica vez, volver al mismo punto?.<\/p>\n<p>Leonhard Euler lo resolvi\u00f3 introduciendo el concepto de <strong>grafo euleriano<\/strong>.<\/p>\n<p>Sea G un grafo conexo y en general no simple:<\/p>\n<p>1 \u2013 Llamaremos <strong>tour <\/strong>de G a una cadena cerrada que atraviesa cada arista de G al menos una vez.<\/p>\n<p>2 \u2013 Llamaremos <strong>tour euleriano <\/strong>de G a un tour de G que atraviesa cada arista exactamente una vez.<\/p>\n<p>3 \u2013 Llamaremos <strong>grafo euleriano <\/strong>a aquel en el que podemos encontrar un <strong>tour euleriano<\/strong>.<\/p>\n<p>4 \u2013 Llamaremos <strong>camino euleriano <\/strong>a una cadena (simple) que atraviesa cada arista exactamente una vez.<strong><br \/>\n<\/strong><\/p>\n<p>Para ver si un grafo tiene un tour euleriano (y por lo tanto es un grafo euleriano) o si tiene un camino euleriano tenemos varios argumentos con los que descartar el tour euleriano, el camino euleriano o ambos:<\/p>\n<p>-Para que el grafo pueda tener un tour euleriano, no debe tener v\u00e9rtices de grado impar.<\/p>\n<p>-Para que el grafo pueda tener un camino euleriano, debe tener exactamente dos v\u00e9rtices de grado impar.<\/p>\n<p>La forma de calcular un tour euleriano y un camino euleriano viene dado por el algoritmo de Fleury.<\/p>\n<p><strong>ALGORITMO DE FLEURY<\/strong><\/p>\n<p><strong>Grafo no dirigido<\/strong><\/p>\n<p>Para calcular un tour euleriano en un grafo no dirigido partimos de vi y terminamos en vi. Vamos a ir construyendo una cadena simple de forma que no se repitan aristas y que no se elijan aristas de corte a no ser que no haya otra alternativa, estas aristas de corte son aquellas que al quitarlas, dejan v\u00e9rtices aislados. Cada arista que vamos eligiendo y eliminando la a\u00f1adimos al tour euleriano. Terminaremos cuando hayamos llegado desde vi a vj y no queden aristas.<\/p>\n<p>Para calcular un camino euleriano partimos de un v\u00e9rtice vi de grado impar y llegamos al otro v\u00e9rtice de grado impar. El proceso que seguimos de un v\u00e9rtice al otro es el mismo que para el tour euleriano.<\/p>\n<p><strong>Modificaci\u00f3n para grafos dirigidos<\/strong><\/p>\n<p>El proceso es el mismo, para calcular el tour euleriano debemos tener cuidado y al eliminar arcos no debemos elegir un arco que al eliminarlo aumente el n\u00famero de componentes conexas del grafo no dirigido asociado, a no ser que no tengamos otra alternativa.<\/p>\n<p>Para calcular el camino euleriano debemos empezar por un v\u00e9rtice de grado impar y terminar en el otro v\u00e9rtice de grado impar, de la misma forma que hac\u00edamos en el grafo no dirigido, para ver si un v\u00e9rtice de un grado dirigido tiene grado impar se puede hacer comprobar que:<\/p>\n<p>de(p) = ds(p)-1,\u00a0 de(q) = ds(q)+1<\/p>\n<p>Siendo p y q los v\u00e9rtices inicial y final respectivamente del camino.<\/p>\n<p>EJEMPLO<\/p>\n<p>Teniendo el siguiente grafo no dirigido:<\/p>\n<p><a href=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/Sin-t\u00edtulo-42.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-160\" src=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/Sin-t\u00edtulo-42-300x126.jpg\" alt=\"\" width=\"300\" height=\"126\" srcset=\"https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/Sin-t\u00edtulo-42-300x126.jpg 300w, https:\/\/blogs.ua.es\/dar15\/files\/2011\/01\/Sin-t\u00edtulo-42.jpg 588w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p>Como podemos ver no hay v\u00e9rtices de grado impar, luego puede haber un tour euleriano y no va a haber un camino euleriano.<\/p>\n<p>Empezamos por el V4 por ejemplo, ya que tenemos menos riesgo de quitar una arista de corte, como estamos buscando un tour euleriano sabemos que debemos volver a este v\u00e9rtice al final del tour euleriano.<\/p>\n<p>Quitamos la arista e3 y llegamos al v\u00e9rtice V3, como todo ha sido correcto pues no queda ning\u00fan v\u00e9rtice aislado podemos a\u00f1adir la arista e3 al tour euleriano y seguir con el proceso.<\/p>\n<p>Esto iremos haci\u00e9ndolo v\u00e9rtice a v\u00e9rtice y arista a arista hasta llegar nuevamente a V4.<\/p>\n<p>Si alguien tiene alguna duda le paso el ejercicio completo, con im\u00e1genes de todo el proceso, de todas formas el tour resultante por si alguien lo intenta y quiere ver si lo hizo bien: <strong>e3 e4 e10 e9 e7 e1 e5 e8 e6 e2<\/strong>.<\/p>\n<p><strong>CICLO Y CAMINO HAMILTONIANO<\/strong><\/p>\n<p>Un <strong>camino Hamiltoniano<\/strong> en un grafo G es un camino que atraviesa cada v\u00e9rtice del grafo exactamente una vez.<\/p>\n<p>Un <strong>ciclo Hamiltoniano<\/strong> en un grafo G es un ciclo que atraviesa cada v\u00e9rtice del grafo exactamente una vez.<\/p>\n<p>Un <strong>grafo es Hamiltoniano<\/strong> si existe un ciclo hamiltoniano.<\/p>\n<p><strong>Reglas b\u00e1sicas para construir caminos y ciclos hamiltonianos<\/strong><\/p>\n<p><strong>Regla 1<\/strong> \u2013 Si G no es conexo, no posee ciclos Hamiltonianos.<\/p>\n<p><strong>Regla 2 <\/strong>&#8211; Si G es un grafo con \u201cn\u201d v\u00e9rtices, entonces un camino Hamiltoniano debe tener exactamente n-1 aristas, y un ciclo Hamiltoniano n aristas.<\/p>\n<p><strong>Regla 3 <\/strong>&#8211; Si v es un v\u00e9rtice del grafo, entonces un camino Hamiltoniano debe tener al menos una arista incidente con v y como mucho dos.<\/p>\n<p><strong>Regla <\/strong><strong>4 <\/strong>&#8211; Si G es Hamiltoniano, entonces d<sub>G<\/sub>(v) &gt;=2, donde todos los v\u00e9rtices pertenecen a V.<\/p>\n<p><strong>Regla 5 <\/strong>&#8211; Si v perteneciente a V tiene grado 2, entonces las dos aristas incidentes con v deben aparecer en cualquier ciclo<\/p>\n<p>Hamiltoniano de G.<\/p>\n<p><strong>Regla 6 <\/strong>&#8211; Si v perteneciente a V tiene grado mayor que 2, entonces cuando se intenta construir un ciclo Hamiltoniano, una vez que se pase por v, las aristas no utilizadas incidentes se dejan de tener en cuenta.<\/p>\n<p><strong>Regla 7 <\/strong>&#8211; Al construir un ciclo o camino Hamiltoniano para G, no se puede dar el caso de obtener un ciclo para un subgrafo de G a menos que contenta todos los v\u00e9rtices de G.<\/p>\n<p>No podemos calcular si un grafo es Hamiltoniano en estos momentos, ni si tiene ciclos o caminos Hamiltonianos, lo \u00fanico que podemos hacer es ver si no se cumple alguna de estas reglas y demostrar que NO lo es.<\/p>\n<p>A raiz de todo lo mencionado tenemos el siguiente <strong>teorema<\/strong>:<\/p>\n<p>Sea G un <strong>grafo dirigido bipartido<\/strong> con partici\u00f3n {X, Y}.<\/p>\n<p>(1) Si G tiene un ciclo Hamiltoniano, entonces card(X) =\u00a0 card(Y).<\/p>\n<p>(2) Si G tiene un camino Hamiltoniano, entonces card (X) y card(Y) difieren a lo sumo en 1.<\/p>\n<p>El rec\u00edproco es cierto para grafos bipartidos completos con m\u00e1s de 2 v\u00e9rtices.<\/p>\n<p>Recordad la l\u00f3gica de primer orden, que un grafo no sea Hamiltoniano no quiere decir que card(X) != card(Y).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Sesi\u00f3n correspondiente al d\u00eda (14\/12\/2010). C\u00c1LCULO DE COMPONENTES CONEXAS Diremos que una componente conexa (CC( asociada a un v\u00e9rtice vi es: Conjunto de v\u00e9rtices a los que alcanza vi: R(vi) Y que alcanza a vi: Q(vi) CC asociada a vi: R(vi) \u2229 Q(vi) Una componente conexa asociada a un v\u00e9rtice \u201cv\u201d es un conjunto de [&hellip;]<\/p>\n","protected":false},"author":1754,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-153","post","type-post","status-publish","format-standard","hentry","category-general"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/posts\/153","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/users\/1754"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/comments?post=153"}],"version-history":[{"count":3,"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/posts\/153\/revisions"}],"predecessor-version":[{"id":155,"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/posts\/153\/revisions\/155"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/media?parent=153"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/categories?post=153"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dar15\/wp-json\/wp\/v2\/tags?post=153"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}