Saltar al contenido

Reducción del ciclo hamiltoniano al camino hamiltoniano

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) $.

Ciclo de Hamilton a reducción de la ruta de Hamilton

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.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *