Ciclo euleriano
|
Ciclo euleriano. Un ciclo o circuito euleriano en la Teoría de Grafos es aquel camino que recorre todas las aristas de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Es aquel ciclo que contiene todas las aristas de un grafo solamente una vez.
Definicion
Ciclo o circuito euleriano: Sea G un grafo sin vértices aislados. Un circuito que contiene todas las aristas de G recibe el nombre de circuito euleriano. Es una trayectoria que empieza y termina en el mismo vérticey recorre cada arista exactamente una vez.
Historia
Leonhard Euler en 1736 plantea y resuelve la teoría de los ciclos eulerianos en el problema conocido como el Problema de los Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.