PROBLEMAS DE RECORRIDO DE VÉRTICES
Definiciones:
1. Un camino Hamiltoniano es en grafo G es un camino que atraviesa cada vértice del grafo exactamente una vez.
2. Un cliclo Hamiltoniano en un grafo G es un ciclo que atraviesa cada vértice del grafo exactamente una vez.
3. Un grafo es Hamiltoniano si contiene un ciclo Hamiltoniano.
Reglas básicas para construir caminos o ciclos Hamiltonianos:
Regla 1. Si G no es conexo, no posee ciclos Hamiltonianos.
Regla 2. Si G es un grafo con n vértices, entonces un camino Hamiltoniano debe tener exactamente n-1 aristas, y un ciclo Hamiltoniano, 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 y como mucho dos.
Regla 4. Si G es Hamiltoniano, entonces el grado de cada vértice del grafo debe ser mayor o igual a 2.
Regla 5. Si un vértice del grafo tiene grado 2, entonces las dos aristas incidente con ese vértice deben aparecer en cualquier ciclo Hamiltoniano de G.
Regla 6. Si un vértice del grafo tiene grado mayor que 2, entonces cuando se intenta construir un ciclo Hamiltoniano, una vez que se pase por ese vértice, las aristas no utilizadas incidentes se dejan de tener en cuenta, se eliminan del ciclo.
Regla 7. Al construir un ciclo o camino Hamiltoniano para G, NO se puede dar el caso de obtener un ciclo para un subgrafo de G a menos que contenga todos los vértices de G.
TEOREMA
Sea G un grafo bipartido con partición {X,Y}.
1. Si G tiene un ciclo Hamiltoniano, entonces el cardinal de X sera igual al cardinal de Y.
2. Si G tiene un camino Hamiltoniano, entonces el cardinal de X y el de Y difieren como mucho por 1.
Lo mismo es cierto para grafos bipartidos completos con más de 2 vértices.
TEOREMA DE DIRAC
Todo grafo simple con n vértices, siendo n mayor o igual a 3, y en el que cada vértice tiene grado de por lo menos la mitad de n (n/2), tiene un ciclo Hamiltoniano.
COROLARIO
Si G es un grafo completo simple con un número de vértices igual o mayor que 3, entonces tiene un ciclo Hamiltoniano y, por lo tanto, es un grafo Hamiltoniano.