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 158: | Línea 158: | ||
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 170: | Línea 167: | ||
* http://www.proofwiki.org/wiki/Ore%27s_Theorem | * http://www.proofwiki.org/wiki/Ore%27s_Theorem | ||
* http://www.proofwiki.org/wiki/Dirac%27s_Theorem | * http://www.proofwiki.org/wiki/Dirac%27s_Theorem | ||
---- | |||
<p>Otra idea para la vuelta podría ser:</p> | |||
<p>Supongamos que G+uv es hamiltoniano pero G no lo es. Entonces, usando el contra-recíproco del Teorema de Dirac: (<math> n < 3 </math> ó <math> \exists v,\ d(v) < \frac{n}{2} </math>). Notar que la HI general nos dice que G tiene 3 o mas nodos.</p> | |||
<p>Entonces los vértices u y v que no son adyacentes en G, <math>d(u) + d(v) < \frac{n}{2} + \frac{n}{2} = n \Rightarrow d(u) + d(v) < n </math>. ABS. | |||
==Ejercicio 08.18:== | ==Ejercicio 08.18:== | ||
Línea 177: | Línea 181: | ||
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:== |