En esta semana hemos analizado el problema de planaridad de grafos y la caracterización de grafos no planos mediante la existencia de subgrafos homeomorfos a K_{3,3} o K_5 (o Teorema de Kuratowski).
Hemos jugado con la búsqueda de ciclos Hamiltonianos en ciertos grafos.
Cabe notar que el reconocimiento de un grafo Euleriano es una tarea simple (ver que los grados son pares y que el grafo es conexo). No obstante, el reconocimiento de grafos Hamiltonianos es uno de los problemas célebres de teoría de la computación.
Les invito a que busquen condiciones suficientes para determinar si un grafo es Hamiltoniano. Pueden encontrar una en el libro de Grimaldi. Además, pueden ver que el reconocimiento de ciclos Hamiltonianos es un problema perteneciente a la clase de problemas NP-Completos (libro de Garey and Johnson, recomendado en bibliografía adicional).
Ojalá se entretengan con los juegos que Hamilton ha inventado de antaño...¡y que tan poco éxito tuvo en aquella época en la galería de juegos de Londres!
Cordialmente,
Pablo.