Grafos hamiltonianos

Abstract

RESUMEN: El origen de la teoría de grafos se remonta al trabajo que realizó Euler en 1736, “Solutio problematis ad geometriam situs pertinentis”, donde determinó una condición necesaria para recorrer todas las aristas de un grafo pasando por cada una de ellas una única vez. A mediados del siglo XIX el matemático William Hamilton modificó dicho problema y se preguntó si sería posible recorrer todos los vértices del grafo pasando por ellos una sola vez. Si se tiene tal recorrido y además el punto inicial es igual al final, entonces el grafo es hamiltoniano. Para los grafos hamiltonianos, a diferencia de los eulerianos, no existe una condición necesaria y suficiente que determine dicha propiedad. En este trabajo se enunciaran y demostraran condiciones necesarias y condiciones suficientes para que un grafo sea hamiltoniano.

ABSTRACT: The origin of graph theory goes back to Euler’s work in 1736, “Solutio problema tis ad geometriam situs pertinentis”, where he determined a necessary condition to go through all the edges of a graph passing through each of them a unique time. In the mid-nineteenth century, the mathematician William Hamilton modified this problem and wondered if it would be possible to traverse all the vertices of the graph passing through them only once. If there is such a path and also the initial point is equal to the end point, then the graph is hamiltonian. For hamiltonian graphs, unlike Eulerian graphs, there is no necessary and sufficient condition that determines this property. In this work, necessary conditions and sufficient conditions for a graph to be hamil tonian will be enunciated and demonstrated.