Proyecto 5: Ciclo euleriano

El tema que yo elegí se llama ciclo euleriano, Euler se pronuncia "oil-er". A este tema también se le llama circuito euleriano, circuito de euler, tour euleriano o tour euler.

Definición

Un ciclo euleriano es un camino en un grafo G que comienza y termina en el mismo vértice, que incluye cada arista del grafo exactamente una vez y que puede tener vértices repetidos, es decir, un ciclo que incluye todas las aristas de E y que estas no se repitan.

Temas similares

Este tema esta extremada mente relacionado con el camino euleriano que trata sobre encontrar un camino en un grafo G de manera que se incluyan todas sus aristas sin repetirse, y también es comparado mas aun con el ciclo hamiltoniano que trata sobre un ciclo que incluye todos los vértices una sola vez.

Orígenes

Este acertijo surge con el problema de los 7 puentes de Königsberg (ciudad alemana del siglo XVIII situada sobre el río Praga) que fue resuelto por el matemático suizo Leonhard Euler en 1736 y publicado en un articulo titulado: Solutio problematis ad geometriam situs pertinentis (Solución de un problema relacionado con la geometría de posición).

El problema trata sobre atravesar los 7 puentes de la ciudad que conectaban 2 islas, una sola vez cada uno.

 Königsberg

http://staff.jccc.net/swilson/misc/images/koenigsberg_1910.jpg   

Los puentes son los caminos blancos sobre el río gris.

Euler resolvio el problema imaginando el territorio de las islas y el rio con un grafo conexo.

Para entender el problema de los 7 puentes de Königsberg, hay que imaginar que las aristas son los puentes y que los vértices son islas o territorios en la siguiente imagen.

Ahora hay que tratar de encontrar un ciclo que incluya todas las aristas de manera que en el trayecto no se repitan aristas.

...


Euler descubrió que esto es imposible de hacer en este grafo!, mas no fue el quien dio la demostración matemática sino que fue Carl Hierholzer hasta 1873.

Lo que Leonhard Euler dijo fue (en nuestros términos) que un ciclo euleriano en un grafo G existe si y solo si:

1. El grafo era conexo, es decir, hay por lo menos un camino para llegar a cualquier vértice y
2. El grado de todos los vértices de G es un numero par o dicho de otra manera, si no existe un solo vértice de grado impar.

Y como podemos observar, el grado de cada vértice en el grafo es un numero impar, de tal manera que ni siquiera se aproxima poseer un ciclo euleriano ya que si quisiéramos crearlo tendríamos que agregar o eliminar las tres arista del centro del grafo o agregarle 2 aristas.

Explicación

Podemos entender el argumento de Euler debido a que en un ciclo euleriano cuando pasamos a través de un vértice tenemos que tener 2 caminos (aristas) o cualquier otro numero par, esto es gra(e) mod 2 = 0, uno para llegar y el otro para partir o viceversa y completar el ciclo, de otro modo nos quedaríamos "atascados" en el mismo vértice o en su defecto jamas podríamos volver, de cualquier modo siempre nos faltaría 1 arista por recorrer para completar el ciclo.

Problema que se debe de resolver

Se puede decir que Euler resolvió el siguiente problema de decisión:
"Existe un trayecto que incluya todas las aristas sin repetirse, partiendo de un vértice v y regresando al mismo vértice v, en un grafo G?".

Sin su algoritmo para determinar este problema de decisión, tendríamos que realizar todos los trayectos posibles para determinar si existe algún ciclo euleriano y esto nos daría una complejidad asintótica O(n!), pero con las simples reglas de Euler obtenemos la complejidad O(n).

Ejemplo de ciclo euleriano

Es interesante observar que no importa cuan grande o complejo sea un grafo, si cumple con las 2 condiciones necesarias anteriores (1 y 2), este posee un ciclo euleriano.

En esta imagen el grafo es conexo además de que el grado de todos los vértices es un numero par.

Algoritmo del problema

Se pueden realizar varios algoritmos dependiendo de lo que se pretende resolver, por ejemplo, uno que resuelva el problema de decision: Existe un ciclo euleriano en un grafo G?, otro que resuelva el problema de decision: Cual es un ciclo euleriano en G?, e incluso un tercero que resuelva el problema de decisión: Cuales son todos los ciclos eulerianos en G? (una variante del anterior).

Ademas de que pueden existir variaciones del ciclo euleriano para resolver problemas de optimizacion como: Encuentra un ciclo euleriano de manera que se recorran ciertos vertices antes que otros, en este caso se podrian ponderar los vertices de acuerdo a la preferencia y optimizando el trayecto a recorrer para obtener el mejor ciclo posible.

Algoritmo de existencia

1. Para cada vértice en el grafo se analizara su grado (ignoramos los vecinos, es trivial).
2. Si alguno tiene un grado impar, se dirá que no existe un ciclo euleriano en el grafo y termina el algoritmo.
3. Si al final de analizar todos los vértices, nunca se dijo que no existía un ciclo euleriano, entonces se dice que si existe un ciclo euleriano.

Algoritmo de busqueda (cual es un ciclo euleriano?)

1. Iniciamos en un vértice al azar o elegido
2. Imaginamos una barrera que comienza a recorrer una arista elegida al azar.
3. La barrera se movera hasta que pueda llegar a un vértice con grado distinto a 1. La barrera almacenara en una pila cada arista del trayecto que recorrió, en orden. 
4. Nota: Esta barrera reservara un camino de llegada al vértice inicial, asegurando el ciclo.
5. La barrera cada vez que se mueve a una nueva posicion, eliminara las aristas recorridas.
6. Por otro lado imaginamos un viajero que recorrerá aristas al azar y que por supuesto no tiene acceso a las aristas eliminadas en el trayecto de la barrera.
7. Cada vez que se mueve el viajero a una arista vecina, guarda la arista recorrida en una lista o arreglo y elimina esa misma arista (para no volver a pasar por allí).
8. Cuando la barrera y el viajero no puedan moverse a ningun vertice vecino, se dice cual es el ciclo euleriano, mostrando primero la lista y luego la pila cuyos elementos aparecen en orden contrario a su introducción.

Nota: Probablemente exista un mejor método para encontrar un ciclo euleriano pero por falta de tiempo solo pensé en este algoritmo.

Complejidad computacional

En el algoritmo de existencia consideramos la instancia n como la cantidad de aristas en el grafo, en el paso 1 se sabe de un ciclo de n veces las operaciones que realizara dentro de este. En el segundo paso (que esta dentro del ciclo) se realiza la operación modular con 3 y la comparación con 0 para determinar si el grado es impar, estas son 2 operaciones (2n hasta ahora). Y en el tercer paso solo espera que termine el ciclo para decir que si existe un ciclo euleriano. En total fue:

$O(2n)$, como las constantes no importan es $O(n)$. El problema de existencia de un ciclo euleriano esta en P porque la complejidad O(n) es polinomial.

Pseudocodigo del algoritmo

Problema de decisión (existe un ciclo euleriano?)

#define num_de_vertices 4000

main()
 int i, grad[num_de_vertices];

 for (i=0;i<=size(grad[]);i++)
   if (grad[i]>1)

     if (grad[i]%3==0)
         puts No existe ciclo euleriano;
         goto end;
   else
     puts No existe ciclo euleriano;
end

Problema de decisión (cual es un ciclo euleriano?)

#define num_vertices 4000
int n, fin=0, turno=1, barrera, viajero, ver, aristas[400][400]; //aristas[][] no es mas que una matriz de adyacencia

main()
  read datafile; //Se encuentra la información del grafo
  ver= rand(0)%3;//Elegimos un vértice al "azar"
  barrera=ver;
  while (!fin)
    switch (turno) //Turnamos las funciones de barrera y viajero
      case 1:
           fbarrera();
           break;
      case 2:
           fviajero();
           break;
  if (detenerbarrera==true&&detenerviajero==true)
    print camino(); //Se terminan de turnar y muestran resultados
    print pila(); //en el orden correcto
end


fbarrera()
  if (gra(barrera)==0)//Si no tiene a donde ir, marca terminado
    detenerbarrera();
    fin=true;
  if (gra(barrera)==1)//Si solo existe un camino posible,se mueve
    pila(barrera); //Almacena el trayecto en que se movió
    barrera=vecino(barrera);//Aquí se mueve
    eliminar(barrera, vecino(barrera));//Se elimina ese camino //para no repetirlo
  turno++;
end 


fviajero()
  if (gra(viajero)==0) //Si no tiene a donde ir, marca terminado
    detenerviajero();
  camino(viajero);//Se alamacena el trayecto
  viajero=vecino(viajero);//Se mueve por una arista permitida
  eliminar(viajero, vecino(viajero));//Para no repetir aristas
  turno--;
end


vecino(int x)
  int i;
  for (i=0;i<=num_vertices;i++)
    if (aristas[x][j]==1)//Si existe una arista que incide en x, //se regresa el vértice al que lleva la arista
      return alpha(j);
end


eliminar(int t, int k)
  aristas[t][k]=null;//Al eliminar se asegura quitar la relacion
  aristas[k][t]=null;//en cualquier direccion
end


Análisis asintótico del algoritmo

Para el primer algoritmo en el peor caso es $O(n)$ porque:

Se asigna una constante (num_de_vertices). +1 paso
El for crea un ciclo donde la complejidad dependerá de los procesos dentro de este.
Se hacen dos comparaciones, grad[i]>1 y grad[i] mod 3==0, y una operación modular, mod 3. +3n pasos

Tenemos entonces O(3n+3) pero como las constantes no importan es O(n) y resulta polinomial.

En este mismo pseudocodigo en el mejor de los casos es O(1) esto es debido a que el primer vértice introducido puede ser de grado impar y por lo tanto eliminar la posibilidad del grafo en poseer un ciclo euleriano, entonces el caso promedio seria $O(\frac{1+(3n+1)}{2})$, como las constantes son triviales, sigue siendo $O(n)$.


Para el segundo algoritmo (de búsqueda) es $O(n)$ porque:

Declaramos una constante, num_vertices, y una variable, turno. +2 pasos
Asignamos un vertice al "azar". +2 pasos
Igualamos barrera y ver. +1 paso
Se intercambiaran el mando del programa fbarrera y fviajero por turnos, esto depende de que tan rapido encuentre el ciclo euleriano.

fbarrera va a comparar si termino de buscar el ciclo (1 operación), compara el grado del vértice actual (1 procedimiento si se almacena su grado). +2 pasos

Aquí viene lo interesante, si el grado de vértice es 1, la barrera puede avanzar y realizara las operaciones siguientes:

• Almacena su trayecto en la pila (1 operación), se cambia de posición (1 operación) a un nodo vecino que para encontrarlo se hace en aproximadamente n pasos dependiendo del grado del vértice actual (n operaciones aproximadamente), y elimina la arista que recorrió (2 operaciones). n+4 pasos
• Incrementa el turno. +1 paso

fviajero almacena su trayecto en un arreglo o lista, se mueve (1 operación) a un nodo vecino que para encontrarlo se hace en aproximadamente n pasos dependiendo el grado de vértice actual y se elimina la arista que recorrió (2 operaciones). n+3 pasos


El resultado es $O((t/2)(2n+9))$, donde t es la cantidad de veces que se turnaron.

Nota: En realidad la complejidad asintotica es menor que lo anterior pero no me meteré en detalles numéricos.

Al final las constantes se ignoran y nos quedamos con $O(n)$. El problema esta en P, tiempo polinomial.

Estructuras de datos utilizadas

Utilice arreglos unidimensionales en el primer pseudocodigo y arreglos unidimensionales, pilas y listas en el segundo.

Aplicaciones

Una aplicación del ciclo euleriano puede ser en la optimizacion de recorridos en mapas, por ejemplo si nos preguntaran si existe un camino para un viaje de turistas de manera que estos no recorran cualquiera de los caminos mas de una vez o en la versión extendida, cual es el mejor ciclo para los turistas recorriendo ciertos lugares antes que otros y sin pasar por los mismos caminos mas de una vez?.

También se me acaba de ocurrir que se puede aplicar en la determinación de flexibilidad en problemas de decisión en grandes instituciones o empresas, por ejemplo si se crea un modelo gráfico que simulara las opciones por las que puede optar una empresa con aristas y los estados finales al llevar a cabo lo optado con vértices, se podría conocer entonces el grado de flexibilidad en decisiones de cada estado dependiendo si existe un ciclo euleriano que permita volver al estado inicial por opciones distintas (aristas distintas), esto se vuelve mas real si permitimos la eliminación de opciones con el tiempo, es decir, eliminar aristas cada cierto tiempo, sea al azar o no.

Curiosidades

• Los 7 puentes de Königsberg fueron bombardeados y destruidos por los aliados en 1944 y solo 5 se reconstruyeron.
• La ciudad Königsberg fue renombrada Kalingraado y ahora es parte de Rusia.
• Ahora es posible visitar los puentes con un camino de Euler pero no con un ciclo de Euler. 
• El problema de los 7 puentes de Königsberg resuelto por L. Euler abrio paso a la topología, rama de las matemáticas que se encarga de estudiar propiedades de los objetos geométricos que tienen que ver con la posicion relativa entre puntos.

Fuentes

1 http://www.itl.nist.gov/div897/sqg/dads/HTML/eulercycle.html
2 http://www.economicexpert.com/a/Eulerian:path.htm
3 http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK4/NODE165.HTM
4 http://books.google.com.mx/books?id=7XUSn0IKQEgC&pg=PA502&lpg=PA502&dq=euler+cycle+applications&source=bl&ots=z6cFQPOS0e&sig=gCQCrKXT4T2ZWCFZLVtJ9k-juhk&hl=es&ei=x-DpS5DhHoyCtgOX3IX-Bw&sa=X&oi=book_result&ct=result&resnum=9&ved=0CFkQ6AEwCA#v=onepage&q&f=false
5 http://theoremoftheweek.wordpress.com/2009/09/29/theorem-8-eulerian-circuits/
6 http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/eulerTour.htm
7 http://mathworld.wolfram.com/EulerianCycle.html
8 http://mathforum.org/isaac/problems/bridges2.html
9 http://www.cs.sunysb.edu/~skiena/combinatorica/animations/euler.html
10 http://mathdl.maa.org/mathDL/46/?pa=content&sa=viewDocument&nodeId=1310&bodyId=1452 (explica cada párrafo de la demostración escrita por L. Euler)
11 http://math.dartmouth.edu/~euler/docs/originals/E053.pdf
12 http://www.iesezequielgonzalez.com/matematicas/grafos.htm
13 http://www.mathematische-basteleien.de/house.html
14 http://books.google.com.mx/books?id=aFDWuZZslUUC&printsec=frontcover&dq=CRC+concise+encyclopedia+of+mathematics&ei=f1z0S9qxLpTukgSM_YS8Bw&cd=1
15 http://books.google.com.mx/books?id=TrXd-gxPhVYC&printsec=frontcover&dq=The+algorithm+design+manual+2&ei=x1z0S9aPFJf4lASauI2uBw&cd=1
16 http://www.ual.es/~jlrodri/Topgen5/introduccion.html 



Comentario de auto evaluación


Creo que realice un buen trabajo con el reporte del blog, inclui todos los requisitos, agregue imagenes, trate de explicar de la manera mas simple posible, por otro lado mostré el algoritmo en que yo pensé para poder resolver el problema, y en algunas partes pedi la participacion del lector, estuvo muy completo e inclui 16 enlaces fuente al final para que los lectores encontraran mas información del tema.

Respecto a la presentacion, los primeros segundos al comenzar estaba algo nervioso pero despues se me fueron conforme pasaba el tiempo y me concentraba en la teoria, la cantidad de diapositivas para mostrar me parecio que se excedia en 2 para el tiempo de esta ocasion pero me las salte y las explique muy rapido, aun asi esas 2 diapositivas solo resaltaban el ejemplo posterior del algoritmo y fue mas facil que el publico entendiera la solución del problema de esta ultima forma. El diseno de la presentacion fue muy simple para mantener todo limpio, claro y conciso.

También hice al publico partícipe de la presentación y comente alguna curiosidad pequeña respecto al problema del ciclo euleriano al terminar. El tiempo que me tarde fue un poquito mas del limite acordado pero valieron la pena esos segundos extra para el publico.