Encontrar el número de ciclos hamiltonianos para un gráfico cúbico

Question

Un problema en el que estoy trabajando se reduce a encontrar un bucle cerrado que visite todos los nodos de un cubo. Recordé que esto se llamaba un ciclo hamiltoniano, y entonces necesitaba encontrar el número de Ciclos hamiltonianos .

He buscado que hay 12 ciclos hamiltonianos dirigidos distintos para el cubo ( vía MathWorld )

He calculado los 6 ciclos no dirigidos (como cada camino puede ir en 2 direcciones, esto hace un total de 6x2 = 12 ciclos dirigidos).

¿Hay alguna manera de demostrar que estos son todos los ciclos hamiltonianos no dirigidos distintos? O se encuentra por el método de agotamiento (es decir, ensayo y error y básicamente encontrar que ningún otro camino funciona).

Estaría encantado de citar Mathworld diciendo que esta es la respuesta, pero me parece algo insatisfactorio no dar más razones.

Hice muchas, muchas búsquedas en la web, pero seguí encontrando complicados apuntes de cursos no relacionados con esta pregunta. Sospecho que sería una pregunta básica de teoría de grafos, pero de alguna manera se me escapa una referencia.

Por favor, hágame saber si hay una manera de demostrar que hay 12 ciclos hamiltonianos dirigidos en un gráfico cúbico. Las referencias serían muy apreciadas también - estoy feliz de trabajar a través de un poco de teoría de grafos para entender por qué. Gracias.

Answer 1

Elige un punto, arbitrariamente (ya que la gráfica es simétrica). Puedes elegir la trayectoria hamiltoniana que pasa por ese vértice en $3$ caminos, eligiendo efectivamente cuáles de sus aristas incidentes no estarán en el camino. El vértice adyacente que ahora no será adyacente en el camino también ha tenido su camino local elegido, ya que hemos eliminado la opción de una arista.

Para completar el camino a partir de estos dos cortos tramos iniciales, un extremo se enlaza directamente y el otro debe conectarse a través de los vértices aún no incluidos en el camino - $2$ opciones. Puede demostrarlo eligiendo la opción de no conexión en un extremo de un tramo corto, y luego observando que el otro extremo del mismo tramo debe ahora conectarse directamente con el otro tramo inicial del camino para evitar un ciclo corto.

Así que hay un total de $3\times 2 = 6$ ciclos hamiltonianos no dirigidos para el cubo, como has encontrado.