Estructura

Barinas, Enero del 2013
GRAFOS EULERIANOS Y HAMILTONIANOS

* Grafos eulerianos:
Dícese de los grafos no orientados formados por un ciclo euleriano; es decir, aquellos que pueden recorrerse completamente desde un vértice y regresar al punto de origen sin pasar dos veces por la misma arista.
El nombre de este tipo de grafos proviene del matemático Leonard Euler quien abordó por primeravez el asunto de cómo debían caracterizarse los grafos para poder recorrerse de la manera deseada tras desestimar el problema de los puentes de Königsberg.
El problema análogo de recorrido pero que en lugar de limitar el doble paso por las aristas lo hace impidiendo que se transite dos veces por los vértices ha dado lugar a la existencia de los grafos hamiltonianos.

Antecedentes
Elproblema de los 7 puentes de la ciudad de Königsberg (hoy Kaliningrado) constituyó durante mucho tiempo un rompecabezas para personas comunes y entendidas en matemáticas y aunque existía la sospecha de que fuese insoluble tampoco había una forma de decir definitivamente que no tuviera solución.
No fue hasta que Euler caracterizó el problema y la forma que habían de tener los grafos que pudieransatisfacerlo en 1736, que finalmente quedó probado que el famoso problema carecía de solución. De esta forma, también comenzaba a existir la teoría de grafos. Con el análisis de los grafos eulerianos se formularon además las condiciones para saber si el camino euleriano era abierto o cerrado (cíclico), llegando a una versión completa de la caracterización de los grafos en 1873 de la mano de CarlHierholzer.

Teorema general
Sea un grafo G=<V,A> no dirigido y conexo, entonces las expresiones siguientes equivalen:
* G es grafo euleriano.
* Todos sus vertices tienen grado par no nulo.

Propiedades
* Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
* Un grafo no dirigido es euleriano si es conexo y si se puededescomponer en uno con los vértices disjuntos.
* Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
* Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
* Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y al menos dos vértices en elgrafo tienen grado impar.

* Grafos 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 adyacente al primero, el camino es un ciclo hamiltoniano.
El problema de encontrar un ciclo (o camino)hamiltoniano en un grafo arbitrario se sabe que es NP-completo.
Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, pero esta solución no se generaliza a todos losgrafos.
Un camino hamiltoniano es un camino que pasa por cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano si es un ciclo que pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.

Teorema de Bondy-Chvatal

La mejorcaracterización de los grafos hamiltonianos fue dada en 1972 por el teorema de Bondy-Chvátal que generalizaba los resultados anteriormente encontrados por G. A. Dirac. Básicamente dice que un grafo es hamiltoniano si existen suficientes aristas. Primero debemos definir lo que es la cerradura de un grafo.
Dado un grafo G con n vértices, la cerradura (cl (G)) es construida de manera única a partir...