Los puentes de Koenigsberg

LOS PUENTES DE KOENIGSBERG

La rama de la geometría que trata de las magnitudes ha sido celosamente estudiada en el pasado, pero existe otra rama que ha permanecido casi desconocida hasta ahora. Leibniz fue el primero en tratar de ella, llamándola "geometría de la posición" (geometría situs). Esta rama de la geometría trata de las relaciones que dependen solamente de la posición, e investiga las propiedades de la posición. No tiene en cuenta las magnitudes ni requiere cálculos con cantidades. Pero hasta ahora no se ha dado ninguna definición satisfactoria de los problemas que pertenecen a esta geometría de la posición ni del método que ha de utilizarse para resolver sus problemas. Fue divulgado recientemente un problema que, aunque ciertamente parecía pertenecer a la geometría, sin embargo, no requería la determinación de magnitud alguna, ni podía resolverse por un cálculo cuantitativo. Por consiguiente, no dudé en adscribirlo a la geometría de la posición, especialmente porque la la solución requería solamente la consideración de la posición, siendo el cálculo totalmente inútil. En este artículo daré una relación del método que he descubierto para la solución de este tipo de problemas, que puede servir como un ejemplo de la geometría de la posición.

El problema, que según entiendo es muy bien conocido, se enuncia así:

Se me ha informado de que, mientras unos negaban la posibilidad de hacerlo y otros lo dudaban, nadie sostenía que fuese posible realmente. Sobre la base precedente he formulado yo mismo el el siguiente problema muy general:

"Dada una configuración cualquiera del río y de los brazos en los que pueda dividirse, así como un número cualquiera de puentes, determinar si es posible o no cruzar cada puente exactamente una vez".

El problema particular de los siete puentes de Koenigsberg podría resolverse haciendo meticulosamente una tabla de todos los recorridos posibles, asegurándose así, por inspección de cuál de todos ellos, si es que alguno hay, satisface lo exigido. Este método de solución, sin embargo, es demasiado tedioso y difícil a causa del gran número de combinaciones posibles, y en otros problemas en los que se da un gran número de puentes no podría ser utilizado en absoluto... Por lo tanto, lo descarté y traté de buscar otro más restringido a su alcance, a saber, un método que mostrase solamente si se puede descubrir un camino que satisfaga la condición prescrita. Tal intento, pensé, sería más simple.

Todo el método se apoya en la forma apropiada y conveniente en la que denoto el paso de los puentes. Uso letras mayúsculas A, B, C, D, para designar las diversas porciones de tierra que están separadas una de otra por el río. Así, cuando una persona va del área A al área B a través del puente a o b, denoto este paso mediante las letras AB, designando la primera el área de donde ha venido y la segunda el área de llegada, después de cruzar el puente. Si el caminante cruza después el puente f desde B a D, este paso se denota mediante las letras BD. Los dos pasos AB y BD realizados sucesivamente son denotados simplemente por las letras ABD, donde la letra B designa el área a la cual conduce la primera travesía, así como el área de partida de la segunda travesía de puentes.

Análogamente, si el caminante parte de D a través del puente g hacia C, se designan los tres pasos sucesivos de puentes mediante las cuatro letras ABDC... El cruce de cuatro puentes vendrá representado por cinco letras, y si el caminante cruza un número arbitrario de puentes su camino vendrá descrito por un número de letras una unidad mayor que el número de puentes. Por ejemplo, se necesitan ocho letras para designar el cruce sucesivo de siete puentes.

Con este método no se presta atención alguna a los puentes que se usan, es decir, si el paso de un área a otra puede hacerse mediante diversos puentes, no importa cuál de ellos se use, supuesto que efectivamente conduce al área deseada. Así, si se pudiese describir un camino sobre los siete puentes de Koenigsberg de tal forma que se cruzase una sola vez, entonces deberíamos poder describir este camino usando ocho letras, y en esta serie de letras la combinación AB (ó BA) habría de aparecer dos veces, puesto que hay dos puentes, a y b, que unen las regiones A y B. Análogamente la combinación AC habría de aparecer dos veces, mientras que las combinaciones AD, BD y CD habrían de hacerlo una sola vez cada una.

Nuestro problema queda así reducido a determinar si a partir de cuatro letras A, B, C y D se puede formar una serie de ocho letras en la cual todas las combinaciones que hemos mencionado aparecen el número de veces requerido. Antes de hacer el esfuerzo de tratar de encontrar tal ordenación de letras haremos bien, sin embargo, en considerar si su existencia es teóricamente posible o no. Porque si se pudiera mostrar que tal ordenación es de hecho imposible, entonces todo esfuerzo por encontrarlo sería en balde. Así pues, yo he tratado de encontrar una regla que determine sin dificultad, en lo que respecta a esta y a otras cuestiones semejantes, si es factible tal ordenación de letras.

A fin de encontrar tal regla considero una única región A a la que conducen un número arbitrario de puentes a, b, c, d, etc.

De estos puentes considero primero solamente el a. Si el caminante cruza este puente, ha de haber estado en A antes de cruzar o ha alcanzado A después de cruzarlo, y así, según el método precedente de notación, la letra A aparecerá exactamente una vez. Si hay tres puentes que conducen a A y el caminante cruza los tres, entonces la letra A aparecerá dos veces en la expresión de este camino. ya sea que el camino comience en A o no. Y si hay cinco puentes que conducen a A, la expresión del camino que los cruce todos contendrá la letra A tres veces. Si el número de puentes es impar, se aumenta este número en una unidad y se divide por dos. El cociente representa el número de veces que aparece la letra A.

Volvamos ahora al problema de Koenigsberg. Puesto que hay cinco puentes que conducen a ( y parten de) la isla A, la letra A ha de aparecer tres veces en la expresión que describe el camino requerido. La letra B ha de aparecer dos veces, puesto que hay tres puentes que conducen a B. Asimismo D y C han de aparecer cada una dos veces. Es decir la serie de ... letras que representa el cruce de los siete puentes ha de contener A tres veces y B, C y D cada una dos veces. Pero esto es completamente imposible con una serie de ocho letras (pues la suma de las cuatro letras requeridas es nueve). Así es claro que no se puede realizar una travesía de los siete puentes de Koenigsberg en la forma requerida.

Utilizando este método siempre podemos, si el número de puentes que conducen a una región particular es impar, determinar si es posible un camino que cruce cada puente exactamente una vez. Tal ruta existe si el número de puentes más uno es igual a la suma de los números que indican cuántas veces ha de aparecer cada una de las letras. Al contrario, si esta suma es mayor que el número de puentes más uno, como en nuestro ejemplo, entonces no puede trazarse la ruta deseada. La regla que he dado para determinar a partir del número de puentes que conducen a A cuántas veces aparecerá la letra A en la descripción de la ruta es independiente de que estos puentes provengan de una única región B o de varias regiones, porque para ello he tenido que considerar solamente la región A, intentando a partir de esto cuántas veces ha de aparecer la letra A.

Cuando el número de puentes que conducen a A es par, hemos de tener en cuenta si el camino comienza en A o no. Por ejemplo, si hay dos puentes que conducen a A y la ruta comienza en A, entonces la letra A aparecerá dos veces, una para indicar la salida de A por uno de los puentes y una segunda vez para indicar la llegada a A por el otro puente. Sin embargo, si el camino comienza su ruta en otra región, la letra A aparecerá solamente una vez, puesto que en mi método de descripción la simple aparición de A indica tanto una entrada en A como una salida de A.

Supongamos, por ejemplo, que hay cuatro puentes que conducen a la región A y que la ruta comienza en A. La letra A aparecerá entonces tres veces en la expresión de la ruta completa, mientras que si el camino hubiese comenzado en cualquier otra región, A aparecería solamente dos veces. Si son seis los puentes que conducen a A, la letra A aparecerá cuatro veces si es que A es el punto inicial, mientras que de otra forma aparecerá sólo tres veces. En general, si el número de puentes es par, el número de veces que aparecerá la letra A, cuando la región de partida no es A, será la mitad del número de puentes. Cuando la ruta comienza en A, será la mitad más uno.

Cada ruta ha de comenzar, por supuesto, en alguna región. Así, a partir del número de puentes que conducen a cada región, determino el número de veces que la letra correspondiente aparecerá en la expresión de la ruta entera del siguiente modo: Cuando el número de puentes es impar, lo aumento en uno y lo divido por dos; cuando el número es par, lo divido simplemente por dos. Entonces, si la suma de los números resultantes es igual al número de puentes más uno, el camino puede realizarse, si bien ha de comenzar en una región a la que conduzca un número impar de puentes. Pero si la suma es una unidad menor que el número de puentes más uno, el camino es posible si su punto inicial es una región a la que conduzca un número par de puentes, ya que en este casola suma se incrementa de nuevo en una unidad.

Mi procedimiento para determinar si en un sistema dado de ríos y puentes es posible cruzar cada puente una sola vez es el siguiente:

1. En primer lugar designo las diferentes regiones separadas por el agua mediante A, B, C, etc.

2. En segundo lugar tomo el número total de puentes, lo aumento en una unidad, y escribo el número resultante en la parte superior del papel.

3. En tercer lugar, bajo este número escribo las letras A, B, C, etc., en una sola columna, y enfrenta de cada letra anoto el número de puentes que conducen a cada región particular.

4. Escribo un asterisco junto a cada letra a la que corresponde un número par.

5. En una tercera columna escribo, junto a cada número par, la mitad de dicho número, y junto a cada número impar, la mitad de este número impar aumentado en una unidad.

6. Sumo la última columna de números. Si la suma es una unidad menor que, o igual que el número escrito inicialmente en la parte superior del papel, concluyo que la ruta es posible. Pero ha de hacerse notar que cuando la suma es una unidad menor que el número de la parte superior, la ruta entonces ha de comenzar en una región señalada con un asterisco, y ... que cuando estos dos números son iguales, entonces la ruta ha de comenzar en una región que no contenga ningún asterisco.

Para el problema de Koenigsberg, los cálculos son los siguientes:

La última columna suma ahora más que 8, y por lo tanto, el camino requerido es imposible.

Consideremos el ejemplo de dos islas con cuatro ríos que las rodeen. Son quince los puentes, señalados por a, b, c, d, etc., que cruzan el agua alrededor de las islas y los ríos adyacentes. El problema consiste en determinar si se puede realizar un trayecto que atraviese todos los puentes, pero ninguno más de una vez.

Comienzo señalando las regiones que están separadas por el agua con las letras A, B, C, D, E, F; hay seis.Segundo, tomo el número de puentes (15), añado una unidad (16) y escribo este número en la parte superior. Tercero, escribo las letras A, B, C, etc. en una columna y enfrente de cada letra escribo el número de puentes que que dan a aquella región, por ejemplo, ocho puentes para A, cuatro para B, etc. Cuarto, marco con un asterisco las letras a las que corresponden números pares. Quinto, en una tercera columna escribo la mitad del correspondiente número par, o, si el número es impar, añado una unidad y escribo la mitad del número así obtenido. Sexto, sumo los números de la tercera columna y obtengo 16. De la siguiente forma:

La suma de la tercera columna es la misma que el número 16 que aparece arriba y, por lo tanto, se concluye que el trayecto puede realizarse si comienza en las regiones D o E, cuyos símbolos no tienen asterisco. La expresión representa una ruta posible:

E a F b B c F d A e F f C g A h C i D k A m E n A p B o E l D

Aquí he indicado por letras minúsculas entre las mayúsculas los puentes que se cruzan.

Por este método podemos determinar fácilmente, incluso en caso de complejidad considerable, si una única travesía de los puentes sucesivamente es posible o no. Pero quisiera ahora presentar otro método mucho más simple, que se deduce muy fácilmente de lo precedente, mediante unas cuantas observaciones preliminares. En primer lugar, obsérvese que la suma de los números escritos en la segunda columna es necesariamente el doble del número de puentes existente. La razón consiste en que en la tabla de los puentes que conducen a las diversas regiones cada puente es contado dos veces, una vez por cada una de las dos regiones que une.

De esta observación se sigue que la suma de los números de la segunda columna ha de ser un número par, puesto que su mitad representa el número de puentes. Por lo tanto ... si algunos de entre los números frente a las letras A, B, C, etc. son impares, un número par de entre ellos deben ser impares. En el problema de Koenigsberg, por ejemplo, los cuatro números enfrente de las letras A, B, C, D eran impares, mientras que en el ejemplo último sólo dos de los números eran impares, los correspondientes a D y E.

Puesto que la suma de los números correspondientes a A, B, C, etc. es el doble del número de puentes, es claro que si esta suma se aumenta en dos unidades y luego se divide por dos, el número resultante ha de coincidir con el número escrito en la parte superior. Cuando todos los números en la segunda son pares, y se escribe en la tercera la mitad de cada uno de ellos, el total de esta columna será una unidad menor que el número en la parte superior. En este caso será siempre posible cruzar todos los puentes. Ya que, cualquiera que sea la región donde el trayecto se comience, habrá siempre un número par de puentes que conduzcan a ella, lo cual es la condición...

Además, cuando sólo dos de los números enfrente de las letras son impares, y los otro son pares, la ruta requerida es posible, supuesto que se comience en una región a la que conduzca un número impar de puentes. Tomamos la mitad de cada número par, y asimismo la mitad de cada impar aumentado en una unidad, según nuestro método requiere, y la suma de estas mitades será entonces una unidad mayor que el número de puentes, y así igual al número escrito en la parte superior. Pero cuando un número par mayor que dos de entre los números en la segunda columna son impares, es claro que la suma de los números de la tercera columna será mayor que el número de la parte superior y así el camino deseado es imposible.

Así, para cualquier configuración que surja, el modo más fácil de determinar si es posible cruzar todos los puentes de una sola vez consiste en aplicar las siguientes reglas:

1. Si hay más de dos regiones a las que conduce un número impar de puentes, ninguna ruta se puede hallar que satisfaga las condiciones requeridas.

2. Si, por el contrario, hay sólo dos regiones con un número impar de puentes que conduzcan a ellas, el camino pedido se puede realizar, supuesto que se comience en una de tales regiones.

3. Si, finalmente, no hay ninguna región a la que conduzca un número impar de puentes, el camino pedido se puede realizar, comenzando en cualquier punto.

Estas reglas resuelven completamente el problema inicialmente propuesto.

Tras haber determinado que existe realmente un camino, nos queda la cuestión de cómo hallarlo. Para esto nos servirá la siguiente regla:

Donde sea posible eliminamos mentalmente todo par de puentes que unan las mismas dos regiones. Esto reduce de ordinario considerablemente el número de puentes. Luego, y esto no debería ser difícil, procedemos a trazar la ruta requerida a través de los restantes puentes. El esquema de esta ruta, una vez que la hemos encontrado, no será fundamentalmente modificado por la adición de los puentes que eliminamos de nuestra consideración inicialmente, como muestra un momento de reflexión. Por lo tanto pienso que no es necesario decir nada más acerca de la forma de encontrar las rutas.