Ciclo euleriano

Ciclo euleriano
Información sobre la plantilla
CicloEuleriano1.png
Concepto:Sea G un grafo sin vértices aislados. Un circuito que contiene todas las aristas de G recibe el nombre de circuito 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.

Definición

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értice y recorre cada arista exactamente una vez.

CicloEuleriano.png
Recorrido {A,I}{I,H}{H,C}{C,G}{G,F}{F,E}{E,J}{J,I}{I,B}{B,H}{H,G}{G,D}{D,F}{F,J}{J,A}{A,B}{B,C}{C,D}{D,E}{E,A}.

Historia

Leonhard Euler en 1736 plantea y resuelve la teoría de los ciclos eulerianos en 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.

Véase también

Fuentes