Problema del ciclo hamiltoniano

En teoría de grafos, el Problema del ciclo hamiltoniano y el Problema del camino hamiltoniano tratan de determinar si un ciclo hamiltoniano o un camino hamiltoniano existen en un determinado grafo. Existe una íntima relación entre ambos, de los que se conoce que son NP-completos. Un ciclo hamiltoniano, es a su vez, un ciclo que pasa una y solo una vez por todos los nodos (vértices) del grafo. Cuando hablamos de grafos ponderados, que poseen pesos o costos en sus aristas, se sabe que el ciclo hamiltoniano de menor costo es a su vez también la solución al problema del viajante (TSP, del inglés Travelling Salesman Problem). Si un grafo (G) tiene un vértice de grado 1, automáticamente sabemos que no puede ser hamiltoniano.

Para saber si un grafo es Hamiltoniano o no, debemos aplicar el Teorema de Dirac, que se enuncia:

"Sea G = (V,E) un grafo conexo con |V| ≥ 3. Si deg(v) ≥ |V|/2 para todo v∈V, entonces G es hamiltoniano."

Para facilitar la comprensión del mismo podríamos ver el Teorema de Dirac del modo siguiente: Sea un grafo al que llamaremos G, con sus vértices y aristas, conexo, y con n.º total de vértices mayor o igual a 3. Es decir, el grafo a tratar debe cumplir todas estas características para poder continuar aplicando el Teorema, si no las cumple entonces no será Hamiltoniano. Ahora bien, suponiendo que se cumplen dichas características, proseguimos:

Si el grado de cada uno de los vértices de este grafo es mayor o igual que la mitad del número total de vértices, y esto se cumple para todos y cada uno de los vértices de G, entonces este grafo es Hamiltoniano.

• Datos: Q9062938