Camino hamiltoniano

Ciclo hamiltoniano.

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-completo.

Los caminos y ciclos hamiltonianos se llaman así en honor de William Rowan Hamilton, inventor de un juego que consistía en encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, aunque su solución no era generalizable a todos los grafos.

Definición

Un camino hamiltoniano es un camino que pasa por cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano si es un ciclo que pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.

Estos conceptos se pueden extender para los grafos dirigidos los cuales son igual a un carro.

Other Languages
Deutsch: Hamiltonweg
magyar: Hamilton-út
Bahasa Indonesia: Lintasan Hamilton
한국어: 해밀턴 경로
Nederlands: Hamiltonpad
norsk bokmål: Hamiltonvei
Piemontèis: Graf hamiltonian
Simple English: Hamiltonian path
slovenčina: Hamiltonovský graf
slovenščina: Hamiltonova pot
српски / srpski: Хамилтонов пут
svenska: Hamiltonväg
Türkçe: Hamilton yolu
українська: Гамільтонів шлях
Tiếng Việt: Đường đi Hamilton
中文: 哈密顿图