Grafo hamiltoniano
| ||||||
Grafo hamiltoniano. Es un grafo que admite un circuito hamiltoniano.
Definiciones
- Circuito Hamiltoniano: Es un camino cerrado que pasa una sola vez por todos y cada uno de los vértices del grafo, es decir, es un ciclo que a su vez es un camino hamiltoniano.
- Camino Hamiltoniano: Es un camino simple (que no repite vértices) que incluye todos los vértices de G.
Historia
William Rowan Hamilton, quien inventó el juego icosiano conocido como el rompecabezas de Hamilton que consiste en encontrar un ciclo hamiltoniano en el gráfico de borde del dodecaedro. Hamilton resolvió este problema utilizando el cálculo icosiano(que es una estructura algebraica basada en raíces de unidad con muchas similitudes con los cuaterniones, inventado por Hamilton). Esta solución no se aplica a gráficos arbitrarios.
Los grafos, caminos y ciclos hamiltonianos llevan su nombre, además de llevar el nombre de Hamilton, los ciclos hamiltonianos en poliedros también fueron analizados un año antes por Thomas Kirkman, quien, dio un ejemplo de poliedro sin ciclos hamiltonianos. Incluso antes, los ciclos y caminos hamiltonianos en el gráfico del caballo del tablero de ajedrez, el recorrido del caballero, habían sido estudiados en el siglo IX en las matemáticas indias por Rudrata , y casi al mismo tiempo en las matemáticas islámicas por al-Adli ar-Rumi.En Europa del siglo XVIII, las giras de los caballeros fueron publicadas por Abraham de Moivre y Leonhard Euler.
Observaciones
- Dado un grafo con un ciclo de Hamilton, si suprimimos una de sus aristas se obtiene un camino de Hamilton.
- Un grafo puede tener un camino de Hamilton y no poseer ningún ciclo de Hamilton.
- Un grafo con vértice de grado uno no posee ningún ciclo de Hamilton, puesto que en estos ciclos cada vértice del grafo es incidente con dos aristas.
- Si un vértice de un grafo tiene grado dos, entonces las dos aristas incidentes en este vértice forman parte de cualquier ciclo de Hamilton que hubiera en el grafo.
- Cuando se está construyendo un ciclo de Hamilton y ́este pasa por un vértice, entonces ignoramos a efecto de su construcción, las restantes aristas incidentes en este vértice que no forman parte del ciclo.
- Un ciclo de Hamilton no puede contener otro ciclo más pequeño dentro de él.
- Un grafo de Hamilton no puede tener vértices de corte o articulación.
- Si G tiene un ciclo de Hamilton, entonces todos los vértices tienen grado mayor o igual que 2.
A pesar de la aparente analogía entre grafos eulerianos y hamiltonianos, hay profundas diferencias en su estudio. La fundamental es que no se conoce ninguna caracterización para los grafos hamiltonianos.
Teorema
- Teorema de Dirac (condición suficiente)
Sea G = (V ,A, δ) un grafo conexo con n ≥3 vértice. Si ∀v ∈V se verifica que grad (v ) ≥n/2 entonces G es hamiltoniano
- Teorema (condición necesaria)
Un grafo hamiltoniano no tiene ningún vértice de corte
- Teorema de Ore (condición suficiente)
Sea G = (V ,A,δ) un grafo sin bucles con |V |= n ≥2. Si se verifica que grad (v ) + grad (w ) ≥n −1,∀v ,w ∈V , con v 6= w , entonces G posee un camino de Hamilton Sea G = (V ,A,δ) un grafo sin bucles con |V |= n ≥2. Si se verifica que grad (v ) + grad (w ) ≥n −1,∀v ,w ∈V , con v 6= w , entonces G posee un camino de Hamilton
Propiedades
- Cualquier ciclo hamiltoniano se puede convertir en una ruta hamiltoniana eliminando uno de sus bordes, pero una ruta hamiltoniana puede extenderse a un ciclo hamiltoniano solo si sus puntos finales son adyacentes.
- Todos los gráficos hamiltonianos están biconectados , pero no es necesario que un gráfico biconectado sea hamiltoniano.
Véase también
Fuentes
- Teoría de Grafos. Gustavo Montero. [1]. Consultado el 15 de noviembre de 2021.
- Grafos bipartitos balanceados hamiltoniano y conjuntos independientes balanceados. Daniel Brito. [2]. Consultado el 15 de noviembre de 2021.
- Ficha Nº4. Caminos y Ciclos Hamiltonianos. Prof. Fernando Gerfauo. [3]. Consultado el 15 de noviembre de 2021.
