Tengo gráficos planos relativamente pequeños (40-80 nodos) cúbicos (3-regulares), y tengo que decidir su Hamiltonicidad. Soy consciente del hecho de que esta tarea es NP-completo, pero espero que para los algoritmos de tiempo asintóticamente exponenciales que son sin embargo muy rápido para el tamaño gráfico Estoy interesado enEncontrar ciclos hamiltonianos en gráficos planos cúbicos
40 nodos parece factible. Está eligiendo 40 de 60 bordes para incluir.
Probemos una búsqueda en profundidad.
Para comenzar, elija un vértice V. Tendrá que excluir exactamente uno de sus 3 bordes de incidente. Pruebe estas 3 posibilidades de a una por vez. Cuando elige un borde para excluir, está forzando la inclusión de 4 bordes. Después de esto, llamaremos a los vértices del borde excluido "usado".
Si pudieras repetir este proceso 10 veces, habrías elegido los 40 bordes, buscando solo 3^10 (59049) posibilidades. Por supuesto, te quedarás sin vértices "aislados" después de que se hayan determinado suficientes bordes.
Pero, ahora tenemos una idea para un algoritmo. En cada paso, intenta elegir un vértice con el menor número de vecinos "usados". En realidad, elegir un vértice con 2 vecinos usados es lo mejor, ya que el borde utilizado es forzado. No estoy seguro de si elegir un vértice con 1 o 0 vecinos usados es el siguiente mejor. ¡Prueba ambas formas! (Y 3 vecinos usados indican una búsqueda fallida)
Cuando hayamos terminado de seleccionar los bordes, verifique si forman un solo ciclo.
¿Tiene algunos gráficos de muestra? Podría intentar una implementación simple.
de http://mathworld.wolfram.com/HamiltonianCycle.html:. "Rubin (1974) describe un procedimiento de búsqueda eficiente que puede encontrar algunos o todos los caminos y circuitos de Hamilton en un gráfico que usa deducciones que reducen en gran medida el retroceso y las conjeturas ".
el papel está a la venta aquí: http://portal.acm.org/citation.cfm?id=321850.321854