Recibido: miércoles, 10 mayo 2006

---

---

¿Qué pasaría si... (*)

 

 

partiendo de la capital de la provincia donde vives y regresando al mismo sitio, imaginaras que visitas todas las capitales de provincia de España “a vuelo de pájaro”, sin repetir ninguna y cubriendo la menor distancia total posible? ¿Podrías encontrar un itinerario? ¿Cómo lo harías?

 

[La solución, en el próximo número]

 

 

Solución al problema anterior

 

...intentáramos trazar el dibujo de la Figura 1:

 

Figura 1.

 

sin levantar el lápiz del papel y sin repetir ninguna línea? ¿Podríamos hacerlo?

 

 

Respuesta: No, no podríamos. ¿Me preguntas por qué? Pues vamos a ver. Llamemos A, B, C y D, respectivamente, a cada uno de los puntos unidos a varias de las líneas, como muestra la Figura 2.

 

 

Figura 2.

Todos esos puntos están conectados con un número impar de líneas, tres para A, C y D, y cinco para B. Imaginemos que estamos dibujando la figura y que hemos llegado al punto D, digamos. La primera vez que esto pase podremos salir de D usando una línea diferente a la de llegada, pero la segunda vez no podremos, así que mejor que hayamos completado el dibujo para entonces. Esto quiere decir que cada punto unido a un número impar de líneas tiene que ser el comienzo o el fin de nuestro dibujo. O sea que sólo puede haber dos puntos así. Los demás puntos tienen que estar unidos a un número par de líneas, porque cada vez que visitamos uno de esos puntos necesitamos dos líneas, una para llegar y otra para salir. Es decir, que si suponemos que empezamos y terminamos en puntos distintos, no es posible trazar la figura dada sin levantar el lápiz del papel y sin repetir ninguna línea.

 

Quizá te estés preguntando que pasaría si quisiéramos empezar y terminar el dibujo en el mismo punto. Razonando como en el caso anterior, vemos que ahora todos los puntos deberían de estar unidos a un número par de líneas, porque el punto donde comenzamos y el punto donde terminamos coinciden, por lo cual necesitamos una línea para salir, dos cada vez que visitamos ese punto y otra para regresar. Es decir, que, sea como sea, no es posible trazar el diseño propuesto.

 

Este criterio tan simple que hemos deducido basándonos en la paridad de los puntos se debe al matemático Leonardo Euler, nacido en Basilea en 1707 y muerto en San Petersburgo en 1783. Si te preguntas que cómo llegó Euler al tema de los dibujos sin levantar el lápiz, aquí va la historia, que tiene lugar en la actual ciudad rusa de Kaliningrado, situada a orillas del mar Báltico a unos 50 kilómetros de la frontera polaca.

 

En los años 1730 esta ciudad se llamaba Könisgberg y pertenecía a Prusia. Dos islas en el río Pregel, en Königsberg, se unían entre ellas y con la tierra firme mediante siete puentes, como muestra la Figura 3.

 

Figura 3.

 

Parece que entre las gentes de Königsberg corría el siguiente acertijo: ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez? Euler supo de este acertijo y para resolverlo indicó con cuatro puntos las cuatro partes de tierra firme y las unió con siete líneas simbolizando los puentes. Su dibujo podría haber sido el siguiente:

 

Figura 4

 

Está claro que las líneas rojas en la Figura 4 forman el mismo tipo de diseño que aparece en la Figura 1. Euler observó que el resolver el acertijo de los siete puentes de Königsberg se reduce a nuestra pregunta del principio: ¿Es posible dibujar la figura sin levantar el lápiz del papel y sin repetir ninguna línea? El razonamiento que Euler usó para contestar negativamente a esta pregunta es precisamente lo que hemos discutido al comienzo.

 

Euler no sólo resolvió el acertijo, sino que al hacerlo creó toda una nueva rama de la geometría, llamada mucho más tarde Topología, en la cual el tamaño, y hasta cierto punto la forma de un objeto, pasa a un segundo plano.

 

Quizá lo más extraordinario de estos dibujos y acertijos es que tienen en realidad mucho que ver con un montón de situaciones prácticas muy importantes, entre ellas el encontrar rutas eficientes para el reparto de la correspondencia, o para leer los medidores del gas o de la electricidad, o para recoger la basura. Rutas eficientes se traducen en emplear menos tiempo y en definitiva en procesos más económicos. Este es el tema de la ciencia llamada Investigación Operativa.

 

Por ejemplo, imaginémonos que un cartero es responsable de llevar la correspondencia a todas las casas en ambas aceras de las calles que se muestran en la Figura 5.

 

¿Hay una ruta que le permita al cartero repartir la correspondencia caminando sólo una vez por cada acera?

 

Para responder a esta pregunta representemos cada cruce de calles con un punto y cada acera con una línea. El dibujo que nos quedará se verá como el de la Figura 6.

 

Figura 5.

Figura 6.

 

Y la pregunta que tendremos que responder es si podemos hacer este dibujo sin repetir ninguna línea y sin levantar el lápiz del papel. Basándonos en el criterio de Euler, podemos decir que sí, que hay una manera de hacer eso, empezando y terminando en el mismo punto, puesto que cada punto está unido a un número par de líneas. Volviendo a la situación del cartero, eso se traduce en decir que el cartero puede repartir la correspondencia caminando sólo una vez por cada acera.

 

En la terminología corriente, un diagrama como los de las Figuras 1 y 6, se llama un grafo o una red, y consta de puntos, o vértices y de líneas, o aristas, conectando los vértices. Si se pueden recorrer todas las aristas exactamente una vez regresando al mismo vértice del que se partió, se dice que el gráfico tiene un circuito de Euler. Cuando se puede empezar y terminar en vértices distintos, se dice que el gráfico tiene un camino de Euler.

 

Es bueno observar que el criterio de Euler nos dice si hay caminos o circuitos, pero realmente no nos muestra cómo encontrar uno. El encontrarlo puede ser un problema difícil si la red es muy complicada. Aquí las computadoras juegan un papel esencial.

 

¿Qué pasa con el cartero si el vecindario es tal que no puede haber circuitos o caminos de Euler? Entonces, como en muchas otras ocasiones, nos tendremos que conformar con algo menos eficiente, que involucrará el caminar más de una vez por algunas aceras. Trasladado al grafo correspondiente, esto quiere decir que tendremos que agregar una o más aristas en lugares convenientes. Esto se llama eulerizar el grafo y entonces el problema, también difícil, es saber cuál es el mínimo número de aristas que hay que agregar. Este es un problema fundamental en Investigación Operativa. Fue llamado el Problema del Cartero Chino por el matemático J. Edmonds, en un artículo publicado en 1973, quizá porque quien lo formuló en un artículo aparecido en 1962 fue un matemático chino, M.K. Kwan.

 

Más allá de las matemáticas y las computadoras, el factor humano juega un papel decisivo en la solución de problemas como los que hemos mencionado. Nuestra intuición y nuestro sentido común son herramientas importantes cuando se trabaja con modelos matemáticos que nunca son capaces de capturar por completo toda la complejidad de un problema.

 

 

---

---