Un camino Hamiltoniano en un grafo G es un camino que atraviesa cada vértice del grafo exactamente una vez.
Un ciclo Hamiltoniano en un grafo G es un ciclo que atraviesa cada vértice del grafo exactamente una vez.
Un grafo Hamiltoniano es aquiel grafo G que contiene un ciclo Hamiltoniano.
REGLAS PARA CONSTRUIR
CAMINOS Y CICLOS HAMILTONIANOS
Regla 1. Si G no es conexo, no posee ciclos Hamiltonianos
Regla 2. Si G es un grafo con n vértices
– Un camino debe tener n-1 aristas
– Un ciclo debe tener n aristas
Regla 3. Si v es un vértice del grafo, entonces un camino Hamiltoniano debe tener al menos una arista incidente con v como mucho dos.
Regla 4. Si G es Hamiltoniano, entoncees dG(v) ≥ 2.
Regla 5. Si v tiene grado 2, las dos aristas incidentes a v aparecerán en culquier ciclo Hamiltoniano.
Regla 6. Si v tiene grado > 2 cuando se intenta construir un ciclo Hamiltoniano, una vez que pase por v, las aristas no utilizadas incidentes, no se tienen en cuenta.
Regla 7. Al construir un ciclo o camino hamiltoniano para G no se puede obtener un subgrafo sin que contenga todos los vértices.
TEOREMAS
Sea G un grafo bipartido con partición {X,Y}.
Teorema 1. Si G tiene un ciclo Hamiltoniano, entonces card(X) = card(Y).
Teorena 2. Si G tiene un camino Hamiltoniano entonces card(X) y card(Y) difieren a lo sumo en 1.
Teorena de Dirac. Todo grafo simple con n vértices, n ≥ 3, en el que todo vértice tiene grado por lo menos n/2, tiene un ciclo Hamiltoniano.
Colorario. Si G es un grafo completo simple con n vértices, n ≥ 3, entonces G tiene un ciclo Hamiltoniano.