Estoy buscando una explicación sobre cómo reducir el problema del ciclo hamiltoniano al del camino hamiltoniano (para demostrar que también este último es NP-completo). No he podido encontrar ninguna en la web, ¿puede alguien ayudarme? (enlazar una fuente también es bueno).
Gracias.
Nota: La siguiente es una reducción de Cook y no una reducción de Karp. Las definiciones modernas de NP-Completitud utilizan la reducción de Karp.
Para una reducción del ciclo hamiltoniano a la trayectoria.
Dado un gráfico $G$ del que necesitamos encontrar el Ciclo Hamiltoniano, para una sola arista $e = \{u,v\}$ añadir nuevos vértices $u'$ y $v'$ tal que $u'$ está conectado sólo a $u$ y $v'$ está conectado sólo a $v$ para dar un nuevo gráfico $G_e$ .
$G_e$ tiene una trayectoria hamiltoniana si y sólo si $G$ tiene un ciclo hamiltoniano con la arista $e=\{u,v\}$ .
Ejecutar el algoritmo del camino hamiltoniano en cada $G_e$ para cada arista $e \in G$ . Si todos los grafos no tienen un camino hamiltoniano, entonces $G$ no tiene ningún ciclo hamiltoniano. Si al menos una $G_e$ tiene una trayectoria hamiltoniana, entonces $G$ tiene un ciclo hamiltoniano que contiene la arista $e$ .
Creo que te equivocas sobre la reducción de HC a HP (respuesta nº 1). Si nos fijamos en este caso : U* ------------ V y aplique su reducción: U' -------- U* ------------ V* ----------V'* Es muy fácil ver que en el gráfico después de la reducción hay un camino hemilton .. (u' -> u -> v -> v') Espero su respuesta (tal vez no entendí la reducción)
@LitalZubery: Si te he entendido bien, ¿te refieres al caso especial en el que G es exactamente una única arista? Sí, eso debería mencionarse, pero en realidad no rompe la prueba, ya que un número finito de excepciones no afectará a la prueba de NP-Completitud.
Se trata de una reducción del Ciclo de Hamilton no dirigido al Camino de Hamilton no dirigido. Toma un gráfico $G$ y devuelve un gráfico $f(G)$ tal que $G$ tiene un ciclo de Hamilton si $f(G)$ tiene un camino de Hamilton.
Dado un gráfico $G = (V,E)$ construimos un gráfico $f(G)$ de la siguiente manera.
Dejemos que $v \in V$ sea un vértice de G, y sea $v',s,t \notin V$ .
Queremos hacer $v'$ una "copia" de $v$ y añadir vértices de grado uno; $s,t$ conectado a $v,v'$ respectivamente. (Véase la figura 1.)
Eso es, $f(G)$ tiene vértices $V\cup \{v',s,t\}$ y bordes $E\cup\{(v',w)|(v,w)\in E\}\cup\{(s,v),(v',t),(v,v')\}$ .
Ahora bien, si $G$ tiene un Ciclo de Hamilton, podemos escribirlo en la forma $(v,u),edges,(u',v)$ , donde $edges$ es una lista de aristas que deben formar un camino simple $u\ldots u'$ visitando todos los vértices menos $v$ . Pero entonces, $(s,v),(v,u),edges,(u',v'),(v',t)$ es un camino de Hamilton entre $s$ y $t$ en $f(G)$ .
Si por el contrario $f(G)$ tiene un Camino de Hamilton, entonces debe tener $s$ y $t$ como puntos finales, ya que tienen grado 1. En cuyo caso debe (hasta la inversión) ser de la forma $(s,v),(v,y),edges',(y',v'),(v',t)$ . Pero entonces, $G$ tiene un ciclo de Hamilton $(v,y),edges',(y',v)$ .
Para el caso dirigido,
Dado $\langle G=(V,E)\rangle$ para el ciclo hamiltoniano, podemos construir la entrada $\langle G',s,t\rangle$ : elige un vértice $u \in V$ y dividirlo en dos vértices, de forma que las aristas que salen de $u$ , saldrá de $s$ y los vértices que entran en $u$ , entrará a $t$ .
La respuesta mencionada es correcta para mostrar la reducción, pero tengo esta idea que es más rápida que la idea presentada. Por favor, corregidme si me equivoco. Si el camino de jamón dice que no para incluso un solo vértice, entonces el ciclo de jamón dice que no. Esto significa que todos los vértices deben decir que sí para el camino de jamón (por lo tanto, un método de identificación para pedir cada egde).Un método más rápido sería: Elegir cualquier vértice. Para cada una de sus aristas elimine la arista y añada 2 vértices y únalos de la misma manera que se menciona en la respuesta. Si para cualquier arista se elimina y se añaden 2 nuevos vértices el camino del jamón dice que sí, entonces la salida es Sí.
Por favor, corríjanme si me equivoco.
Esto es falso, al menos en la breve versión que has dado. Deje que $G$ sea el grafo con cinco vértices y cinco aristas que corresponde a la forma de la letra mayúscula A . Eliminando la arista horizontal de cruce se obtienen cinco vértices y cuatro aristas que designamos gráfico $G'$ . Mientras que $G'$ tiene un camino hamiltoniano (es un camino), el grafo $G$ no tiene un ciclo hamiltoniano.
Oh, es mi error no haber escrito la reducción completa. Gracias por señalar que hardmath. Debo decir que si hay un camino Hamiltoniano en G' de u a v donde (u,v) es la arista eliminada. Y si G es un grafo dirigido, también debemos comprobar si la dirección de la arista (u,v) y elegir el punto de partida adecuado u o v para el camino hamiltoniano. Por cierto, creo que mi reducción mediante la eliminación de un borde no es adecuada, ya que debe ser vértice u y vértice v deben ser los vértices inicial y final (o viceversa). Por lo tanto, deberíamos añadir dos vértices más en lugar de eliminar la arista.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Abaco, mi respuesta, que has aceptado, es errónea. Aryabhata ha dado una solución correcta.
1 votos
@user96758: Creo que tienes razón. Dado un vértice, entre todas las aristas unidas a él, al menos 2 están en un HC (si es que existe). De hecho, cuando una de estas 2 aristas, digamos $e$ (sin pérdida de generalidad, $e = \{u,v\}$ de $u$ a $v$ ), el nuevo gráfico tendrá un HP a partir de $v$ y terminando en $u$ . Así que no necesitamos vértices adicionales para reducir el problema HC a HP. Por otro lado, como el coste de reducción es polinómico en todos los métodos mencionados aquí y por otros usuarios, acabamos de demostrar lo mismo.
0 votos
Aquí encontré una solución mucho más compacta: aduni.org/courses/algorithms/courseware/psets/