Edición de «Práctica 8: Caminos Eulerianos y Hamiltonianos (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
==Propiedades== | ==Propiedades== | ||
(Para todo G: grafo, D: digrafo) | (Para todo G: grafo, D: digrafo) | ||
* (DEF) G tiene '''circuito euleriano''' <=> <math>\exists</math> circuito en G que recorre todos los ejes de G 1 vez | * (DEF) G tiene '''circuito euleriano''' <=> <math>\exists</math> circuito en G que recorre todos los ejes de G 1 vez | ||
* (TEO) G tiene | * (TEO) G tiene circuito euleriano <=> G es conexo y todo vertice tiene grado par | ||
* (COR) G tiene '''camino euleriano''' <=> G es conexo y tiene exactamente 2 vertices de grado impar | * (COR) G tiene '''camino euleriano''' <=> G es conexo y tiene exactamente 2 vertices de grado impar | ||
* (TEO) D tiene '''circuito euleriano orientado''' <=> para todo vertice v, d_in(v) = d_out(v) | * (TEO) D tiene '''circuito euleriano orientado''' <=> para todo vertice v, d_in(v) = d_out(v) | ||
Línea 103: | Línea 101: | ||
==Ejercicio 08.11:== | ==Ejercicio 08.11:== | ||
<br>a)Depende la | <br>a)Depende la implementacion. Se podria hacer un BFS en ultima instancia. Igual nose si hay una mejor solucion. | ||
<br>b) Me parece que es muy similar a lo del A. | <br>b) Me parece que es muy similar a lo del A. | ||
<br>c) | <br>c) Esto se los dejo de tarea. | ||
<br>d) Depende lo que hayan elegido | <br>d) Depende lo que hayan elegido. | ||
<br>e) | <br>e) Me parece que la idea debe ser usar que n esta acotado por m, y con BFS o DFS teniamos complejidad O(m+n) que se reduce a O(m). Pero habria que preguntar por las dudas. | ||
==Ejercicio 08.12:== | ==Ejercicio 08.12:== | ||
Línea 114: | Línea 112: | ||
==Ejercicio 08.13:== | ==Ejercicio 08.13:== | ||
<br>He aqui un circuito hamiltoniano: | <br>He aqui un circuito hamiltoniano: | ||
<br>http://upload.wikimedia.org/wikipedia/ | <br>http://upload.wikimedia.org/wikipedia/es/2/2c/Grafo_ejemplo_4_ciclo_hamiltoniano.png | ||
<br>Lo del camino de 5 vertices se puede por "algo asi" como que se pasan por las caras de un dodecaedro, entonces siempre se puede extender, por la simetria | <br>Lo del camino de 5 vertices se puede por "algo asi" como que se pasan por las caras de un dodecaedro, entonces siempre se puede extender, por la simetria | ||
Línea 121: | Línea 119: | ||
==Ejercicio 08.15:== | ==Ejercicio 08.15:== | ||
El circuito Hamiltoniano es una serie de n+1 pasos donde en el paso 1 estamos parados sobre el primer nodo, y en el paso n+1 nuevamente en el primer nodo. | El circuito Hamiltoniano es una serie de n+1 pasos donde en el paso 1 estamos parados sobre el primer nodo, y en el paso n+1 nuevamente en el primer nodo. | ||
Es evidente que en pasos consecutivos nos moveremos de una partición a otra.. | Es evidente que en pasos consecutivos nos moveremos de una partición a otra.. | ||
De este modo vemos que empezamos en el paso 1 en una particion (llamemosle V1), luego en el paso 3 volveremos a V1, en el paso 5 volveremos a V1, ....asi hasta llegar a n (ya que n es impar), luego en el paso n+1 deberá estar necesariamente en la otra partición, pues entonces, en el paso n+1 estará en una partición distinta de la partición de donde empezamos, por lo que no se puede formar un circuito hamiltoniano. | De este modo vemos que empezamos en el paso 1 en una particion (llamemosle V1), luego en el paso 3 volveremos a V1, en el paso 5 volveremos a V1, ....asi hasta llegar a n (ya que n es impar), luego en el paso n+1 deberá estar necesariamente en la otra partición, pues entonces, en el paso n+1 estará en una partición distinta de la partición de donde empezamos, por lo que no se puede formar un circuito hamiltoniano. | ||
Se puede formalizar de muchos modos, pero la idea suele ser la misma. | Se puede formalizar de muchos modos, pero la idea suele ser la misma. | ||
==Ejercicio 08.16:== | ==Ejercicio 08.16:== | ||
Se puede probar de manera constructiva. | Se puede probar de manera constructiva. | ||
Se prueban los nodos para n=4, (el peor caso seria cuando todos tienen grado 2). | Se prueban los nodos para n=4, (el peor caso seria cuando todos tienen grado 2). | ||
Luego, se puede ver que partiendo de un grafo G que cumple la propiedad, y agregando un nodo tal que la propiedad se mantenga, se puede formar un circuito hamiltoniano usando el camino hamiltoniano de G, y buscando dos nodos consecutivos a los cuales el nodo agregado este conectado. Al haber dos nodos consecutivos a los cuales el nodo agregado esta conectado, el circuito hamiltoniano se formará | Luego, se puede ver que partiendo de un grafo G que cumple la propiedad, y agregando un nodo tal que la propiedad se mantenga, se puede formar un circuito hamiltoniano usando el camino hamiltoniano de G, y buscando dos nodos consecutivos a los cuales el nodo agregado este conectado. Al haber dos nodos consecutivos a los cuales el nodo agregado esta conectado, el circuito hamiltoniano se formará llendo de uno de esos nodos al nuevo nodo agregado, y del nodo agregado, al consecutivo que recien dijimos. | ||
==Ejercicio 08.17:== | ==Ejercicio 08.17:== | ||
Dem: Si G es hamiltoniano entonces, trivialmente, tambien G+uv lo es. Sup. que G+uv es hamiltoniano pero G no lo es. Entonces, como en la dem. del teorema 4.3, obtenemos (4.4). Pero esto contradice la hipotesis (4.5) | Dem: Si G es hamiltoniano entonces, trivialmente, tambien G+uv lo es. Sup. que G+uv es hamiltoniano pero G no lo es. Entonces, como en la dem. del teorema 4.3, obtenemos (4.4). Pero esto contradice la hipotesis (4.5) | ||
<br>[Sacado del libro de North-Holland.. para leerlo tranquilos :P] | <br>[Sacado del libro de North-Holland.. para leerlo tranquilos :P] | ||
<br>Teorema 4.3: si G es un grafo de tal que | <br>Teorema 4.3: si G es un grafo de tal que n>=3 y para todo v, d(v) >= n/2 -> G es hamiltoniano | ||
<br>Dem: Sup. que NO. como n >= 3, G no puede ser completo. Sean u,v vertices no ady. en G. Por eleccion de G, G+uv es hamiltoniano. Mas aun, como G no lo es, cada ciclo hamiltoniano de G+uv debe contener el eje uv. Entonces hay un camino hamiltoniano {v1,..,vk} en G tal que u=v1 y v=vk. | <br>Dem: Sup. que NO. como n >= 3, G no puede ser completo. Sean u,v vertices no ady. en G. Por eleccion de G, G+uv es hamiltoniano. Mas aun, como G no lo es, cada ciclo hamiltoniano de G+uv debe contener el eje uv. Entonces hay un camino hamiltoniano {v1,..,vk} en G tal que u=v1 y v=vk. | ||
<br>Sean S={vi | hay eje u-v(i+1)} y T={vi | hay eje v(i)-v}. Como vk no esta en S∪T -> |S∪T| < n -> |S∩T| = 0 (ya que si contuviera algun vertice vi, entonces G tendria el ciclo hamiltoniano {v1,..,vi,vk,vk-1,..,vi+1,v1} que seria ABS). Usando lo anterior obtenemos d(u)+d(v)=|S|+|T|=|S∪T|+|S∩T| < n (este es el 4.4). Pero esto contradice HI (para todo v, d(v) >= n/2, con lo cual d(u)+d(v) >= 2*n/2 = n) ABS | <br>Sean S={vi | hay eje u-v(i+1)} y T={vi | hay eje v(i)-v}. Como vk no esta en S∪T -> |S∪T| < n -> |S∩T| = 0 (ya que si contuviera algun vertice vi, entonces G tendria el ciclo hamiltoniano {v1,..,vi,vk,vk-1,..,vi+1,v1} que seria ABS). Usando lo anterior obtenemos d(u)+d(v)=|S|+|T|=|S∪T|+|S∩T| < n (este es el 4.4). Pero esto contradice HI (para todo v, d(v) >= n/2, con lo cual d(u)+d(v) >= 2*n/2 = n) ABS | ||
==Ejercicio 08.18:== | ==Ejercicio 08.18:== | ||
Línea 177: | Línea 143: | ||
Si tenemos un grafo de <math>m = \frac{n(n-1)}{2}</math> en cada paso vamos a sacar <math>n</math> ejes así que como cota superior no podemos tener más de <math>\frac{n(n-1)}{2n}</math> circuitos hamiltonianos disjuntos en ejes que es lo mismo que: <math>\lfloor\frac{(n-1)}{2}\rfloor</math>. | Si tenemos un grafo de <math>m = \frac{n(n-1)}{2}</math> en cada paso vamos a sacar <math>n</math> ejes así que como cota superior no podemos tener más de <math>\frac{n(n-1)}{2n}</math> circuitos hamiltonianos disjuntos en ejes que es lo mismo que: <math>\lfloor\frac{(n-1)}{2}\rfloor</math>. | ||
==Ejercicio 08.19:== | ==Ejercicio 08.19:== | ||
Sea V = {v1,v2,..,v6}. Como son todos de grado 3, entonces por ej. v1 esta conectado a v2,v3,v4. Entonces c/u de estos 3 esta conectado a otros 2 vertices. Entonces por ej. v4 esta conectado a v5 y v6. Esto implica que v2 y v3 solo les queda para conectarse a v5 y v6. Luego, el grafo resultante es de la forma del K33 (si toman v1,v5,v6 como una particion y v2,v3,v4 como la otra se dan cuenta), y se puede ver que K33 tiene circuito hamiltoniano. | Sea V = {v1,v2,..,v6}. Como son todos de grado 3, entonces por ej. v1 esta conectado a v2,v3,v4. Entonces c/u de estos 3 esta conectado a otros 2 vertices. Entonces por ej. v4 esta conectado a v5 y v6. Esto implica que v2 y v3 solo les queda para conectarse a v5 y v6. Luego, el grafo resultante es de la forma del K33 (si toman v1,v5,v6 como una particion y v2,v3,v4 como la otra se dan cuenta), y se puede ver que K33 tiene circuito hamiltoniano. | ||
==Ejercicio 08.20:== | ==Ejercicio 08.20:== | ||
Línea 210: | Línea 169: | ||
<br>c) | <br>c) | ||
==Ejercicio 08.25:== | ==Ejercicio 08.25:== | ||