Grafo hamiltoniano - Historial de revisiones

Carlos idict: /* Fuentes */

2021-11-30T00:02:51Z

‎Fuentes

Carlos idict en 00:01 30 nov 2021

2021-11-30T00:01:28Z

Ana ciget.hol en 18:13 29 nov 2021

2021-11-29T18:13:00Z

Ana ciget.hol: Página creada con «{{Definición|nombre=Grafo hamiltoniano|imagen=Grafohamilton.png|concepto=Es un grafo que admite un circuito hamiltoniano.}} '''Grafo hamiltoniano'''. Es un grafo que…»

2021-11-29T18:07:50Z

Página creada con «{{Definición|nombre=Grafo hamiltoniano|imagen=Grafohamilton.png|concepto=Es un grafo que admite un circuito hamiltoniano.}} '''Grafo hamiltoniano'''. Es un grafo que…»

Página nueva

{{Definición|nombre=Grafo hamiltoniano|imagen=Grafohamilton.png|concepto=Es un [[grafo]] que admite un circuito 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.
== 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.

==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]].

==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.

==Veáse también.==
* [[Grafo euleriano]].
* [[Teoria de Grafos]].

==Fuentes.==
# Teoría de Grafos. Gustavo Montero. [https://www2.ulpgc.es/hege/almacen/download/25/25317/teoriadegrafos.pdf]. Consultado el [[15 de noviembre]] de [[2021]].
# Grafos bipartitos balanceados hamiltoniano y conjuntos independientes balanceados. Daniel Brito. [http://ve.scielo.org/scielo.php?script=sci_arttext&pid=S1315-01622013000100004]. Consultado el [[15 de noviembre]] de [[2021]].
# Ficha Nº4. Caminos y Ciclos Hamiltonianos. Prof. Fernando Gerfauo. [https://www.fing.edu.uy/tecnoinf/paysandu/cursos/2do/mdl2/material/ficha4.pdf]. Consultado el [[15 de noviembre]] de [[2021]].
<div>
[[Categoría:Álgebra]] [[Categoría:Matematicas]]

← Revisión anterior		Revisión del 00:02 30 nov 2021
Línea 62:		Línea 62:
	*Ficha Nº4. Caminos y Ciclos Hamiltonianos. Prof. Fernando Gerfauo. [https://www.fing.edu.uy/tecnoinf/paysandu/cursos/2do/mdl2/material/ficha4.pdf]. Consultado el [[15 de noviembre]] de [[2021]].		*Ficha Nº4. Caminos y Ciclos Hamiltonianos. Prof. Fernando Gerfauo. [https://www.fing.edu.uy/tecnoinf/paysandu/cursos/2do/mdl2/material/ficha4.pdf]. Consultado el [[15 de noviembre]] de [[2021]].

−	[[Categoría:Álgebra]] [[Categoría:~~Matemática~~]]	+	[[Categoría:Álgebra]] [[Categoría:Matemáticas]]

@@ Línea 1: / Línea 1: @@
-{{Definición|nombre=Grafo hamiltoniano|imagen=Grafohamilton.png|concepto=Es un [[grafo]] que admite un circuito hamiltoniano.}}
+{{Definición
 '''Grafo hamiltoniano'''. Es un grafo que admite un circuito hamiltoniano.
-==Definiciones.==
+==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.
 == Observaciones ==
@@ Línea 18: / Línea 30: @@
 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.
-==Historia.==
+==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
@@ Línea 35: / Línea 46: @@
 grad (v ) + grad (w ) ≥n −1,∀v ,w ∈V , con v 6= w , entonces G posee un camino de Hamilton
-===Propiedades.===
+==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.
-==Veáse también.==
+==Véase también==
 * [[Grafo euleriano]].
 * [[Teoría de grafos]].
-==Fuentes.==
+==Fuentes==
-# Teoría de Grafos. Gustavo Montero. [https://www2.ulpgc.es/hege/almacen/download/25/25317/teoriadegrafos.pdf]. Consultado el [[15 de noviembre]] de [[2021]].
-# Grafos bipartitos balanceados hamiltoniano y conjuntos independientes balanceados. Daniel Brito. [http://ve.scielo.org/scielo.php?script=sci_arttext&pid=S1315-01622013000100004]. Consultado el [[15 de noviembre]] de [[2021]].
+*Teoría de Grafos. Gustavo Montero. [https://www2.ulpgc.es/hege/almacen/download/25/25317/teoriadegrafos.pdf]. Consultado el [[15 de noviembre]] de [[2021]].
-# Ficha Nº4.  Caminos y Ciclos Hamiltonianos. Prof. Fernando Gerfauo. [https://www.fing.edu.uy/tecnoinf/paysandu/cursos/2do/mdl2/material/ficha4.pdf]. Consultado el [[15 de noviembre]] de [[2021]].
+*Grafos bipartitos balanceados hamiltoniano y conjuntos independientes balanceados. Daniel Brito. [http://ve.scielo.org/scielo.php?script=sci_arttext&pid=S1315-01622013000100004]. Consultado el [[15 de noviembre]] de [[2021]].
-<div>
+*Ficha Nº4.  Caminos y Ciclos Hamiltonianos. Prof. Fernando Gerfauo. [https://www.fing.edu.uy/tecnoinf/paysandu/cursos/2do/mdl2/material/ficha4.pdf]. Consultado el [[15 de noviembre]] de [[2021]].
-[[Categoría:Álgebra]] [[Categoría:Matematicas]]