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 170: | Línea 170: | ||
* 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:== |