Caminos

‘’‘Un ciclo es un camino, es decir una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices. Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).

(Para mas temas) meg_edy@hotmail.com

Caminos hamiltonianos

	Un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano
	Un grafo G se dice hamiltoniano si tiene un ciclo hamiltoniano.

	Nota.- A diferencia de los grafos eulerianos, no hay una caracterización de cuando un grafo tiene un ciclo o un camino hamiltoniano

	Teorema.- Si un grafo es conexo con |V|3 y para cada par de vértices la suma de sus grados es mayor o igual que el número de vértices entonces es hamiltoniano.


	Problema del vendedor ambulante

	En un grafo G con pesos se pretende encontrar un ciclo que pase por todos los vértices de forma que la suma de los pesos de las aristas escogidas para formar el ciclo sea lo menor posible.

delgado mendivil,hiegura frayre,villaseñor hernadnez