algorithm - problema - Diferencia entre el camino hamiltoniano y el camino euler
problema de los ciclos hamiltonianos (8)
Definiciones de la teoría de gráficos
(En orden descendente de generalidad)
Walk : una secuencia de bordes donde el final de un borde marca el comienzo del siguiente borde
Sendero : una caminata que no repite ningún borde. Todos los senderos son paseos.
Camino : una caminata donde cada vértice se atraviesa exactamente una vez. (caminos utilizados para referirse a paseos abiertos, la definición ha cambiado ahora) La propiedad de atravesar vértices una sola vez significa que los bordes también se cruzan una sola vez, por lo tanto, todos los caminos son senderos.
Senderos hamiltonianos y senderos eulerianos
Camino hamiltoniano : visita cada vértice en el gráfico (exactamente una vez, porque es un camino)
Sendero euleriano : visita cada borde del gráfico exactamente una vez (porque es un camino, los vértices se pueden cruzar más de una vez).
¿Puede alguien decirme la diferencia entre el camino hamiltoniano y el camino euler? ¡Parecen similares!
Están relacionados pero no son dependientes ni se excluyen mutuamente. Si un gráfico tiene un ciclo de Eurler, puede tener o no un ciclo de Hamilton y viceversa.
Los ciclos de Euler visitan cada borde en el gráfico exactamente una vez. Si hay vértices en el gráfico con más de dos aristas, entonces, por definición, el ciclo pasará por esos vértices más de una vez. Como resultado, los vértices se pueden repetir pero los bordes no.
Los ciclos hamiltonianos visitan cada vértice en el gráfico exactamente una vez (similar al problema del vendedor ambulante). Como resultado, ni los bordes ni los vértices se pueden repetir.
La ruta de Euler es un gráfico que usa cada borde (NOTA) del gráfico exactamente una vez . El circuito de Euler es un camino euler que regresa al punto de inicio después de cubrir todos los bordes .
Mientras que hamilton path es un gráfico que cubre todos los vértices (NOTA) exactamente una vez. Cuando este camino regrese a su punto de partida, este camino se llama circuito hamilton.
La ruta euleriana debe visitar cada borde exactamente una vez, mientras que la ruta hamiltoniana debe visitar cada vértice exactamente una vez.
Un camino de Euler es un camino que cruza cada borde exactamente una vez sin repetir, si termina en el vértice inicial, entonces es un ciclo de Euler.
Un camino hamiltoniano pasa a través de cada vértice (nótese cada borde), exactamente una vez, si termina en el vértice inicial, entonces es un ciclo hamiltoniano.
En un camino de Euler, puede pasar por un vértice más de una vez.
En un camino hamiltoniano, es posible que no pases por todos los bordes.
Un camino hamiltoniano visita cada nodo (o vértice) exactamente una vez, y un camino euleriano atraviesa cada borde exactamente una vez.
Una ruta de Euler es una ruta que usa cada borde de un gráfico exactamente una vez. Y debe tener exactamente dos vértices impares. La ruta comienza y termina en diferentes vértices. Un ciclo de Hamilton es un ciclo que contiene cada vértice del gráfico, por lo tanto, no puede usar todos los bordes del gráfico.
Usaré un ejemplo común en biología; reconstruir un genoma haciendo muestras de ADN.
Asamblea de novo
Para construir un genoma a partir de lecturas cortas, es necesario construir un gráfico de esas lecturas. Lo hacemos al dividir las lecturas en k-mers y ensamblarlas en un gráfico.
Podemos reconstruir el genoma visitando cada nodo una vez como en el diagrama. Esto se conoce como ruta hamiltoniana.
Desafortunadamente, la construcción de dicha ruta es NP-difícil. No es posible derivar un algoritmo eficiente para resolverlo. En cambio, en bioinformática, construimos un ciclo euleriano donde un borde representa una superposición.
