Dos islas, dos orillas, siete puentes. Contar los puentes por orilla da 3, 3, 3 y 5, y los grados suman 3 + 3 + 3 + 5 = 14 (primer enlace; el tercer enlace obtiene el mismo 14 como 3 × 3 + 5, que es la agrupación más rápida). La mitad de ese total es el número de puentes —el segundo enlace divide y da 7— y la relación no es exclusiva de este mapa: cada puente contribuye a dos orillas, así que los grados tienen que ser el doble del número de aristas. El cuarto enlace, 4 × 3/2 = 6, es el número de parejas de masas de tierra disponibles para unir con un puente, y hay siete puentes que sentar en seis parejas, así que al menos una pareja de masas de tierra está unida por dos puentes en lugar de uno.
El argumento de Euler es que un paseo que cruce cada puente una vez tiene que entrar y salir por parejas de cada masa de tierra por la que pasa, así que todo vértice usado como punto de parada tiene grado par; solo el primer y el último vértice del paseo están exentos, y solo hay dos. Königsberg tiene cuatro vértices impares, así que no existe ningún paseo del tipo pedido, y la prueba está completa antes de que nadie mida un río. Esa es la razón por la que el artículo se trata como el primer teorema de la teoría de grafos y no como la solución de un pasatiempo: las distancias, las formas de las orillas y las anchuras del Pregel son todas irrelevantes, y Euler lo dice, colocando el problema en una geometría de la posición en lugar de una geometría de la magnitud. Dos de los siete puentes fueron destruidos en 1944 y nunca se reconstruyeron, así que hoy la pregunta es de turista; la aritmética de aquí va sobre el mapa que le enviaron a Euler en 1735.
Respuesta
14
Cómo leerla
La suma de los cuatro grados. El segundo enlace la reduce a la mitad en los siete puentes; el tercero la suma de otra manera; el cuarto cuenta las parejas de masas de tierra.
Fuente
Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis', 1736, the founding paper of graph theory; the Königsberg bridges on the Pregel were seven in Euler's map, two of which were destroyed in 1944 and not rebuilt
Resuélvelo en la calculadora
Estos enlaces abren la calculadora adecuada con los números de este problema ya escritos. La línea de arriba es lo que debería mostrar la pantalla: compruébalo tú mismo.