Ciclo hamiltoniano, verificando y encontrando

Question

Si tenemos un algoritmo que en el tiempo polinomial dice que si un gráfico G tiene un ciclo hamiltoniano, ¿podemos tener un algoritmo que en el tiempo polinomial encontrar un ciclo hamiltoniano?

Mi intento es eliminar un borde del gráfico G y tener G ', después de ejecutar el algoritmo en g' para saber si tiene un ciclo hamiltoniano si no significa que el borde está en un ciclo hamiltoniano.Ahora no sé cómo continuar.

Answer 1

Let $ P $ Sé un camino simple arbitrario en la gráfica. Si $ p $ aparece en un ciclo hamiltoniano de la gráfica, puede eliminar todos los vértices de $ P $ Excepto el primer y el último vértice, conecte estos dos vértices con un borde y el gráfico resultante debe ser hamiltoniano.

Teniendo esto en cuenta, podemos construir el ciclo Hamiltoniano paso a paso a partir de la ruta de la longitud, ya que ya describió cómo construir un camino de este tipo. Luego, podemos extender una ruta de longitud $ i $ a una ruta de longitud $ i + 1 $ usando El truco de arriba, donde intentamos todos los vecinos del último vértice en la ruta como un próximo vértice y aplicamos el truco de arriba para verificar si existe un ciclo hamiltoniano donde la nueva ruta es parte del ciclo. Tenga en cuenta que llamamos a la caja negra a la mayoría de los $ m:= | e | $ veces. Una vez que llegamos a un camino de longitud $ n-3 $ es fácil completar la ruta en un ciclo hamiltoniano en tiempo lineal.