Los habitantes de Königsberg se preguntaban si podían recorrer la ciudad cruzando cada uno de sus siete puentes una sola vez. En 1736, Leonhard Euler respondió que no, y para hacerlo ignoró todo lo que no importaba: distancias, calles y formas.
Intenta adivinar · luego te explicamos
Para resolver el problema de los puentes, Euler representó cada zona de tierra como un punto y cada puente como una línea entre dos puntos. ¿Cómo se llama esa estructura?
Un grafo es una estructura matemática formada por nodos, también llamados vértices, y aristas, también llamadas enlaces, que conectan pares de nodos. Es la forma más simple de representar relaciones.
Su poder está en lo que ignora. Euler resolvió el problema de Königsberg en 1736 dejando de lado distancias, calles y formas, y quedándose solo con qué zona conectaba cada puente. Con eso demostró que el recorrido pedido era imposible, y fundó la teoría de grafos.
Casi cualquier sistema de relaciones se puede ver como un grafo: personas y amistades, ciudades y carreteras, páginas web e hipervínculos, proteínas e interacciones.
Las aristas pueden tener dirección, como seguir a alguien en una red social sin que te siga de vuelta, o peso, como la distancia de una carretera. El resto de este tema usa estas piezas para medir quién importa en una red y cómo se mueven las cosas por ella.