• Asignatura: Matemáticas
  • Autor: michi0501p758rn
  • hace 7 años

¿Cuál es la diferencia de un camino y un ciclo hamiltoniano?

Respuestas

Respuesta dada por: colegil1337
1

Respuesta:

la diferencia es que son lo mismo solo que el ciclo hamiltoniano es un camino en las matemáticas y el camino es un camino en el sentido de

Explicación paso a paso:

el ciclo hamiltoniano es un camino en las matemáticas y el camino es un camino en el sentido de camino para caminar o en cualquier otro sentido y en todas las definiciones de camino en el diccionario en cambio el ciclo hamiltoniano es = Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.

El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo1​ y como tal aparece en la lista de los 21 problemas NP-completos de Karp.

El nombre proviene del matemático irlandés sir William Rowan Hamilton (1805-65), que propuso viajar a veinte ciudades del mundo, representadas como los vértices de un dodecaedro regular, siguiendo las aristas del dodecaedro.

No obstante, los ciclos y caminos actualmente denominados hamiltonianos aparecieron mucho antes. Al parecer, ya en el siglo IX el poeta indio Rudrata nombra el llamado camino del caballo. Se trata de una sucesión de movimientos del caballo sobre un arcidriche de manera que esta pieza, el caballo, visite todos y cada uno de los escaques una sola vez. Se trata, en consecuencia, de encontrar un camino hamiltoniano en un grafo cuyos vértices son los escaques de un arcidriche de manera que dos vértices son adyacentes si y sólo si se puede pasar de uno a otro mediante un movimiento de caballo.

Definición

Un camino sin vértices repetidos que recorre todos los vértices del grafo se llama camino hamiltoniano.

Un camino hamiltoniano que sea un circuito se llama circuito hamiltoniano.

Un grafo que tiene un circuito hamiltoniano se llama grafo hamiltoniano.

Para grafos dirigidos, o dígrafos, las definiciones correspondientes tienen en cuenta que las aristas están dirigidas.

Un camino dirigido en un digrafo es camino dirigido hamiltoniano si visita todos los vértices del digrafo sin repetir ninguno.

Un ciclo dirigido hamiltoniano en un digrafo es un camino dirigido hamiltoniano que es ciclo.

El grafo dirigido es digrafo hamiltoniano si contiene un ciclo dirigido hamiltoniano.

Al contrario que en el caso de los grafos eulerianos, no se conoce ninguna caracterización de los grafos hamiltonianos. Desde luego, todos los grafos hamiltonianos son conexos pero no todos los grafos conexos son hamiltonianos.

Ejemplos

Todos los grafos ciclos son hamiltonianos.

Los grafos completos con más de dos vértices son hamiltonianos.

Todos los campeonatos poseen caminos dirigidos hamiltonianos.2​ Se puede consultar la demostración en [Theorem 2.2.13​].

Todos los sólidos platónicos (el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro), considerados como grafos, son hamiltonianos.4​

Entre los grafos eulerianos los hay que son hamiltonianos y los hay que no lo son, y entre los grafos hamiltonianos los hay que son eulerianos y los hay que no lo son.

Preguntas similares