Grafos Hamiltonianos

GRAFOS HAMILTONIANOS

Tabla de Contenido
Introducción 3
Marco Teórico 4
Teoría de Grafos 4
Grafos Hamiltonianos 5
Teorema 5
Como podemos construir un camino y un ciclo hamiltoniano 6
Ejemplos 6
Conclusión 7
Anexos 8
1. LEONHARD PAUL EULER 8
2. PROBLEMA DE LOS PUENTES DE KÖNIGSBERG. 9
3. SIR  WILLIAM ROWAN HAMILTON 9
Referencias 10

Introducción

La matemáticacomo ciencia de los números y de las figuras,
se a divido primordialmente en el “campo de los números y sus infinitas combinaciones” y por el
“campo de las representaciones de las figuras,
ya sea en el plano o bien el espacio”
(Cantor)

Las matemáticas discretas son un área de las matemáticas que se encarga del estudio de estructuras que soncontables separadamente del conjunto donde se encuentren, por ejemplo los grafos, los números enteros, sentencias lógicas, relaciones y un sinfín de subtemas.

Nos basaremos en las graficas de estos conjuntos, para así entender de una forma mas precisa los conocimientos que nos dejaron los grandes matemáticos de la historia, y comprender la relación con la ciencia de la computación.

Dar unaimagen grafica a estos conjuntos se denomina “Teoría De Grafos” o “Teoría De Las Graficas”, Leonhard Euler [ 1 ] matemático suizo es el gran padre de esta teoría, que se basó en su artículo Problema de los puentes de Königsberg [ 2 ].

Después de que Leonhard Euler elaborara el análisis y solución del Problema de los puentes de Königsberg, otros matemáticos ilustres de esa época hicieron susaportes como William Rowan Hamilton con su Grafo Hamiltoniano que estudiares a continuación.

Marco Teórico
Teoría de Grafos

La Teoría de Grafos o de las Graficas estudia las propiedades de los grafos, los grafos es un diagrama conformado por un conjunto, no vacio, de vértices y un conjunto de aristas.

Los vértices o nodos son una de las partes fundamentales para crear un grafo, estarepresentado por un círculo o punto ●, se nombran por medio de letras o números.

Las aristas o lados son el conjunto de líneas o caminos que se utilizan para trazar una trayectoria de un nodo a otro nodo, estas se representan por una línea ─ en el grafo no dirigido y con una flecha → en el grafo dirigido, se nombran por letras, números o combinación de ambos.

Los caminos son denominados como latrayectoria que se traza para llegar a un nodo.

Los circuitos o ciclos son aquellos donde su trayectoria inicia y termina en el mismo punto sin importa el camino que haga, la diferencia en el nombre esta en el tipo de grafo que sea por ejemplo en los grafos dirigidos se llama circuito y en los grafos no dirigidos se llama ciclos.

Grafos Hamiltonianos

Los grafos Hamiltonianos fue unaporte de William Rowan Hamilton 9 [ 3 ], físico y astrónomo irlandés, quien propone el siguiente problema
“El camino debe de ser una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez, si solo así será un Grafo Hamiltoniano”.
Con este enunciado Hamilton dice que el un camino que se debe trazar para que un grafo sea denominado Hamiltoniano tiene que recorrertodos los nodos que tiene sin pasar dos veces por un mismo vértice, sin tomar en cuenta de donde partió.
Un ejemplo es el juego que realiza que consistía en colocar el nombre de 12 ciudades, donde se salía de cualquiera de ellas, y visitar cada una de las ciudades solo una vez y regresar al mismo punto de salida.
Ejemplo:

Después de todo esto llegamos a la conclusión de para que un grafo seaHamiltoniano tiene que tener un ciclo o circuito hamiltoniano.
Teorema

(1) Si G tiene un ciclo Hamiltoniano, entonces X = Y.

(2) Si G tiene un camino Hamiltoniano, entonces X y Y difieren a lo sumo en 1.

Como podemos construir un camino y un ciclo hamiltoniano

Regla 1. Si G no es conexo, no posee ciclos Hamiltonianos. Un grafo es conexo si y solo si el numero de componentes...