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.. | ||
Línea 154: | Línea 146: | ||
==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] | ||
Línea 177: | Línea 163: | ||
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:== |