Ciclo euleriano

En la teoría de grafos, un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. El problema de encontrar dichos caminos fue discutido por primera vez por Leonhard Euler, en el famoso problema de los puentes de Königsberg.


Ciclos eulerianos

Dibujar un sobre abierto, como el de la imagen, sin levantar el lápiz del papel ni pasar dos veces por el mismo sitio, es posible. En cambio, dibujar el sobre cerrado (prescindiendo del punto 5 y sus líneas adyacentes) es imposible.

En la imagen, es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.

Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.

Other Languages
العربية: دارة أويلرية
čeština: Eulerovský tah
dansk: Euler-tur
English: Eulerian path
français: Graphe eulérien
magyar: Euler-kör
日本語: オイラー路
қазақша: Эйлер графы
한국어: 한붓그리기
norsk bokmål: Eulervei
português: Caminho euleriano
русский: Эйлеров цикл
Simple English: Eulerian path
српски / srpski: Ојлеров пут
українська: Ейлерів ланцюг
Tiếng Việt: Đường đi Euler