Quimica General de Umsa

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:
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
Euler 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
El 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.
Los 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.

Quimica General de Umsa

Cargado por

Copyright:

Formatos disponibles

Quimica General de Umsa

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Quimica General de Umsa

Cargado por

Copyright:

Formatos disponibles

Euler: Los puentes de Konigsberg y la teoría

También podría gustarte