K?nigsberg, Euler y dibujos en un solo trazo

Con relativa frecuencia, podemos encontrar acertijos que nos proponen decidir si en cierta composici¨®n de l¨ªneas y puntos podemos recorrer, comenzando por uno de esos puntos, todas las l¨ªneas, pasando exactamente una vez por cada una de ellas. Vamos, que si podemos replicar el dibujo con un solo trazo sin repetir l¨ªneas. Dos ejemplos t¨ªpicos son el sobre cerrado y el sobre abierto:

?Se puede siempre? Y, en caso de que la respuesta sea negativa, ?cu¨¢ndo se puede? Hoy hablaremos sobre este tema, muy relacionado con los comienzos de una de las ramas de las matem¨¢ticas m¨¢s importantes y con m¨¢s aplicaciones de nuestro tiempo: la teor¨ªa de grafos.

La ciudad rusa de K?nigsberg (actual Kaliningrado) fue testigo de los primeros pasos importantes que se dieron en relaci¨®n con los grafos. Y sus siete puentes fueron los culpables. La pregunta era si se pod¨ªan recorrer todos estos siete puentes pasando por cada uno de ellos exactamente una vez, siendo la situaci¨®n de los mismos como se muestra en la siguiente imagen. Ten¨¦is los puentes rodeados con c¨ªrculos azules y las cuatro regiones etiquetadas con las letras A, B, C y D:

Fue Leonhard Euler quien dio respuesta a esta pregunta. Asign¨® a cada porci¨®n de tierra un punto, y a cada puente una l¨ªnea, convirtiendo el problema de los puentes en un problema de teor¨ªa de grafos.

El grafo que obtuvo es el siguiente:

Como hay que comenzar en un v¨¦rtice y terminar en otro (podr¨ªa ser el mismo con el que se empieza), Euler observ¨® que en los v¨¦rtices intermedios deben concurrir un n¨²mero par de aristas, para que por cada una con la que llegamos a dicho v¨¦rtice haya otra por la que salgamos de ¨¦l. Como en el grafo de los puentes de K?nigsberg tenemos en todos los v¨¦rtices un n¨²mero impar de aristas, la conclusi¨®n es que no se puede encontrar un camino que recorra todos los puentes pasando por cada uno de ellos exactamente una vez.

La cuesti¨®n ahora es determinar qu¨¦ condiciones tiene que cumplir un grafo para que s¨ª se pueda encontrar un camino como el que estamos buscando. Aunque con lo dicho hasta ahora ya se puede intuir, vamos a explicarlo a continuaci¨®n.

En todo lo que hemos comentado hasta ahora, estamos tratando con grafos no dirigidos, que son grafos en los que podemos recorrer cada arista en los dos sentidos (en los grafos dirigidos, las aristas se representan con flechas y solamente pueden recorrerse en el sentido que est¨¦ indicado por cada flecha), y con grafos conexos, que son grafos en los que cada v¨¦rtice siempre puede conectarse con cualquier otro mediante un camino de aristas. En este tipo de grafos, el grado de un v¨¦rtice es el n¨²mero de aristas que concurren en ¨¦l. Tras esta definici¨®n, vamos con el teorema que nos dice cu¨¢ndo podemos hacer lo que buscamos:

Teorema:

En un grafo no dirigido y conexo, podemos encontrar un camino que recorra todas las aristas pasando por cada una de ellas exactamente una vez si se da alguna de las siguientes situaciones:

1.- Todos los v¨¦rtices tienen grado par. En este caso, podemos empezar en cualquiera de ellos, y acabaremos en ese mismo v¨¦rtice.

2.- Dos de sus v¨¦rtices tienen grado impar y el resto tiene grado par. Entonces, el camino buscado comenzar¨¢ en uno de los v¨¦rtices de grado impar y terminar¨¢ en el otro.

El primero de ellos se denomina circuito euleriano (porque comienza y termina en el mismo v¨¦rtice), y el segundo camino euleriano.

Con este resultado ya podemos responder a lo que pregunt¨¢bamos al principio del art¨ªculo: no podemos encontrar un camino de este tipo que recorra el sobre cerrado (tiene cuatro v¨¦rtices con grado impar) y s¨ª podemos encontrar dicho camino en el sobre abierto (tiene dos v¨¦rtices con grado impar).

Ahora que tenemos el cu¨¢ndo (sabemos cu¨¢ndo podemos recorrer un grafo de la forma descrita), lo interesante ser¨ªa saber el c¨®mo. Cierto es que en un grafo con pocos v¨¦rtices y pocas aristas no es dif¨ªcil encontrar el camino (o el ciclo) a ojo, pero cuando el n¨²mero de v¨¦rtices y el n¨²mero de aristas crece la cosa se complica. Por ello, vamos a ver un m¨¦todo, atribuido a Carl Hierholzer, para encontrar un circuito euleriano (en grafos cuyos v¨¦rtices tienen todos grado par) que luego usaremos tambi¨¦n para encontrar un camino euleriano en grafos con exactamente dos v¨¦rtices de grado impar.

Veamos c¨®mo encontrar un circuito euleriano. Como todos los v¨¦rtices deben tener grado par, podemos comenzar por el que queramos (y terminaremos tambi¨¦n en ¨¦l). Tomamos un v¨¦rtice cualquiera, digamos A, como comienzo, y seguimos estos pasos:

1.- Buscamos un camino de aristas (sin repetir ninguna) que comience en A y acabe tambi¨¦n en A. Apuntamos entonces la secuencia de v¨¦rtices que hemos recorrido (que, evidentemente, comenzar¨¢ en A y acabar¨¢ tambi¨¦n en A).

2.- Quitamos las aristas que hemos recorrido y los v¨¦rtices aislados (v¨¦rtices a los que no llega ninguna arista), si es que nos qued¨® alguno.

3.- Si todav¨ªa queda algo del grafo, tomamos un v¨¦rtice por el que ya hayamos pasado y hacemos lo mismo que en el paso 1: buscamos un camino de aristas que comience en ¨¦l y acabe tambi¨¦n en ¨¦l, y apuntamos la secuencia de v¨¦rtices recorridos.

4.- Insertamos esta secuencia en la anterior. Por ejemplo, si la primera era (A,B,C,D,A) y la segunda es (B,J,L,B), nos quedar¨ªa (A,B,J,L,B,C,D,A). Despu¨¦s, quitamos aristas recorridas y v¨¦rtices aislados.

5.- Repetimos los pasos 3 y 4 las veces que sea necesario, y vamos insertando las secuencias de v¨¦rtices obtenidas. El camino que nos queda al final es un camino que pasa por todas las aristas exactamente una vez.

Veamos un ejemplo con un grafo concreto. Vamos a encontrar un circuito euleriano en el grafo que Lewis Carroll le envi¨® por carta a una de sus amigas en 1869 y que Carlo Frabetti nos ense?aba en El sobre m¨¢gico de Lewis Carroll:

Pod¨¦is comprobar que todos sus v¨¦rtices tienen grado par, por lo que podremos encontrar nuestro circuito euleriano. Elegimos un v¨¦rtice para comenzar, por ejemplo el A y aplicamos el paso 1. Como da igual el camino cerrado que elijamos, tomamos el (A,E,F,I,G,B,A). Quitamos las aristas recorridas y los v¨¦rtices aislados, como indica el paso 2. Nos queda el siguiente grafo:

Vamos con el paso 3: tomamos un v¨¦rtice del grafo resultante por el que ya hayamos pasado y buscamos un camino cerrado como en el primer paso. Por ejemplo, elegimos el B y recorremos el camino (B,R,Q,M,L,J,H,C,B). Y ahora, como comenta el paso 4, insertamos esta secuencia de v¨¦rtices en la primera. Nos queda la secuencia siguiente:

(A,E,F,I,G,B,R,Q,M,L,J,H,C,B,A)

Quitamos aristas ya recorridas y los v¨¦rtices que quedan aislados y nos queda el siguiente grafo:

(A,E,F,I,G,B,R,Q,C,D,J,I,K,L,N,O,P,Q,M,L,J,H,C,B,A)

Posiblemente, sea interesante que os dibuj¨¦is el grafo en un papel y sig¨¢is el camino obtenido tachando las aristas que vay¨¢is recorriendo, para comprobar que en realidad se trata de un circuito euleriano. Tambi¨¦n pod¨¦is buscar otros posibles circuitos eulerianos, ya que, evidentemente, ¨¦sta no es la ¨²nica opci¨®n posible.

Veamos ahora c¨®mo encontrar un camino euleriano en un grafo que tenga exactamente dos v¨¦rtices de grado impar. Si llamamos A y B a estos dos v¨¦rtices, la clave es dibujar una nueva arista que una A con B (aunque ya hubiera una). Con ello conseguimos un grafo cuyos v¨¦rtices tienen todos grado par, y podemos aplicar el proceso descrito anteriormente. Solamente hay que tener cuidado con un par de cosas. La primera es que el v¨¦rtice elegido para comenzar sea uno de los dos que tienen grado impar al principio, el A o el B. Y la segunda es que, durante el proceso, vayamos eligiendo caminos que no contengan a la arista que hemos a?adido. Lo m¨¢s conveniente es que esa arista quede para el final, que sea la ¨²ltima arista recorrida. As¨ª, cuando tengamos la secuencia de v¨¦rtices del circuito euleriano, simplemente tenemos que eliminar el ¨²ltimo v¨¦rtice (que ser¨¢ el v¨¦rtice con el que comenzamos) y ya tenemos nuestro camino euleriano.

Veamos el caso del sobre abierto como ejemplo. Partiendo del grafo inicial, a?adimos la arista que hace que todos los v¨¦rtices sean de grado par y aplicamos el proceso comenzando con el v¨¦rtice A. Al final ten¨¦is el camino euleriano resultante, con las aristas numeradas seg¨²n el orden en el que las hemos recorrido:

Ya ten¨¦is procedimiento para proponer acertijos (con soluci¨®n o sin ella) a los amigos y para resolver (si es que se puede) los que os puedan proponer.