Ciclo hamiltoniano en un gráfico en menos de 128 palabras

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.

Fuente del ciclo hamiltoniano wikipedia

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada.