Pasatiempos |
Escrito por Josefina Álvarez | ||||||||
jueves, 11 de mayo de 2006 | ||||||||
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:
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.
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.
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: 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.
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.
![]() (*) Sección a cargo de Josefina Álvarez.
|