Caminos y Circuitos

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 valencia par.

EI 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 que están unidos por la arista seleccionada.

5) Si todos 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:

Solución

1) Se puede observar que, efectivamente, se trata de un grafo conexo y que todos sus vértices tienen valencia par.

2) Considérese que se inicia el recorrido en el vértice a.

3) Hay que escoger una arista a partir del vértice actual, y esa arista seleccionada no debe ser “lado puente" a menos que no exista otra alternativa.

Se puede seleccionar cualquiera de las dos aristas [a, b) o (a, c), ya que ninguna es puente. Supóngase que en este caso se escoge (a, b), indicada con línea punteada.

4) Regístrese como parte del circuito de Euler dicha arista. Circuito de Euler: {a, b).

5) Desconéctense los vértices que están unidos por la arista seleccionada. Después de eliminar la arista se tiene el siguiente grafo

Como en este caso todavía no están desconectados todos los vértices del grafo, se continúa desde el paso 3, obteniéndose las siguientes posiciones:

Como se ve en el siguiente grafo, del vértice actual b se puede seleccionar cualquiera de las aristas (Jb, c), (b, e) o (b, d), ya que ninguna es puente. Supóngase que se escoge (Jb, c) indicada con línea punteada. Circuito de Euler: (a, b, c).

Eliminando la arista seleccionada se obtiene el siguiente grafo:

Del vértice actual c se puede seleccionar cualquiera de las aristas (c, e) o (c, í), ya que ninguna es puente. Supóngase que se escoge (c, e) como se indica. Circuito de Euler: (a, Jb, c, e).

Eliminando la arista seleccionada se obtiene el siguiente grafo:

Del vértice actual e se puede seleccionar cualquiera de las aristas (e, b) o (e, d), pero no (e, í) porque se trata de un lado puente. Supóngase que se escoge (e, d) como se indica en el siguiente grafo. Circuito de Euler: (a, b, c, e, d).

Eliminando la arista seleccionada se obtiene el siguiente grafo:

En el vértice actual d solamente está el lado puente (d, b), pero como ya no existe otra arista se selecciona ésta. Circuito de Euler: (a, b, c, e, d, b)

Eliminado la arista seleccionada se obtiene el siguiente grafo:

Se continúa así hasta que todos los vértices queden desconectados. 

Finalmente se obtiene el circuito de Euler: (a, b, c, e, d, b, e, f, c, a).

Como se mencionó, con el circuito de Euler se puede dar solución al juego de La Firma del diablo al reconstruir el grafo, partiendo del nodo a, como lo muestra la numeración de las aristas: 

Circuito Hamilton

Se trata de un problema similar al del circuito de Euler, con la diferencia je que en lugar de pasar por todos los lados del grafo solamente una vez, en el circuito de Hamilton se pasa por cada vértice solamente una vez.

El problema surgió en el siglo XIX cuando Hamilton inventó un juego en donde estaban colocados nombres de ciudades en las esquinas de un dodecaedro. El juego consiste en iniciar en cualquier ciudad, viajar a lo largo de las aristas y visitar cada una de las ciudades exactamente una vez y regresar al punto de partida.

Respecto de un grafo se sabe que tiene un circuito de Euler si es conexo 7 todos sus vértices tienen valencia par, sin embargo no hay forma de saber con anticipación si un grafo tiene o no un circuito de Hamilton.

  

EJERCICIO:

 Determina si es posible un circuito de Hamilton en el siguiente grafo:

Solución. El circuito de Hamilton es como se indica en el grafo.

El circuito de Hamilton es {a, b, h, g, e, j, i, f, d, c, a}, la línea punteada.

EJERCICIO:

Considérese el siguiente grafo G:

a)¿Tiene un camino de Euler?
No tiene camino de Euler, por que no se puede pasar por todas la aristas ya que se pasaría por un vértice varias veces.

b)¿Tiene un circuito de Euler?
No hay circuito de Euler por que hay que pasar varias veces por un vértice y el circuito de Euler dice que el ciclo debe recorrer todos los vértices pasando por todos los lados solamente una vez. 

c)¿Tiene un circuito de Hamilton?
No tiene circuito de Hamilton por que pasa por un vértice varias veces

d)Obtener:

• Conjunto de vértices (V): V={1,2,3,4,5,6,7,8,9,10}
• Conjunto de aristas (A): A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,ñ,o,p,q}
• Conjunto de lazos (L): L={3,10} ó L={f,p}
• Conjuntos de lados paralelos (P): P={1,3} ó {q,e}

e)Obtener matriz de adyacencia: n x n = 10 x10 =100