El paso a paso o código que hallarás en este post es la solución más sencilla y válida que encontramos a tus dudas o dilema.
Solución:
Nota: Lo siguiente es una reducción de Cook y no una reducción de Karp. Las definiciones modernas de NP-Completeness utilizan la reducción de Karp.
Para una reducción del ciclo hamiltoniano a la ruta.
Dado un gráfico $ G $ del cual necesitamos encontrar el ciclo hamiltoniano, para un solo borde $ e = u, v $ agregue nuevos vértices $ u ‘$ y $ v’ $ de manera que $ u ‘$ esté conectado solo a $ u $ y $ v ‘$ está conectado solo a $ v $ para dar un nuevo gráfico $ G_e $.
$ G_e $ tiene un camino hamiltoniano si y solo si $ G $ tiene un ciclo hamiltoniano con la arista $ e = u, v $.
Ejecute el algoritmo de ruta de Hamilton en cada $ G_e $ para cada borde $ e en G $. Si todas las gráficas no tienen un camino hamiltoniano, entonces $ G $ no tiene un ciclo hamiltoniano. Si al menos un $ G_e $ tiene una trayectoria hamiltoniana, entonces $ G $ tiene un ciclo hamiltoniano que contiene la arista $ e $.
Se trata de una reducción del ciclo de Hamilton sin dirección a la ruta de Hamilton sin dirección. Toma una gráfica $ G $ y devuelve una gráfica $ f (G) $ tal que $ G $ tiene un ciclo de Hamilton sif $ f (G) $ tiene una ruta de Hamilton.
Dado un gráfico $ G = (V, E) $, construimos un gráfico $ f (G) $ de la siguiente manera.
Sea $ v en V $ un vértice de G, y sea $ v ‘, s, t notin V $.
Queremos hacer de $ v ‘$ una “copia” de $ v $, y agregar vértices de grado uno; $ s, t $, conectados a $ v, v ‘$, respectivamente. (Ver figura 1).
Es decir, $ f (G) $ tiene vértices $ V cup v ‘, s, t $ y aristas $ E cup (v’, w) taza (s, v), (v ‘, t), (v, v’) $.
Ahora, si $ G $ tiene un ciclo de Hamilton, podemos escribirlo en la forma $ (v, u), bordes, (u ‘, v) $, donde $ bordes $ es una lista de bordes que deben formar una ruta simple $ u ldots u ‘$ visitando todos los vértices menos $ v $. Pero entonces, $ (s, v), (v, u), bordes, (u ‘, v’), (v ‘, t) $ es una ruta de Hamilton entre $ s $ y $ t $ en $ f (G PS
Si, por otro lado, $ f (G) $ tiene una ruta de Hamilton, entonces debe tener $ s $ y $ t $ como extremos, ya que tienen grado 1. En cuyo caso debe (hasta la inversión) ser de la forma $ (s, v), (v, y), bordes ‘, (y’, v ‘), (v’, t) $. Pero entonces, $ G $ tiene un ciclo de Hamilton $ (v, y), bordes ‘, (y’, v) $.
Para el caso dirigido,
Dado $ langle G = (V, E) rangle $ para el ciclo hamiltoniano, podemos construir input $ langle G ‘, s, t rangle $: elija un vértice $ u en V $ y divídalo en dos vértices, de modo que las aristas que salen de $ u $ saldrán de $ s $ y los vértices que llegan a $ u $, llegarán a $ t $.
Sección de Reseñas y Valoraciones
Acuérdate de que puedes permitirte explicar si acertaste tu incógnita en el momento justo.