Problema de los siete puentes de Königsberg
Se sabe que el problema de los siete puentes de Königsberg está en el origen de la topología y la teoría de grafos . Resuelto por Leonhard Euler en 1735, este problema matemático se presenta de la siguiente manera:
|
|
| La ciudad de Königsberg (ahora Kaliningrado ) está construida alrededor de dos islas ubicadas en el Pregel y conectadas entre sí por un puente. Otros seis puentes conectan las orillas del río con cualquiera de las dos islas, como se muestra en el plano anterior. El problema es determinar si existe o no un paseo por las calles de Königsberg que permita, desde un punto de partida de su elección, pasar una vez y sólo una vez por cada puente, y volver a su punto de partida, entendiéndose que sólo se puede cruzar el Pregel pasando por puentes. |
Resolución de problema
Tal paseo no existe, y fue Euler quien dio la solución a este problema caracterizando los grafos que hoy llamamos “ eulerianos ” en referencia al ilustre matemático, utilizando un teorema cuya rigurosa demostración fue de hecho publicada solo en 1873, por Carl Hierholzer .
Este problema solo tiene interés histórico en esta forma no generalizada, porque en este caso es bastante intuitivo demostrar que la caminata solicitada no existe. Para ver esto, simplemente asocie un gráfico con la ciudad como en la figura anterior y asuma que existe el paseo deseado. Entonces podemos, a partir de la caminata, ordenar los siete bordes del gráfico de modo que dos bordes consecutivos con respecto a nuestro orden sean adyacentes en el gráfico (considerando que el último y el primer borde son consecutivos, ya que hay un regreso al punto de partida ).
Por tanto, cualquier vértice del gráfico es necesariamente incidente a un número par de aristas (ya que si es incidente a una arista, también es incidente a la arista anterior o que le sigue en orden). Pero el gráfico tiene vértices que inciden en tres aristas, de ahí la imposibilidad.
Tenga en cuenta que incluso si no requerimos el regreso al punto de partida, no existe una caminata que cruce cada puente una vez y solo una vez. Existiría si como máximo dos vértices del gráfico, correspondientes a los puntos a elegir respectivamente como salida y llegada, incidieran en un número impar de aristas, o los vértices del gráfico de puentes de Königsberg fueran los cuatro en este caso; caminar es, por tanto, imposible. Sin embargo, bastaría con eliminar o agregar cualquier puente para que el gráfico modificado permita recorrer todos los puentes sin retorno (solo quedan dos vértices de incidencia impar). Y hay al menos dos puentes bien elegidos que deben agregarse o eliminarse para permitir el viaje de regreso inicialmente buscado.
Otra forma intuitiva de ver este problema, sin recurrir a la teoría de grafos, es considerar que para cubrir todos los puentes, tendrás que entrar y salir de cada isla (o orilla) nuevamente. Así, en cada isla durante todo el recorrido, habrá tantos puentes de entrada como puentes de salida, con los dos juegos de puentes separados. De lo contrario, cada isla (u orilla) solo podría ser un lugar de salida o un lugar de llegada y el circuito no podría cerrarse sin pasar nuevamente por uno de los puentes ya impresos en el resto del recorrido. Por lo tanto, cada isla (u orilla) debe tener un número par de puentes que la conecten con las otras islas o costas. En el ejemplo de Königsberg, tal solución no existe ya que, por ejemplo, West Island tiene cinco puentes, que no se pueden dividir en dos conjuntos iguales de puentes de entrada o salida. Lo mismo ocurre con la ribera norte con tres puentes (ni siquiera parejos), la ribera sur con tres puentes también y la isla este, con tres puntas también.
Finalmente, podemos notar que si existe tal ruta (un número par de puentes en cada isla u orilla), no necesariamente existe una solución única ya que podemos emparejar cada puente de entrada con cualquiera de los puentes de salida. Una solución única (en el sentido de por supuesto) solo existe si solo hay dos puentes en cada isla (o costa), el gráfico de adyacencia se reduce a un solo círculo que pasa por todos los puentes. Sin embargo, siempre podemos encontrar soluciones que requieran no cruzar nunca su camino durante el recorrido: basta con emparejar los sucesivos puentes a lo largo de la orilla. Pero aquí, nuevamente, la solución no es única (en el sentido por supuesto), si hay más de dos puentes que entran o salen de la misma isla (o orilla del río).
Sin embargo, la paridad del número de puentes que conectan cada isla u orilla con las demás no impone la paridad del número total de puentes que conectan todas las islas (o costas). Por ejemplo, con una ciudad portuaria en una isla que forma un delta en la desembocadura marítima de un río y a lo largo de sus orillas, existe una solución con solo tres puentes: un puente conecta la isla con un banco por encima de cada uno de los dos brazos del delta. y un tercer puente conecta las dos orillas del río antes del delta. El mismo caso de tres puentes también se aplica a una ciudad centrada en una sola isla fluvial: un puente conecta la isla sobre cada uno de los dos brazos del río y otro puente conecta directamente las dos orillas del río río arriba o río abajo de la isla.
Notas y referencias
- Jean-Gabriel Ganascia , Le Petit Trésor: diccionario de informática y ciencias de la información , Flammarion ,1998( leer en línea ).
Bibliografía
- (la) Leonhard Euler , "Solutio problematis ad geometriam situs relevanteis" , en Memorias de la Academia de Ciencias de Berlín ,1735( leer en línea [PDF] )
- Édouard Lucas , Recreaciones matemáticas: Los cruces, los puentes, los laberintos las reinas, el solitario, la numeración, el baguenaudier, el teaser , París, Gauthier Villars,1882( leer en línea )El problema de los siete puentes es el tema de la "recreación n o 2" bajo el título "Los puentes de París en 1880" . leer en línea en Gallica