Un camino hamiltoniano visita todos los vértices exactamente una vez. Si además regresa al punto inicial, forma un ciclo hamiltoniano y el grafo se denomina hamiltoniano.
Los problemas hamiltonianos preguntan si es posible recorrer todos los lugares sin repetir ninguno. A diferencia de los caminos mínimos, aquí importa cubrir el conjunto completo de vértices.
Esta estructura aparece en planificación, secuenciación, rompecabezas y en el problema del viajante estudiado anteriormente.
Un camino hamiltoniano contiene todos los vértices del grafo exactamente una vez. No necesita terminar donde comenzó.
Puede haber muchos caminos hamiltonianos, uno solo o ninguno.
Un ciclo hamiltoniano visita todos los vértices exactamente una vez y contiene una arista que une el último con el primero.
Un grafo es hamiltoniano si contiene al menos uno de estos ciclos.
Todo ciclo hamiltoniano produce un camino hamiltoniano al quitar una arista. La implicación inversa no siempre se cumple.
Por ejemplo, un camino simple con varios vértices es hamiltoniano como camino, pero no contiene ninguna arista que permita regresar del extremo final al inicial.
Si un grafo posee un ciclo hamiltoniano, debe ser conectado y cada vértice debe tener grado al menos 2.
Estas condiciones permiten descartar casos, pero no garantizan un ciclo: existen grafos conectados de grado mínimo 2 que no son hamiltonianos.
Avanza por la búsqueda. La rama A–B–D–E–C termina sin poder completar el ciclo; el algoritmo retrocede y prueba E–F hasta encontrar una solución.
Camino parcial
Vértices disponibles
Acción actual
Un grafo hamiltoniano con al menos tres vértices no puede tener un vértice de corte. Si se elimina cualquier vértice de su ciclo hamiltoniano, los restantes todavía quedan conectados mediante un camino.
Si G es hamiltoniano, al eliminar un conjunto S de vértices no pueden quedar más de |S| componentes.
También es una condición necesaria, no una caracterización completa.
Sea G un grafo simple con n ≥ 3 vértices. Si cada vértice tiene grado al menos n/2, entonces G es hamiltoniano.
Dirac proporciona una condición suficiente. Un grafo que no la cumple todavía puede ser hamiltoniano.
Sea G simple con n ≥ 3. Si para cada par de vértices no adyacentes u y v se cumple grado(u) + grado(v) ≥ n, entonces G es hamiltoniano.
Ore generaliza la intuición de que una densidad alta fuerza la existencia de un ciclo global.
| Prueba | Si se cumple | Si no se cumple |
|---|---|---|
| Grado mínimo 2 | Solo permite continuar | No es hamiltoniano |
| Sin vértice de corte | Solo permite continuar | No es hamiltoniano |
| Dirac | Es hamiltoniano | No concluye |
| Ore | Es hamiltoniano | No concluye |
Se fija un origen y se construye un camino. Cada candidato debe ser vecino del último vértice y no haber sido visitado. Si se incluyen todos, se comprueba el regreso al origen.
function buscar(posicion) {
if (posicion === vertices.length) {
return sonAdyacentes(camino[posicion - 1], camino[0]);
}
for (const candidato of vecinos[camino[posicion - 1]]) {
if (!visitado.has(candidato)) {
camino[posicion] = candidato;
visitado.add(candidato);
if (buscar(posicion + 1)) return true;
visitado.delete(candidato);
}
}
return false;
}function cicloHamiltoniano(grafo) {
const vertices = Object.keys(grafo);
if (vertices.length === 0) return null;
const camino = [vertices[0]];
const visitado = new Set(camino);
function dfs() {
if (camino.length === vertices.length) {
return grafo[camino.at(-1)].includes(camino[0]);
}
for (const vecino of grafo[camino.at(-1)]) {
if (!visitado.has(vecino)) {
visitado.add(vecino); camino.push(vecino);
if (dfs()) return true;
camino.pop(); visitado.delete(vecino);
}
}
return false;
}
return dfs() ? [...camino, camino[0]] : null;
}El backtracking mejora si abandona estados que aíslan vértices no visitados, crean un extremo sin salida o dividen el resto del grafo en componentes incompatibles.
Ordenar primero los candidatos más restrictivos puede descubrir antes los fracasos y reducir notablemente el árbol de búsqueda.
Puede almacenarse si existe un camino que comienza en un origen, visita exactamente el subconjunto S y termina en v.
El método usa O(n²2ⁿ) tiempo y O(n2ⁿ) espacio: sigue siendo exponencial, pero evita repetir subproblemas.
Decidir si un grafo contiene un ciclo hamiltoniano es NP-completo. Una búsqueda directa puede explorar O(n!) órdenes de vértices.
Verificar un ciclo propuesto cuesta solo O(n), pero encontrarlo o demostrar que no existe puede requerir tiempo exponencial.
| Concepto | Debe recorrer | Repeticiones | Criterio |
|---|---|---|---|
| Hamiltoniano | Todos los vértices | No repite vértices | No existe caracterización simple conocida |
| Euleriano | Todas las aristas | Puede repetir vértices | Se decide mediante grados y conectividad |
La hamiltonicidad exige una estructura global que no puede deducirse únicamente mirando grados locales. Las condiciones teóricas resuelven algunos casos y la búsqueda exacta cubre los restantes a costa de complejidad exponencial.
En el próximo tema estudiaremos grafos eulerianos, donde el objetivo cambia de visitar vértices a recorrer todas las aristas.