Teoría de grafos · Definición

Ciclo euleriano

matemáticas discretasgrafos

Antes de empezar necesitas conocer

Resuelve el problema de recorrer todas las calles, o puentes, de una red sin repetir ninguna; fue el origen de la teoría de grafos.

Definición

Un ciclo euleriano de un grafo \(G=(V,E)\) es un ciclo que recorre cada arista de \(G\) exactamente una vez.

\[G\text{ conexo y }\deg(v)\text{ par }\forall v\in V\iff\text{hay ciclo euleriano}\]

Euler resolvió en 1736 el problema de los puentes de Königsberg: un grafo conexo tiene un ciclo euleriano si y solo si todos sus vértices tienen grado par. La razón es local: cada vez que el recorrido llega a un vértice debe salir por otra arista, así que las aristas de cada vértice se emparejan. El recíproco se demuestra por inducción, extrayendo ciclos hasta agotar las aristas.

Si hay exactamente dos vértices de grado impar, no existe un ciclo, pero sí un camino euleriano abierto que empieza en uno de ellos y termina en el otro. Con más de dos vértices impares no hay ni siquiera eso. El grafo de Königsberg tiene cuatro vértices de grado impar, de modo que no admite ningún recorrido que cruce cada puente una sola vez.

Ejemplo guía: \(K_5\) es conexo y todos sus vértices tienen grado 4, así que recorre sus 10 aristas en un ciclo; \(K_4\) tiene grados 3 y no lo permite. Un error típico es confundirlo con el ciclo hamiltoniano, que visita vértices, no aristas: el euleriano puede pasar muchas veces por un mismo vértice. El algoritmo de Hierholzer construye el ciclo en tiempo lineal.

Para pensar

¿Qué condición sobre los grados caracteriza a un grafo conexo con un camino euleriano abierto?

Que tenga exactamente dos vértices de grado impar; el camino empieza en uno y termina en el otro.

Ejercicios 10

  1. ¿Cuál de estos grafos tiene un ciclo euleriano?
  2. Un grafo conexo tiene vértices de grados \(2,4,4,6\). ¿Tiene ciclo euleriano?
  3. \(K_7\) tiene un ciclo euleriano. ¿Cuántas aristas recorre?
  4. ¿Cuál de estos grafos bipartitos completos tiene un ciclo euleriano?
  5. Un grafo conexo tiene exactamente dos vértices de grado impar. ¿Qué es cierto?
  6. Un grafo conexo tiene seis vértices de grados \(2,2,2,2,4,x\). ¿Qué valor de \(x\) permite un ciclo euleriano?
  7. Si un grafo tiene un ciclo euleriano, ¿cuál afirmación es siempre cierta?
  8. El grafo de los puentes de Königsberg tiene vértices de grados \(3,3,3,5\). ¿Por qué no existe un ciclo euleriano?
  9. A \(K_5\) se le quitan las 4 aristas de un ciclo \(1\text{-}2\text{-}3\text{-}4\text{-}1\). ¿Qué grafo queda?
  10. Dos grafos conexos \(G\) y \(H\) con el mismo conjunto de vértices tienen ciclo euleriano y no comparten aristas. ¿Qué pasa con su unión?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.5
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.5