Teoría de grafos: los siete puentes de Königsberg
Graph theory: seven bridges of Königsberg
- Fecha
- 1736 · fiabilidad alta
- Lugar
- San Petersburgo, Rusia
- Autoría
- Leonhard Euler
- Personas
- 👤 Leonhard Euler1707–1783
- Ámbito
- Saber y símbolos
Qué se descubrió
Al demostrar que no existe un paseo que cruce cada puente exactamente una vez, Euler abstrajo el problema a vértices y aristas y dio el criterio de los grados pares. Nacen la teoría de grafos y la topología.
El problema surgió en Königsberg (Kaliningrado), pero Euler lo resolvió y presentó en la Academia de San Petersburgo.
A qué dio paso
- teoría de grafos
- topología
- redes y algoritmos de caminos
- fórmula de Euler para poliedros
Se apoya en
- geometria situs de Leibniz
Hizo posible
- Fórmula de Euler para poliedros (V - A + C = 2)1750
- Teorema de Ramsey1930
- Algoritmo de Dijkstra de caminos mínimos1956
- análisis de redes eléctricas (Kirchhoff)
- enrutamiento en internet
- logística