Un ciclo Hamiltoniano es un ciclo que contiene todas las tapas del gráfico.
No hay ningún algoritmo general (es decir, válido para cualquier gráfico) y eficaz (es decir, ningún algoritmo en el número de pasos computacionales o un políno del tamaño del gráfico) para averiguar si hay un ciclo hamiltoniano en un gráfico.
Condición DIRAC: Si para todos los tops u del gráfico G grado (u) ‘n /2 entonces G contiene un ciclo hamiltoniano
Condición ORE: Si para cualquier par usted y v de no vecinos deg(u) ‘deg(v) ‘entonces G contiene un ciclo hamiltorio
Si un gráfico verifica la condición de diraC, entonces verifica la condición orE (la recíproca es false).
