- Problema del ciclo hamiltoniano
-
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 o vertices del grafo. Cuando hablamos de grafos dirigido, 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 vendedor viajero (TSP, del inglés Travelling Salesman Problem).
Tenemos un ejemplo en el cual comenzamos en el punto1 y terminamos en ese mismo punto, el problema es encontrar 3 opcines de poder llegar a ese mismo punto de partida. El problema es el siguientes 1,2,3,1 la formula n-1 eso quiere decir que 4 − 1 = 3 cual es la solucíon. yo solo he econtrado 2 formas de llegar al mismo punto de partido en este caso 1. Tomando en cuenta que no se puede volver a pasar por el mismo lugar.
Si un grafo (G) tiene un vértice de valencia 1, automáticamente sabemos que no puede ser hamiltoniano. También podemos detectar si un grafo es hamiltoniano o no si dicho grafo contiene un número impar de vértices con valencia impar. Por ejemplo, si tiene 10 vértices y 3 de ellos son impares, no admite un ciclo hamiltoniano =()
Categorías: Problemas NP-completos | Teoría de grafos
Wikimedia foundation. 2010.
