Siete puentes, un camino: Königsberg

69 En este trabajo se presenta el problema de los puentes de Konigsberg, resuelto por Leonhard Euler, en 1735, como herramienta didáctica que se puede utilizar para introducir a los alumnos en el estudio de la Combinatoria. Se indican también las primeras nociones elementales de la Teoría de Grafos, adaptadas al nivel de conocimiento de estos alumnos, y se comentan algunas aplicaciones de esta teoría a la resolución de problemas relacionados con el que sirve de base al trabajo, como puede ser el problema de dibujar una figura sin levantar el lápiz del papel. This article deals with the problem of Königsberg bridges solved by Leonhard Euler in 1735 as the teaching tool for students’ introduction to combinatory analysis. Elementary knowledge of the Grafos Theory at student level is also pointed out, as well as some applications of this theory to the solving of problems related to the one central to this work, as can be figure drawing without raising the pencil from the writing paper. s un hecho constatado que en enseñanza universitaria, cuando en la licenciatura de Matemáticas se presentan a los alumnos las primeras nociones de la Teoría de Grafos, base de la Matemática Discreta, tan en boga actualmente, el Profesor suele recurrir en su primera clase a comentarles el Problema de los Puentes de Königsberg , a fin de lograr varios objetivos a la vez. En primer lugar, para señalarlo como uno de los problemas —que junto a otros de similar importancia como puedan ser el Problema de los 4 Colores, resuelto mediante ordenador por K. Apple y W. Haken, en 1976 o el Problema sobre Planaridad de Grafos, resuelto por Kuratowski en 1930 (véase Biggs y otros, 1986: 180 y 147, resp.)— dio lugar al nacimien- to de la Teoría de Grafos. En segundo lugar, como herramienta muy apropiada para ir introduciendo al alumno en los conceptos más básicos de esta teoría, como puedan ser los de grafo en sí, vértices, aristas, incidencia y adyacencia. Y finalmente, aunque según el dicho inglés no lo menos importante (the last, but not the least), para mostrar a sus alumnos lo que significa un proceso de modelización en el que un matemático cuando se le presenta un problema de la vida real lo modeliza, es decir, prescinde del significado físico real de los elementos del problema (zonas de la ciudad y puentes en este caso), crea una nueva teoría matemática ade- Juan Núñez Valdés. Universidad de Sevilla María Alfonso Pérez, Silvia Bueno Guillén, Mª del Rocio Diánez del Valle, Mª del Carmen de Elías Olivenza Siete puentes, un camino: Königsberg E cuada a este modelo (la Teoría de Grafos, en este caso), resuelve el problema según los fundamentos de esta teoría, y posteriormente traduce la solución obtenida (en grafos) a la situación real de partida, es decir, cuando en esquema, realiza las siguientes operaciones: 45 Febrero 2004, pp. 69-78 Euler calculaba sin aparente esfuerzo, como los hombres respiran o las águilas se sostienen en el aire. Arago El origen de este artículo surge de la realización individual de un trabajo sobre los Puentes de Königsberg, por parte de cuatro de sus autoras, alumnas de la asignatura de libre configuración: “Introducción a la Teoría de Grafos y sus Aplicaciones”, cursada en la licenciatura de Matemáticas de la Universidad de Sevilla, durante el primer cuatrimestre del curso 2002-03 e impartida por el autor que resta, profesor del Departamento de Geometría y Topología de la Facultad de Matemáticas de esa Universidad. Una vez le fueron presentados estos cuatro trabajos por separado al profesor, éste le propone a las alumnas realizar un trabajo unificado conjunto que con la incorporación de algunos aspectos metodológicos y didácticos no sólo contribuyese a mejorar la impartición de la citada asignatura en años venideros, sino que también pudiese servir como una introducción amena y sencilla a la combinatoria que se enseña en Secundaria. Fruto de todo ello es el artículo que se presenta, que se ha estructurado como sigue: tras esta introducción, se indican los objetivos que los autores se han planteado relacionados fundamentalmente con su aplicación a la introducción de la combinatoria en Secundaria. En las siguientes secciones se ofrecen unas breves pinceladas históricas sobre la ciudad de Königsberg y sobre tres de sus más destacados ciudadanos de los últimos 300 años: el filósofo Immanuel Kant, el físico Gustav Robert Kirchoff y el matemático David Hilbert. Posteriormente se aborda el núcleo fundamental del artículo. Se exponen el Problema de los Puentes de Königsberg y la solución al mismo (ingeniosa, como se verá) dada por Euler en 1735 y puede observarse el proceso de modelización ideado por Euler para resolver una situación concreta y la formulación de una nueva teoría matemática, la Teoría de Grafos, como base de esta resolución. Como complemento, también se presenta una breve biografía de L. Euler. Finalmente, se recogen, de forma breve, otros problemas relacionados con el de los Puentes de Königsberg , que pudieran servir al alumno para compararlos con otros parecidos o incluso para inventarse él mismo otros similares. Objetivos y motivación La motivación que nos ha llevado a escribir estas líneas obedece a dos razones. La primera de ellas, la de utilizar la historia de las matemáticas para la introducción de determinados temas del currículo. Si además, en nuestra opinión, esta introducción histórica no sólo se limita a dar unos cuantos datos biográficos del matemático o científico autor de algún resultado que se vaya a ver en clase, sino que además, el profesor explica a los alumnos cómo surgió ese resultado, sus antecedentes, las dificultades que en esa época existían para obtenerlo y su relación con otros resultados, tanto de Matemáticas como de otras disciplinas, seguro que la motivación de los alumnos a la hora de recibir esas enseñanzas y su interés por las mismas aumentan de forma notable y su predisposición para estudiarlas es bastante más elevada que si todo esto no se hubiese llevado a cabo. La segunda de las razones está relacionada con la anterior; de hecho, pudiera decirse que son complementarias. Si además de todo lo comentado anteriormente, el profesor puede aprovechar esta explicación histórica para introducir el tema presentándo a los alumnos una situación que, aunque pareciera que no tiene nada que ver con lo que después se va a explicar, facilite el que piensen por ellos mismos y sean capaces de ir elaborando ese tema. Esta experiencia es positiva y el profesor habrá conseguido, generalmente con menos esfuerzo del habitual, que los alumnos se hayan motivado más y que los conocimientos sobre ese tema se hayan afianzado de manera más fuerte que en otras condiciones. Por otra parte, sabido es que la combinatoria es una de las partes de las Matemáticas que a los alumnos de secundaria más les agrada, aunque ciertamente les resulte difícil resolver los problemas. Este tema les gusta por las connotaciones que la combinatoria tiene sobre la vida real. Así, los enunciados de los problemas de combinatoria suelen reflejar situaciones que el alumno, o bien ha experimentado personalmente, o bien entiende que aparecen en la realidad. Los inconvenientes que encuentran a la hora de resolver los problemas, no son las fórmulas en sí, sino las dificultades que surgen a la hora de decidir en las cuestiones que se les plantean si influye o no el orden y si hay o no repetición. El Problema de los Puentes de Königsberg cumple, en nuestra opinión, los dos requisitos considerados anteriormente, para que el profesor de secundaria pueda realizar una introducción de la combinatoria, sencilla, amena, asequible de entender y fácilmente manipulable por los alumnos, en el sentido esto último de ir ellos mismos probando y obtener deducciones y conclusiones acerca de las preguntas que el profesor plantea sobre el tema. El alumno, a la vez que el profesor va narrando la historia, puede ir averiguando por sí mismo si existe el camino que se plantea, si la solución, caso de existir, es única o no, si este problema es parecido a otros que pudieran ocurrírsele y en definitiva, si en lugar de llegar a la solución considerando todas las posibilidades, es capaz de formular una estrategia que lleve a la misma de una forma más simple, rápida y lógica a la vez. Todo ello, como puede observarse, son objetivos del estudio de la combinatoria en Secundaria. Si además de todo esto, el profesor logra que los alumnos comprendan la SUMA 45 Febrero 2004 70 SUMA 45 Febrero 2004 71 importancia del proceso de modelización en Matemáticas, es decir, de abstraerse de la realidad y dejar de considerar los aspectos irrelevantes del problema para centrarse en los esenciales, mejor que mejor. Por todo ello, los objetivos que nos hemos planteado son los siguientes: 1. Utilizar la historia de las Matemáticas como herramienta de apoyo para las clases de Matemáticas de Secundaria (este objetivo es extrapolable a la enseñanza universitaria). 2. Ofrecer una introducción amena, sencilla y agradable al estudio de la combinatoria en la Enseñanza Secundaria. 3. Estimular la capacidad de pensamiento y de razonamiento del alumnado de Secundaria con problemas más o menos ingeniosos, distintos de los tradicionales. 4. Facilitar enunciados parecidos al de los puentes de Königsberg para que el alumno intente solucionarlos mediante el uso de estrategias personales. 5. Proporcionar un primer ejemplo, sencillo, de lo que se denomina proceso de modelización en Matemáticas. Finalmente, antes de terminar esta sección, nos gustaría comentar una nueva posibilidad de utilizar el contenido de este artículo en una actividad no inicialmente prevista por los autores a la hora de redactarlo. Esta posibilidad pudiera ser considerada también como un objetivo más a alcanzar tras su lectura. La ciudad de Königsberg La palabra “Königsberg ” significa en alemán “Colina Real”. La ciudad de Königsberg (en algunos textos se escribe Koenigsberg) , actualmente llamada Kaliningrado, se encuentra a orillas del Mar Báltico, en territorio ruso y a unos 50 kilómetros de la frontera con Polonia. Hasta mediados del siglo pasado, Königsberg pertenecía a la nación de Prusia, estando situada al este de la misma. La ciudad estaba atravesada por el río Pregel, que en la actualidad se denomina Pregolya. Königsberg tiene su origen en una fortaleza del siglo XIII (aproximadamente hacia 1255) construida por los caballeros teutónicos. Su función era ser el centro de la lucha para expulsar a los eslavos fuera de Prusia e instaurar el régimen germánico. Fue destruida en 1263 por los prusianos, y posteriormente reedificada en 1268. Posteriormente, Königsberg entró a formar parte de la Liga Hanseática en el siglo XIV, hacia 1365. Desde el siglo XVI al XVII albergó a los maestres de la orden teutónica y a los duques de Prusia. La ciudad sufrió mucho durante la guerra de los siete años, donde la ocuparon primero los rusos, en el siglo XVIII, tras la batalla de Frienland, y luego los franceses, en el siglo XIX. Durante todo ese tiempo y hasta 1945, Königsberg fue la capital de Prusia Oriental, habiendo también pertenecido al Imperio Alemán y al III Reich. Durante las dos guerras mundiales, Königsberg fue duramente atacada y seriamente dañada. Muchos de sus edificios históricos fueron derrumbados por bombardeos. En 1946, en la Conferencia de Berlín, la ciudad pasó a manos de la antigua URSS, que le cambió el nombre, un año después, por el de Kaliningrado. La reciente cumbre Unión Europea-Rusia ha confirmado las discrepancias sobre el futuro de Kaliningrado, que probablemente se transformará pronto en un enclave ruso dentro de la Unión Europea. Königsberg en tiempos de Euler Kaliningrado, siglo XX Entre sus principales construcciones se encuentra la Universidad Albertina, fundada en 1544 por el duque de Prusia, Alber- to de Brandenburgo. Esta universidad pronto se convirtió en un importante centro de estudios al que asistía un gran número de estudiantes por el espíritu de la reforma que predominaba. En el siglo XVII, decayó su importancia debido a las largas guerras y por las continuas disputas teológicas, aunque después, bajo la protección de los reyes prusianos, la universidad alcanzó un nuevo período de esplendor, sobre todo en tiempos del filósofo nacido en la propia ciudad, Immanuel Kant. La catedral, iniciada en el año 1325, es de estilo fundamentalmente gótico alemán. En su interior hay numerosas esculturas y pinturas del renacimiento flamenco. El palacio es obra de Von Unfried. En él fueron coronados los principales reyes de Prusia, como Federico III, en 1701 y Guillermo I, en 1861. Ciudadanos destacados nacidos en Königsberg En la ciudad de Königsberg nacieron tres de las personalidades científicas y filosóficas más importantes de los últimos tres siglos, contando con el actual. En concreto y por orden cronológico, el filósofo I. Kant, el físico G.R. Kirchoff y el matemático D. Hilbert vieron la luz por primera vez en esta ciudad y pasaron en ella los primeros años de sus vidas. Ofrecemos a continuación en esta sección unas breves notas biográficas de todos ellos. IMMANUEL KANT, para muchos uno de los más grandes filósofos de todos los tiempos y el pensador más influyente de la era moderna, nació en Königsberg en 1724. Tras realizar sus estudios primarios, Kant ingresó en la Universidad, donde gustaba del estudio de los autores clásicos. También se dedicó a estudiar física y matemáticas. La muerte de su padre hizo que Kant tuviese que abandonar sus estudios y ganarse la vida como tutor privado. En 1755, reanudó sus estudios universitarios y obtuvo el doctorado. Posteriormente, impartió clases en la universidad y dio conferencias de ciencias y matemáticas, para llegar paulatinamente a disertar sobre casi todas las ramas de la filosofía. Durante este periodo, sus escritos y conferencias hicieron que se ganara una gran reputación como filósofo, aunque ello no bastó para que se le concediera una cátedra, que no logró hasta 1770, cuando se le designó profesor de lógica y metafísica. En años posteriores continuó con su labor docente, atrayendo un gran número de estudiantes a su ciudad natal. Sus nada ortodoxas enseñanzas religiosas le crearon problemas con el gobierno de Prusia, hasta el punto de que el rey, Federico Guillermo II, le llegó a prohibir impartir clases sobre asuntos religiosos, orden que Kant obedeció hasta la muerte del monarca. Ya una vez retirado, en 1978, Kant publicó un epítome con sus ideas en materia religiosa. Sus principales obras son: “Los Fundamentos de la Metafísica de las Costumbres”, “La Crítica del Juicio” y “Primeros Principios Metafísicos de las Ciencias de la Naturaleza”. Kant murió el 12 de Febrero de 1804 en su ciudad natal, donde había pasado toda su vida. GUSTAV ROBERT KIRCHOFF, físico alemán nacido en Königsberg en 1824, era hijo de un abogado. A los 18 años entró en la universidad de su ciudad, obtuvo el doctorado cinco años después y recibió una beca para continuar estudios de postgraduado en París, adonde no pudo viajar por la revolución de 1848. Fue profesor en Berlín y también en las universidades de Breslay y Heidelberg. Entre sus descubrimientos científicos más importantes citamos la formulación en 1845 de sus leyes relativas a las corrientes eléctricas en las redes de conductores, sus aportaciones a la física de las radiaciones, que le acreditan como creador del análisis espectral, y su contribución al conocimiento de la constitución íntima de la materia. En 1859 comunicó a la Academia de Berlín la presencia de sodio en el Sol, abriendo de esta forma un nuevo capítulo de la Física: la Astrofísica. Ese mismo año, estableció la ley que lleva su nombre. En 1860 realizó unas investigaciones sobre las transformaciones del calor en energía luminosa y a partir de 1864, trabajó en diversas cuestiones de la Física, tales como las descargas eléctricas oscilantes, la velocidad del sonido en los tubos sonoros o las características del éter (que entonces se creía existente). Murió en 1887 en Berlín. 72 SUMA 45 Febrero 2004 DAVID HILBERT. Este eminente matemático alemán nació en Königsberg el 23 de enero de 1862. Estudió en el instituto y en la Universidad de su ciudad, doctorándose bajo la dirección del profesor Lindemann en 1885. Seguidamente, se incorporó al profesorado de dicha Universidad en 1886, llegando a obtener el título de catedrático. En 1895, reclamado por Klein, consiguió la cátedra de matemáticas en la Universidad de Gottingen, donde continuó toda su carrera profesional. Hilbert trabajó muchas ramas de la matemática pura y aplicada, como la teoría de la relatividad, la teoría de invariantes, el análisis funcional (son especialmente conocidos sus Espacios de Hilbert), las ecuaciones integrales y el cálculo de variaciones, entre otras. Estos trabajos influyeron de forma notable en la geometría, aumentando su prestigio al participar en el Segundo Congreso Internacional de Matemáticos, celebrado en París a finales del siglo XIX. En su intervención, propuso sus 23 problemas abiertos, muchos de los cuales han sido resueltos abriendo nuevos campos en la matemática. Se retiró en 1930, siendo nombrado ciudadano de honor de la ciudad de Königsberg . Murió en Gottingen, en 1943. Su lema fue: “Nosotros debemos conocer, nosotros conoceremos”. El problema de los puentes de Königsberg Como ya se ha comentado, en el siglo XVII la ciudad de Königsberg estaba atravesada por el rio Pregel (actualmente llamado Pregolya), que se dividía en el Viejo y en el Nuevo Pregel. Este río formaba dos islas a su paso por la ciudad, una de las cuales, la más pequeña, se llamaba la isla Kneiphof. Para unir las cuatro partes de la ciudad separadas por la geografía, existían siete puentes. Se cuenta que los domingos por la mañana y los días de fiesta, los habitantes de la ciudad salían a pasear (presumiblemente, para tomar el sol, habida cuenta del frío que debía hacer en Königsberg , dada su situación geográfica) y se entretenían tratando de resolver el siguiente problema: ¿Es posible recorrer todas las zonas de la ciudad, atravesando todos los puentes, una y sólo una vez cada uno de ellos? Mientras unos negaban la posibilidad de hacerlo y otros dudaban, nadie sostenía que fuese posible hacerlo realmente. De hecho, es un dato histórico que un comité de jóvenes de la ciudad visitó, en 1735, a Leonhard Euler, matemático suizo nacido en Basilea en 1707, para pedirle que resolviera el conflictivo problema. La solución de Euler al problema de los puentes de Königsberg Euler, una vez enterado del problema, se dedicó por completo al estudio del mismo, dando una solución simple e ingeniosa, que servía también para cualquier número de puentes. Para empezar, Euler formuló el problema de la siguiente manera: “En la ciudad de Königsberg, en Prusia, hay una isla Allamada Kneiphof, rodeada por los dos brazos del río Pregel. Hay siete puentes a, b, c, d, e, fy g, que cruzan por los dos brazos del río. La cuestión consiste en determinar si una persona puede realizar un paseo de tal forma que cruce cada uno de estos puentes sólo una vez”. A los pocos meses Euler presentó un voluminoso informe a la Academia rusa de San Petersburgo, en el que afirmaba haber demostrado la imposibilidad de tal ruta. Posteriormente, publicó un artículo titulado Solutio problematis ad geometriam situs pertinentis (Euler 1736), en el que resolvía el problema en el caso general, obteniendo condiciones generales para la existencia de soluciones para cualquier problema del mismo tipo. Este artículo es considerado por varios autores como el nacimiento de la Teoría de Grafos, utilizada actualmente en una gran cantidad de aplicaciones, y también como una de las primeras manifestaciones de una nueva Geometría 73 SUMA 45 Febrero 2004 en la que únicamente importa la posición de los objetos y no sus medidas. Ya Leibniz había sido el primero en hablar de geometriam situs, o geometría de la posición y que actualmente se llama Topología. Según Euler, todo se basaba en utilizar una notación adecuada. Para ello, Euler llamó A, B, Cy Da las distintas regiones de Königsberg. El camino que va desde Ahasta Bpuede ser por el puente ao por el b, pero Euler lo designó por AB. Una vez allí, para ir a D, se sigue el camino BD, designando la trayectoria total por ABD, y así sucesivamente hasta recorrer todas las zonas y puentes, de manera que al final se obtendrá una combinación de ocho letras. Sin embargo esta notación tiene un inconveniente, y es que no tiene en cuenta que para ir de una zona a otra puede que exista más de un puente. Además, en dicha combinación de letras, el camino AB debería aparecer dos veces, ya que también está el BA; el camino CA habría de aparecer otras dos veces; y tan sólo una los caminos AD, BD, y CD. Por lo tanto, las letras A, B, C, D, deben formar una serie de ocho letras, apareciendo el número requerido de veces las combinaciones de las mismas. Euler vio que esta situación concreta no era posible, ya que, por ejemplo, si se empieza en la región A, si esta región sólo conectara con el puente a, como puede que se llegue o se venga de ella, la letra Aaparecería una vez en la combinación de 8 letras. Si hubiera tres puentes que condujeran a la zona, entonces la letra Aaparecería dos veces. Pero como llegan cinco puentes, en este caso, Adebe aparecer tres veces en esa sucesión. Similarmente, Bestaría dos veces; al igual que Dy C. Pero entonces, ya tendríamos nueve letras en la sucesión, cuando para ser la ruta posible únicamente deberían haber ocho. Euler dedujo entonces que no se podía realizar la travesía requerida a través de los siete puentes de Königsberg . Sin embargo, y como dijimos anteriormente, Euler no se contentó sólo con solucionar esta situación concreta, sino que se dedicó por completo al estudio del problema en general, obteniendo una solución que servía también para cualquier número de puentes. Para ello, el procedimiento que siguió Euler consistió en lo siguiente: en primer lugar, apuntó en un papel el número de puentes más uno (ocho, en el caso de Königsberg ). Después, abajo a la izquierda formó una columna con todas las letras de las regiones (A, B, Cy D, en este caso). A su derecha, formó una segunda columna con el número de puentes que salen de cada una de las correspondientes zonas (5, 3, 3 y 3, en este caso), marcando con un asterisco aquellas letras de las que salen un número par de puentes. A continuación realizó las siguientes operaciones con los números de la segunda columna: si el número de la segunda columna (número de puentes que llegan a una determinada región) es impar, lo aumentó en una unidad y lo dividió entre dos. Si el número es par, lo dividió entre dos. Euler colocó finalmente a la derecha una tercera columna con las cuentas anteriormente especificadas (3, 2, 2, 2, en nuestro caso). Euler dedujo entonces que el problema sólo tendría solución si la suma de los números de la última columna es menor o igual que el número inicialmente puesto. Más concretamente, si esta suma es igual al número inicial (8, en este caso), la ruta comienza en una zona no marcada con asterisco, y si es menor, en una señalada. Obsérvese que en el caso de Königsberg , esta suma es nueve, no menor o igual que ocho, por lo que no hay solución al problema de los puentes de Königsberg . Vamos a realizar, con la perspectiva y conocimientos actuales, algunas observaciones al procedimiento seguido por Euler en su razonamiento, que nos muestran bien a las claras su extraordinaria inteligencia, intuición, agudeza mental y cuantas otras buenas cualidades deseemos atribuirle, con la seguridad de quedarnos cortos en estas apreciaciones e incluso de ser incapaces de captar, en toda su intensidad, la enorme capacidad de razonamiento de tan ilustre personaje. Puede observarse que: • La suma de los números de la segunda columna, es siempre par, ya que su mitad refleja el número de puentes. • Si la suma de dichos números se aumenta en dos unidades y luego se divide entre dos, el resultado es el número escri- to en la parte superior de la tabla construida. • Si los números de la segunda columna son todos pares, la tercera columna, formada por las mitades de ellos, sumará una unidad menor que el número escrito inicialmente de la tabla (con lo que la ruta será siempre posible) • Si en la segunda columna hay sólo dos números impares, la ruta requerida será también siempre posible, porque la suma de la tercera columna coincidirá con el número inicial. • Si hay más de dos números impares en la segunda columna, la ruta no será nunca posible, pues la suma de la tercera columna superará siempre al número inicialmente escrito. Por tanto, como reglas para cruzar todos los puentes una sola vez, se tienen: 74 SUMA 45 Febrero 2004 • Si hay más de dos regiones a las que conducen un número impar de puentes, la ruta no será posible. • Si sólo hay dos regiones a las que llega un número impar de puentes, la ruta se podrá realizar, comenzando en una de esas regiones. • Si no hay regiones a las que conduzcan un número impar de puentes, la ruta pedida se podrá realizar, comenzando en cualquier punto. Empleando un lenguaje más actual y propio de las Matemáticas, la solución dada por Euler se podría enunciar así: La condición necesaria y suficiente para que tal ruta exista es que el número de zonas de la ciudad a las que le llega un número impar de puentes sea 0 (en cuyo caso la ruta será cerrada, es decir, comenzará y acabará en la misma región) o 2 (en cuyo caso la ruta será abierta, es decir, comenzará en una región y terminará en otra distinta). Hay que indicar que, en realidad, Euler sólo demostró la condición necesaria en su artículo de 1735, quizás porque para él, la condición suficiente era trivial. Esta condición suficiente tuvo que esperar casi siglo y medio para ser probada, lo que hizo Carl F. Hierholzer, en 1873 (Hierholzer, 1873). Como anécdotas y antes de terminar esta sección con una breve biografía de Leonhard Euler, señalaremos que en 1875 los alemanes construyeron un nuevo puente en la ciudad de Konisberg, situado entre las zonas B y C, con lo cual ya sí era posible realizar la ruta comentada, si bien el camino era abierto, es decir, no se llegaba al mismo punto de partida. Diremos también que sólo cuatro de los puentes originales de Königsberg en 1735 sobrevivieron a la segunda guerra mundial. Los de Schmiede y Koettel fueron destruidos durante la guerra, los de Kraemer y Greune, fueron reconstruidos por los rusos, que los unieron en la carretera de Leninsky Prospekt y el de Honing fue reconstruido por los alemanes en 1935, por lo que sólo los puentes de Holz y Hohe se conservan actualmente indemnes. Leonhard Euler Leonhard Euler es uno de los más grandes científicos de nuestra historia. Su obra aborda todos los campos de las matemáticas y también en astronomía, óptica, acústica y mecánica. Era un hombre entrañable, animoso y alegre, que además, poseía una gran energía en su trabajo. Euler nació el 15 de abril de 1707 en Basilea (Suiza). Su padre, pastor calvinista, deseaba que su hijo siguiera sus pasos, por lo que Euler inició estudios de Teología. Sin embargo, el mismo padre, que había recibido formación matemática de Jakob Bernoulli (1654-1705), reconoció enseguida el talento de su hijo y abandonó su idea de convertirlo en clérigo. Así, el joven Leonhard estudió en la Universidad de Basilea, teología, lenguas orientales, medicina, astronomía, física y matemáticas, teniendo como profesor de esta última disciplina a Johann Bernoulli (1667-1748). A los 17 años, Euler recibe una mención honorífica de la Academia de las Ciencias de París, por un trabajo sobre la mejor disposición de los mástiles de un barco. No sería ésta la primera vez, ya que Euler consiguió en doce ocasiones dicha mención. En 1727, fue invitado por la emperatriz Catalina I para que ocupara un puesto en la Academia de San Petersburgo (hoy Leningrado), donde ya trabajaban sus amigos, los hermanos Daniel y Nikolaus Bernoulli, como profesores de matemáticas. Durante el viaje, Euler se entera de la muerte de Nikolaus por lo que a poco de llegar, estuvo a punto de volverse, aunque finalmente no lo hizo. En 1730 ocupa la cátedra de Filosofía Natural y en 1733 sucede a su amigo Daniel, que abandona Rusia para hacerse cargo de una cátedra de Matemáticas en Basilea. Se decía que Euler producía memorias en media hora, entre la primera y segunda llamada a comer y que componía a menudo sus memorias con un bebé en su regazo mientras que los niños mayores jugaban a su alrededor. Euler publica incesantemente en la revista de la Academia. Fue el iniciador del análisis matemático y de la geometría analítica de tres dimensiones y hacía cálculos sin ningún esfuerzo aparente. Aplicó también el cálculo matemático a la Astronomía, llegando a resolver un problema astronómico en sólo tres días, cuando en opinión de los astrónomos se hubiesen necesitado varios meses para hacerlo. No obstante, forzó tanto la vista en resolver ese problema que sufrió la pérdida de la visión de un ojo a los 30 años (hecho que le haría ganarse el apodo de cíclope) y sufrió de ceguera casi total durante los últimos 17 años de su vida. En 1741, recibe otra invitación, esta vez de Federico el Grande de Prusia, para incorporarse a la Academia de Berlín, en donde pasa 25 años. Cuando sus relaciones con el rey se deterioran, acepta en 1766 un nuevo ofrecimiento de Catalina la Grande y vuelve a Rusia. Euler es considerado una de los autores más prolíficos de la historia. A lo largo de su vida publicó más de 500 libros y 75 SUMA 45 Febrero 2004 artículos. Añadiendo su obra póstuma, se alcanza la cifra de 886 trabajos. Euler contribuyó al avance de la ciencia, introduciendo y popularizando algunas notaciones en matemáticas: Utilizó la letra epara indicar la base del logaritmo neperiano, la letra griega π para designar la razón entre la longitud de la circunferencia y su diámetro, y la letra ipara designar la unidad imaginaria. También en Geometría encontramos huellas de Euler. Utilizó las letras minúsculas a, b, c para los lados de un triángulo y las mayúsculas para los vértices y ángulos A, B, C opuestos a cada uno de los lados. Llamó R, r, s, respectivamente, a los radios de la circunferencia circunscrita, inscrita y al semiperímetro del triángulo. Demostró que el ortocentro (punto donde se cortan las alturas de un triángulo), el baricentro (punto donde se cortan las medianas) y el circuncentro (punto donde se cortan las mediatrices), están alineados, formando la llamada Recta de Euler. Entre sus obras más famosas se encuentran Introducción al análisis de los infinitésimos, en 1748, Instituciones de cálculo diferencial, en 1755, e Instituciones de cálculo integral, en 1768. Leonhard Euler murió, trabajando hasta el último día, en San Petersburgo el 7 de septiembre de 1783. Los puentes de Königsberg y la teoría de Grafos De lo visto anteriormente puede colegirse que la resolución por Euler del problema de los puentes de Königsberg constituye un claro ejemplo de un proceso de modelización. En primer lugar, Euler reemplazó el mapa de la ciudad por un simple diagrama de puntos (representando con las letras A, B, C y D, las zonas de la ciudad) y aristas entre ellos (que representaban los siete puentes. Así, la arista aunía las zonas Ay B, la d, la Ay la C y así sucesivamente, tal como se observa en la figura). Este diagrama constituye el germen de lo que posteriormente se conocería como grafo, razón por lo que muchos autores consideran a Euler como el padre de la Teoría de grafos. Básicamente, un grafo consiste en un conjunto finito de vértices (puntos) y un conjunto finito de aristas (líneas) entre ellos. En un grafo, dos vértices se dicen adyacentes si ambos son extremos de una arista. Toda arista es incidente con sus vértices extremos y dos aristas se dicen incidentes si ambas comparten un vértice común. Se denomina valencia (o grado) de un vértice al número de vértices adyacentes con él o bien al número de aristas incidentes con él. Por convenio, un vértice no se considera adyacente consigo mismo y los vértices de valencia 0 se denominan vértices aislados. Relativo a los problemas de incidencia y adyacencia, tiene especial importancia el denominado Lema del apretón de manos (Handshake Lemma), según el cual en todo grafo el número de vértices con valencia impar es par. Un camino en un grafo es una sucesión consecutiva de vértices y aristas del grafo, comenzando por un vértice, del tipo v1, e1, v2, e2, v3, ..., vr-1, er, de tal manera que cada arista eiuna los vértices vi-1 y vi. Veamos cómo a partir únicamente de estos dos conceptos básicos, el problema de los puentes de Königsberg puede ser reformulado usando terminología de Teoría de Grafos: el objeto del problema es encontrar un camino (no necesariamente cerrado) sobre un grafo que contenga cada arista del grafo una y sólo una vez. En Teoría de Grafos, un camino de este tipo se denomina, como era de esperar, camino euleriano y Euler probó entonces que el grafo de Königsberg no posee un camino euleriano. La Teoría de Grafos también permite la resolución de problemas relativos a campos tan separados como puedan ser la lingüística, la investigación operativa, la electricidad, la genética, la sociología, etc. Para una visión más general de los aspectos básicos de esta teoría se puede consultar Bollobas (1985) o Harary (1969). Otros problemas relacionados con el de los puentes de Königsberg Dibujar una figura sin levantar el lápiz del papel. El concepto de camino euleriano en un grafo, definido anteriormente, así como la consideración del denominado Lema del Apretón de Manos, permiten dar una interpretación geo- 76 SUMA 45 Febrero 2004 La Teoría de grafos permite la resolución de problemas relativos a campos tan separados como puedan ser la lingüística, la investigación operativa, la electricidad, la genética, la sociología, etc. 77 SUMA 45 Febrero 2004 métrica intuitiva y simple de los grafos eulerianos como aquellos grafos que se pueden dibujar sin levantar el lápiz del papel y sin pasar dos veces por la misma arista, permitiéndose sin embargo pasar dos veces por el mismo vértice. En particular, se tienen: • Todo grafo que no tenga vértices de valencia impar se puede dibujar sin levantar el lápiz del papel y sin pasar dos veces por la misma arista. Más concretamente, se puede dibujar empezando desde cualquier vértice, y el dibujo será cerrado, es decir, que termina en el mismo vértice dónde empezó. • Si un grafo tiene exactamente dos vértices de valencia impar, entonces se puede dibujar sin levantar el lápiz del papel y sin pasar dos veces por la misma arista, pero en este caso hay que empezar siempre en uno de esos dos vértices y terminar en el otro. Este es el caso en el que se añade un puente más al problema de los puentes de Königsberg • Si un grafo tiene 4 ó más vértices de valencia impar, entonces no se puede dibujar sin levantar el lápiz del papel y sin pasar dos veces por la misma arista. Estas sencillas reglas permiten resolver la situación que se planteó en la ciudad de Königsberg , en 1875, cuando se construyó un nuevo puente que unía la orilla Bcon la C. ¿Era posible entonces hacer un recorrido de forma que se pase una y solo una vez por cada uno de los puentes? Veamos el grafo que se tiene ahora en este caso: Ahora hay dos vértices de valencia par (By C) y dos con valencia impar (Dcon tres y Acon 5). Por tanto, sí es ya posible el recorrido, siendo estos dos vértices de valencia impar los vértices inicial y final. Además, el camino es abierto, ya que se empieza en un punto y se termina en otro distinto. Un posible camino podría ser por ejemplo: DCBDACABA. El juego icosaédrico. En 1859, Sir William Rowan Hamilton inventó un juego: “The Icosian Game”, que consistía en ponerle el nombre de una ciudad a cada uno de los 20 vértices de un dodecaedro. El jugador debía encontrar un camino cerrado que pasara por todas esas ciudades y además exactamente, una y sólo una vez por cada una de ellas (véase Biggs y otros, 1986: 32). Puede observarse que este juego es muy parecido al de los Puentes de Königsberg , aunque en este caso los papeles de los vértices y de las aristas estén intercambiados entre sí. El camino anteriormente descrito recibe ahora, en Teoría de Grafos el nombre de ciclo hamiltoniano, para diferenciarlo del ciclo euleriano, ya reseñado. Es similar a éste es el probblema del “salto del caballo”, consistente en situar un caballo en cualquier casilla de un tablero de ajedrez y ser capaz de pasar, con el salto del caballo, por todas las restantes 63 casillas del tablero, y además, una sola vez por cada una de ellas. Este problema fue resuelto por Vandermonde, en 1771 (Biggs y otros, 1986: 32). Algunos pasatiempos de Sam Loyd. El problema consiste en dibujar el símbolo griego haciendo la menor cantidad posible de cambios de dirección. SOLUCIÓN. Puede dibujarse con una línea continua, con trece cambios de dirección: