Diferencia entre el camino hamiltoniano y el camino de euler

El sendero euleriano debe visitar cada borde exactamente una vez, mientras que el sendero hamiltoniano debe visitar cada vértice exactamente una vez.

Definiciones de la Teoría de Grafos

(En orden descendente de generalidad)

• Walk : una secuencia de aristas donde el final de una arista marca el comienzo de la siguiente arista

• Trail: una caminata que no repite ningún borde. Todos los senderos son caminatas.

• Path : una caminata donde cada vértice es atravesado exactamente una vez. (rutas usadas para referirse a caminos abiertos, la definición ha cambiado ahora) La propiedad de traversing vértices solo una vez significa que los bordes también se cruzan solo una vez, por lo tanto, todos los caminos son senderos.

Caminos hamiltonianos y senderos eulerianos

• Camino hamiltoniano : visita cada vértice en el gráfico (exactamente una vez, porque es un camino)

• Eulerian trail : visita cada arista en el gráfico exactamente una vez (debido a que es un sendero, los vértices pueden cruzarse más de una vez.)

Un camino hamiltoniano visita cada nodo (o vértice) exactamente una vez, y un camino euleriano atraviesa cada arista exactamente una vez.

Están relacionados pero no son ni dependientes ni mutuamente excluyentes. Si un grafo tiene un ciclo de Eurler, puede o no tener también un ciclo Hamiltoniano y viceversa.

Euler cycles visita cada arista 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á a través de esos vértices más de una vez. Como resultado, los vértices se pueden repetir, pero las aristas no.

ciclos Hamiltonianos visite cada vértice en el gráfico exactamente una vez (similar al problema del vendedor ambulante). Como resultado, ni las aristas ni los vértices pueden repetirse.

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 dividiendo las lecturas en k-mers y ensamblándolas en un gráfico.

Podemos reconstruir el genoma visitando cada nodo una vez como en el diagrama. Esto se conoce como camino hamiltoniano.

Desafortunadamente, la construcción tal camino es NP-duro. No es posible derivar un algoritmo eficiente para resolverlo. En cambio, en bioinformática construimos un ciclo euleriano donde una arista representa una superposición.

Un camino de Euler es un camino que usa cada arista de un gráfico exactamente una vez.y debe tener exactamente dos vértices impares.el camino comienza y termina en diferentes vértices. Un ciclo hamiltoniano es un ciclo que contiene cada vértice del gráfico, por lo tanto, no puede usar todos los bordes del gráfico.

El trazado de Euler es un gráfico que usa cada arista(NOTA) del gráfico exactamente una vez. El circuito de Euler es un camino de euler que vuelve a su punto de partida después de cubrir todas las aristas.

Mientras que hamilton path es un gráfico que cubre todos los vértices(NOTA) exactamente una vez. Cuando este camino vuelve a su punto de partida que este camino se llama circuito de Hamilton.