Teoría de grafos

Caso de los puentes de Königsberg
La ciudad de Königsberg, hoy Kaliningrado, se encuentra a orillas del Mar Báltico, en territorio Ruso y a unos 50 kilómetros de la frontera con Polonia. En el pasado perteneció a Prusia. Uno de sus habitantes más ilustres fue el filósofo Immanuel Kant.

En Königsberg se juntan dos ríos, formando una isla en su confluencia. Siete puentes unían (ya no, pues laciudad fue parcialmente destruida durante la Segunda Guerra Mundial) las diferentes partes de la ciudad, como se aprecia en el mapa de la época. En el siglo XVIII se hizo popular como adivinanza o pasatiempo averiguar si era posible cruzar los siete puentes de la ciudad pasando sólo una vez por cada uno de ellos.

Este problema, por supuesto, puede resolverse mediante un estudio exhaustivo detodos los posibles itinerarios. Pero las matemáticas se interesan en generalizar el problema y buscar una solución sencilla y válida para todos los posibles mapas de ciudades, e incluso objetos más generales.

El problema es simplemente encontrar un trayecto, alrededor de una serie de puentes, que cruce solamente una vez cada uno de ellos. El mapa de abajo muestra la disposición de siete puentesy dos islas en la ciudad de Königsberg.

En 1736, el matemático suizo radicado en San Petersburgo Leonhard Euler publicó "Solutio Problematis ad Geometriam Situs Pertinentis", un artículo en el que resolvía el problema en el caso general. Este trabajo es considerado como el nacimiento de la Teoría de Graficos, utilizada hoy en día en una multiplicidad de aplicaciones, y también uno de lasprimeras apariciones de una «nueva geometría» en la que importan sólo las propiedades estructurales de un objeto y no sus medidas. A esto se refieren las palabras «geometriam situs» en el título de Euler, palabras que hoy se traduce como topología.

La topología es una de las ramas más nuevas de las matemáticas. Una manera simple de describirla es aquella en la cual se señala que su orientación secentra en el estudio de ciertas propiedades de las figuras geométricas. El término topología fue usado por primera vez en 1930 por el matemático Solomon Lefschetz. Generalmente ha sido clasificada dentro de la geometría, se la llama a menudo geometría de la goma elástica, de la lámina elástica o del espacio elástico, pues se preocupa de aquellas propiedades de las figuras geométricas del espacio queno varían cuando el espacio se dobla, da la vuelta, estira o deforma de alguna manera. Las dos únicas excepciones son que el espacio no se puede romper creando una discontinuidad y que dos puntos distintos no se pueden hacer coincidir. La geometría se ocupa de propiedades como la posición o distancia absoluta y de las rectas paralelas, mientras que la topología sólo se ocupa de propiedades comola posición relativa y la forma general.

El estudio de los fundamentos de la topología no es a menudo parte de los programas de estudios de las matemáticas en las escuelas de enseñanza secundaria y, por ello, para muchos suena como el conocimiento de algo intimidante y extraño. Sin embargo, hay algunas ideas de las bases de la topología fácilmente captables e interesantes, aplicables a muchassituaciones, incluidas algunas de diversión. Una de estas áreas es la topología de redes de trayectorias de circulación, que fue desarrollada por Euler en 1735, y que es el tema central de este trabajo.

La idea de Euler fue considerar los cuatro lugares terrestres, que se deseaban comunicar (hay 4 de ellos), como puntos de destino y, a los famosos puentes, como trayectorias entre esos puntos. Enconsecuencia, el mapa de Königsberg –en esencia matemática– puede ser entonces reducido al siguiente diagrama, que es un ejemplo de lo que se suele llamar un gráfico:

Un gráfico, es una figura cuyas líneas o curvas (llamadas márgenes), conectan puntos o vértices. En consecuencia, la trayectoria de los puentes de Königsberg puede ser reformulada como un gráfico, en el cual los márgenes son...