Problema del ciclo hamiltoniano

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 =()


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Problema del viajante — Saltar a navegación, búsqueda Si un viajante parte de la ciudad A y las distancias a todas las demás ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades y volver a la ciudad de partida? Contenido …   Wikipedia Español

  • Problema abstracto — Saltar a navegación, búsqueda En ciencia computacional teórica, un problema abstracto o problema computacional es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la… …   Wikipedia Español

  • Ciclo euleriano — Un ciclo euleriano es aquel camino que recorre todas las aristas de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde… …   Wikipedia Español

  • Camino hamiltoniano — Ciclo hamiltoniano. En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es… …   Wikipedia Español

  • NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

  • Ham — Ham, es el nombre de varias localidades de la Unión Europea. Municipalidad de Ham, Bélgica. Ham (Somme) Ham (Reino Unido) Ham (Wiltshire) Le Ham (Mayenne) Le Ham (Manche) En Argentina Ham, en la provincia de Buenos Aires. Por las siglas HAM,… …   Wikipedia Español

  • Algoritmo de Bellman-Ford — El algoritmo de Bellman Ford (algoritmo de Bell End Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un… …   Wikipedia Español

  • Árbol de expansión — Un árbol de expansión (aristas azules gruesas) de un grafo de rejilla. En el campo matemático de la teoría de grafos, un árbol de expansión T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas)… …   Wikipedia Español

  • Algoritmo — Los diagramas de flujo sirven para representar algoritmos de manera gráfica. En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al… …   Wikipedia Español

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”