Matemáticas | Caminos de Euler y Hamiltonianos

Prerrequisito: fundamentos de la teoría
de grafos Ciertos problemas de grafos tienen que ver con encontrar un camino entre dos vértices de modo que cada borde se recorra exactamente una vez, o encontrar un camino entre dos vértices mientras se visita cada vértice exactamente una vez. Estos caminos son mejor conocidos como camino de Euler y camino hamiltoniano respectivamente.

El problema del camino de Euler se propuso por primera vez en el siglo XVIII.

Caminos y circuitos de Euler:

Un camino de Euler es un camino que usa cada borde de un gráfico exactamente una vez .
Un circuito de Euler es un circuito que usa cada borde de un gráfico exactamente una vez.
Un camino de Euler comienza y termina en diferentes vértices.
Un circuito de Euler comienza y termina en el mismo vértice.

Representación gráfica del problema del puente de Konigsberg :

Existen criterios simples para determinar si un multigrafo tiene un camino de Euler o un circuito de Euler. Para que cualquier multigrafo tenga un circuito de Euler, todos los grados de los vértices deben ser pares.

Teorema: «Un multigrafo conectado (y un gráfico simple) con al menos dos vértices tiene un circuito de Euler si y solo si cada uno de sus vértices tiene un grado par «.

Prueba de la afirmación anterior es que cada vez que un circuito pasa por un vértice, suma dos veces su grado. Como es un circuito, comienza y termina en el mismo vértice, lo que hace que aporte un grado cuando el circuito comienza y otro cuando termina. De esta forma, todo vértice tiene un grado par.
Dado que el gráfico de Konigsberg tiene vértices de grados impares, no existe un circuito de Euler en el gráfico.

Teorema: «Un multigrafo conectado (y un gráfico simple) tiene una ruta de Euler pero no un circuito de Euler si y solo si tiene exactamente dos vértices de grado impar».

La prueba es una extensión de la prueba dada anteriormente. Dado que un camino puede comenzar y terminar en diferentes vértices, los vértices donde comienza y termina el camino pueden tener grados impares.

Ejemplo: ¿Qué gráficos que se muestran a continuación tienen una ruta de Euler o un circuito de Euler?

Solución: $G_{1}$ tiene dos vértices de grado impar $a$ y $d$ el resto de grado par. Entonces este gráfico tiene un camino de Euler pero no un circuito de Euler. El camino comienza y termina en los vértices de grado impar. El camino es- $a, c, d, a, b, d$ .
$G_{2}$ tiene cuatro vértices todos de grado par, por lo que tiene un circuito de Euler. El circuito es – $a, d, b, a, c, d, a$ .

Caminos y circuitos hamiltonianos:

Ruta hamiltoniana: una ruta simple en un gráfico $G$ que pasa por cada vértice exactamente una vez se llama ruta hamiltoniana.

Circuito hamiltoniano: un circuito simple en un gráfico $G$ que pasa por cada vértice exactamente una vez se llama circuito hamiltoniano.

A diferencia de los caminos y circuitos de Euler, no existe un criterio simple necesario y suficiente para determinar si hay caminos o circuitos hamiltonianos en un gráfico. Pero hay ciertos criterios que descartan la existencia de un circuito hamiltoniano en un gráfico, como si hay un vértice de grado uno en un gráfico, entonces es imposible que tenga un circuito hamiltoniano.
Hay ciertos teoremas que dan condiciones suficientes pero no necesarias para la existencia de grafos hamiltonianos.

Teorema de Dirac: «Si $G$ es un gráfico simple con $n$ vértices de $n\geq 3$ tal manera que el grado de cada vértice $G$ es al menos $n/2$ , entonces $G$ tiene un circuito hamiltoniano».

Teorema de Ore: «Si $G$ es un gráfico simple con $n$ vértices con $n\geq 3$ tal que $deg(u) + deg(v) \geq n$ para cada par de vértices no adyacentes $u$ y $v$ en $G$ , entonces $G$ tiene un circuito hamiltoniano».

Como se mencionó anteriormente, los teoremas anteriores son condiciones suficientes pero no necesarias para la existencia de un circuito hamiltoniano en un gráfico, hay ciertos gráficos que tienen un circuito hamiltoniano pero no siguen las condiciones del teorema mencionado anteriormente. Por ejemplo, el ciclo $C_{5}$ tiene un circuito hamiltoniano pero no sigue los teoremas.

Nota: K _n es circuito hamiltoniano para $n \geq 3$

Hay muchos problemas prácticos que pueden resolverse encontrando el circuito hamiltoniano óptimo. Uno de esos problemas es el problema del viajante de comercio, que pide la ruta más corta a través de un conjunto de ciudades.

Ejemplo 1- ¿El siguiente gráfico tiene un circuito hamiltoniano?

Solución: sí, el gráfico anterior tiene un circuito hamiltoniano. La solucion es –

Hamiltonian Path

Ejemplo 2- ¿El siguiente gráfico tiene un circuito hamiltoniano?

Solución: no, el gráfico anterior no tiene un circuito hamiltoniano ya que hay dos vértices con grado uno en el gráfico.

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2007, Pregunta 23
2. GATE CS 2005, Pregunta 84
3. GATE CS 2008, Pregunta 26

Referencias-

Camino euleriano – Wikipedia
Camino hamiltoniano – Wikipedia
Matemáticas discretas y sus aplicaciones, por Kenneth H Rosen

Este artículo es una contribución de Chirag Manwani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta