CAMINO Y CIRCUITO DE EULER

CAMINO DE EULER

Es aquel camino que recorre todos los vértices pasando por todas las ramas solamente una vez.

Una característica importante de los grafos que tienen camino de Euler es que siempre comienza y termina en vértices que tienen valencia impar. Por otro lado un grafo tiene más de dos vértices con valencia impar, entonces no puede tener un camino de Euler ya que es requisito que tenga dos y solamente dos vértices de valencia par.

CIRCUITO DE EULER

Es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez.

Un grafo tiene un circuito de Euler si y sólo si es conexo y todos sus vértices tienen la misma valencia par.

El siguiente algoritmo de Fleury permite determinar un circuito de Euler:

1.- Verificar que el grafo sea conexo y que todos los vértices tengan valencia par. Si no cumple con estas condiciones entonces el grafo no tiene circuito de Euler y finalizar.

2.- Si cumple con la condición anterior, seleccionar un vértice arbitrario para iniciar el recorrido.

3.- Escoger una arista a partir del vértice actual. Esa arista seleccionada no debe ser “lado puente”, a menos que no exista otra alternativa.

Lado puente es aquella arista que si se elimina, los grafos pierden la propiedad de ser conexos.

4.- Desconectar los vértices del grafo ya están desconectados ya se tiene el circuito de Euler y finalizar. De otra manera continuar con el paso 3.

REFERENCIAS:

Murillo, J. A. (s.f.). Matemáticas para la computación. México: Alfaomega Grupo Editor, S. A. de C. V., México.