Los puentes de Königsberg
En la ciudad Prusiana de Königsberg (actualmente Kaliningrado, Rusia), donde nacieron, entre otros, el filósofo Immanuel Kant y el gran matemático David Hilbert, había en el siglo XVIII siete puentes que cruzaban el río Pregel. Unían dos islas que había en el río entre sí y cada una de ellas a las orillas. La gente de la ciudad venía entreteniendose por largo tiempo con este problema: ¿Es posible recorrer los siete puentes con un paseo continuo sin volver a recorrer dos veces el mismo puente?
El matemático suizo Leonard Euler se interesó en el problema de los puentes de Königsberg. En 1736, publicó un trabajo en el que demostraba que no era posible encontrar un trayecto que pudiese cruzar cada puente una sola vez sin omitir ninguno de ellos.
Para empezar, Euler formuló el problema de la siguiente manera: “En la ciudad de Königsberg, en Prusia, hay una isla A llamada Kneiphof, rodeada por los dos brazos del río Pregel. Hay siete puentes a, b, c, d, e, f y 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”.
La idea genial de Euler fue representar la ciudad de Königsberg como un grafo en el que las cuatro partes de la misma eran los vértices y los siete puentes eran las aristas.
Un grafo es básicamente un conjunto no vacío (al menos contiene un elemento) de puntos llamados vértices y un conjunto de líneas llamadas aristas cada una de las cuales une dos vértices.
- Se llama lazo a una arista que une un vértice consigo mismo. Se dice que dos vértices son adyacentes si existe una arista que los une.
- Se dice que un grafo es simple si para cualesquiera dos vértices existe a lo sumo una arista que los une. En otro caso se denomina multigrafo.
- Si v es un vértice de un grafo, se denomina grado de v al número de aristas que inciden en el mismo (por convenio de considera que un lazo cuenta dos veces al determinar el grado de su vértice).
Euler consiguió, a partir de este sencilló esquema, encontrar la solución: Para poder recorrer un sistema de este tipo, los vértices "intermedios" deben tener un número par de aristas. Es decir, deben tener una vía para entrar y una vía para salir. Sólo los puntos de inicio y salida pueden tener un número impar de aristas.
Por tanto lo único que tenemos que hacer es calcular el grado de cada vértice. Si tenemos más de dos vértices de grado impar el recorrido no será posible; por el contrario, si tiene sólo dos vértices o ningún vértice con grado impar entonces sí se podrá recorrer de esa forma (no puede haber sólo un vértice con grado impar ya que el número de vértices de grado impar es par).
Este problema dió origen a la teoría de grafos.