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.
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.
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.
|
Sobre la
autora
|

|
Josefina (Lolina) Álvarez es Professor of Mathematics en New Mexico State University (USA).
Especialista en análisis armónico y funcional, se doctoró en Matemáticas por
la Universidad de Buenos Aires (Argentina), bajo la dirección de A.P.
Calderón. Ha ocupado diversos puestos y cargos académicos en la Universidad
de Buenos Aires y en las estadounidenses de Princeton, Chicago, Florida
Atlantic University y New Mexico. Ha sido investigadora del CONICET
(Argentina). Miembro de la Unión Matemática Argentina, Mathematical
Association of America y American Mathematical Society, formó parte del Committee
on Committees de esta última entre 1999 y 2002. Ha dictado numerosas
conferencias en congresos y sesiones especiales e impartido seminarios en
Alemania, Argentina, Bélgica, Brasil, Canadá, Colombia, España, Estados
Unidos, México, Perú, Polonia, Suecia y Venezuela. Ha pertenecido y en varias
ocasiones presidido los comités organizadores de distintos congresos y
minisimposia. Ha ejercido como evaluadora para
prestigiosas revistas especializadas. Desde 2002 es Editora Asociada del Rocky
Mountain Journal of Mathematics. Autora o coautora de numerosos artículos
científicos y varias monografías en análisis armónico y funcional y directora
de dos tesis doctorales, ha desarrollado asimismo una intensa actividad en el
campo de la educación matemática, habiendo recibido diversos galardones a la excelencia docente.
|