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 114: | Línea 114: | ||
==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 121: | ||
==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. | ||
Ó mucho mas facil: | |||
por, (COR) Si <math>\forall | por, (COR) Si <math>\forall</math> v en V, d(v) >= n/2 -> G contiene un circuito hamiltoniano, | ||
que es lo mismo que | que es lo mismo que d(grado minimo) >=n/2 -> G Hamiltoniano. | ||
Entonces por enunciado, | Entonces por enunciado, d(grado minimo) >=n-2 | ||
n-2>=n/2 <=> n>=4 | |||
y ahi termino. | |||
==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 155: | ||
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:== |