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.
EJERCICIO 1
RESPUESTA:
Trayectoria: Longitud:
1.- a, b, c, d, e 21
2.- a, b, d, c, e 28
3.- a, c, b, d, e 24
4.- a, c, d, b, e 26
5.- a, d, b, c, e 27
6.- a, d, c, b, e 22
EJERCICIO 2
Determinar un circuito de Euler en
el siguiente grafo.
PASO 1
R=a, c, b, e, c, f, e, d, b, a
No hay comentarios:
Publicar un comentario