Ciclo euleriano

Ciclo euleriano 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.

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

• Grafo
• Grafo euleriano
• Grafo hamiltoniano

Fuentes

• Recorridos eulerianos. Gregorio Hernández Peñalver. Disponible en:Departamento de Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones (DMATIC), sección departamental de la Escuela Técnica Superior de Ingenieros Informáticos (ETSIINF), Universidad Politécnica de Madrid (UPM). Consultado el 29 de noviembre de 2021.
• Introducción a la teoría de grafos, Jesús García Miranda. Disponible en:Universidad de Granada. Consultado el 29 de noviembre de 2021.
• Teoría de grafos. Una introducción histórica-técnica, Víctor Manuel Castaño Meneses. Disponible en:Academia de Ingeniería de México. Consultado el 29 de noviembre de 2021.