Instinto Lógico

Recuerda que nadie debe pensar por tí.

Euler: Los puentes de Konigsberg y la teoría de grafos

En matemáticas ocurre con cierta frecuencia que acertijos, paradojas y problemas en apariencia intranscendentes han dado paso teorías y resultados de gran transcendencia y  profundidad. Este es el caso del la curiosidad que despertó el problema del paseo por los puentes de Konigsberg (actual Kaliningrado) que traía de cabeza a muchos de sus habitantes sin dejar de ser una curiosidad que no iba más allá de chascarrillos de paseantes y que cuando se ocupó de él Leonard Euler (1707-1783) y lo trató de forma matemática dio lugar a una nueva rama de las matemáticas que se conoce como teoría de grafos.

Con teoría de grafos se resuelven problemas de estrategias de juegos, de cálculo de rutas óptimas, así como su aplicación a las cuestiones más diversas como optimización en la logística, la robótica, la genética, la sociología o el diseño de redes.

El problema

El problema que dio origen a la teoría de grafos era, como hemos señalado, el paseo atravesando los siete puentes sobre el río Pregel. Este río tenía una isla, isla de Kneiphof, en medio  a la que llegaban cinco puentes, dos a cada orilla y otro que llevaba a otra isla dentro del río, que, a su vez estaba unida a las orillas por sendos puentes, tal y como indica la figura siguiente:

 Puentes de Konigsberg

El problema planteado por los paseantes de Konigsberg era el siguiente: ¿Cómo puede hacerse un paseo atravesando una sola vez cada uno de los siete puentes?. La experiencia había demostrado que era imposible hacer tal paseo, pero cuando el problema fue estudiado por Euler obtuvo una serie  de resultados que dieron luz a este problema y abrió la matemática a nuevos horizontes.

La simplificación de problema

Grafo puentes de KonigsbergEuler estaba en San Petersburgo cuando le llegó la noticia del problema de los paseantes de Konigsberg. Para resolverlo Euler trazó un esquema simplificado de la situación. La idea básica consistió en sustituir la Tierra por puntos y los puentes por arcos.

Los puntos 1 y 3 representan las orillas del río, el punto 2 la isla Kneiphof y el punto 4 representa la otra isla. Las líneas trazadas entre los puntos son los puentes que se designan con las mismas letras con las que hemos designado los puentes en el gráfico anterior.

El problema ahora queda reducido a saber si ese gráfico, que llamaremos grafo, se puede dibujar con una línea continua, sin levantar el lápiz del papel ni “repintar” ningún arco.

Un poco de vocabulario

La gráfica anterior se llama grafo, se designa con G,  y  está formado por un número finito de puntos, llamados vértices o nodos, unidos por una serie de líneas, llamadas arcos.

Un vértice tiene grado par si en él concurren un número par de arcos.

Un vértice tiene grado impar si en él concurren un número impar de arcos.

Observación: En la gráfica anterior los vértices 1, 3 y 4 de orden tres y el 2 de orden cinco

Algunos resultados de Euler sobre grafos

El razonamiento de Euler fue así:

de cualquier sector al que se llegue(se entiende por sector una de las orillas del río o una de las dos islas), sin intención de quedarse hay que salir tantas veces como se entre. Si, como exigen las condiciones las entradas y salidas se deben hacer por puentes distintos, la cantidad de puentes usados para salir ha de ser la misma que la de usados para entrar, lo que quiere decir que la cantidad de puentes que inciden en el cualquier sector de paso ha de ser par.

Como, el caso de los puentes de Konigsberg  el número de puentes que inciden en cada sector es impar el problema planteado por los paseantes no tiene solución.

Como consecuencia de este resultado definió grado de un vértice y expresó, en función de este concepto sus principales consecuencias del problema de los puentes de Konigsberg, expresadas en términos de grafos.  Entre otras destacamos, las siguientes:

Propiedad 1: La suma de los grados de los nodos de un grafo es el doble del número de aristas.

De la propiedad anterior se sigue, de manera natural, la siguiente

Propiedad 2: El número de nodos de grado impar de un grafo tiene que ser par.

Propiedad  3: Si todos los vértices son pares puede hacerse un recorrido partiendo y acabando en el mismo vértice.

Propiedad 4: Si la gráfica tiene a lo sumo dos los vértices impares puede ser recorrido, pasando una vez por cada arco, pero no se vuelve al punto de partida.

Propiedad 5: Si un grafo tiene 2n vértices impares se necesitarán exactamente n viajes distintos para recorrerla (hay que levantar n – 1 veces el lápiz del papel).

Variaciones del problema

puentesDeKonigsbergVariacion1El problema planteado en Konigsberg no era resoluble, pero si hubiera un puente más que uniera directamente las dos orillas, representadas en el grafo por los vértices 1 y 3 y elimináramos el puente que unía ambas islas,  el grafo inicial se habrá transformado de la siguiente forma.

Los vértices 1, 2 y 3 serían de orden cuatro, mientras que el vértice 4 sería de orden dos. Por lo tanto, como todos los vértices son pares, pueden ser recorridos en un paseo todos los puentes pasando por ellos una sola vez y volveremos al vértice desde el que hemos comenzado el paseo.

Si hubiéramos añadido un puente más que uniera directamente las dos orillas, representadas en el grafo por los vértices 1 y 3 sin eliminar el puente que unía ambas islas,  el grafo inicial se habrá transformado.

puentesDeKonigsbergVariacion2Los vértices 1 y 3 serían de orden cuatro, mientras que el vértice 2 seguiría siendo de orden cinco y el vértice 4 de orden tres, por lo tanto, como el grafo tiene dos vértices impares el grafo puede ser recorrido en un paseo todos los puentes pasando por ellos una sola vez. Pero no volveremos al vértice desde el que hemos comenzado el paseo  por ejemplo el paseo  12324314, que recorre los arcos.

Be Sociable, Share!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Instinto Lógico © 2014 Frontier Theme